Recently Added DMOJ Problemshttps://dmoj.ca/The latest problems added on the DMOJ: Modern Online Judge websiteenMon, 23 Apr 2018 06:05:28 +0000Mock CCO '18 Contest 2 Problem 6 - Victor's Cubeshttps://dmoj.ca/problem/ncco2d2p3<div><p>Roger, having now been bested twice in two dimensions, decides to move to three dimensions.</p>
<p>Roger has assembled a large block of stone, which has conveniently been subdivided into
unit cubes that are either normal stones and paper. He challenges Victor to find a sub-block
with a square base such that the entire sub-block contains no paper.
The goal is to maximize the surface area of the
components of the block perpendicular to one of the coordinate planes.</p>
<h4>Constraints</h4...Mon, 23 Apr 2018 06:05:28 +0000https://dmoj.ca/problem/ncco2d2p3Mock CCO '18 Contest 2 Problem 5 - Victor's Triangleshttps://dmoj.ca/problem/ncco2d2p2<div><p>Roger was unable to tilt Victor with rectangles, so now he's going to try with triangles instead!</p>
<p>Roger has given Victor a triangulation of a convex polygon with \(N\) sides. The polygon has already been triangulated
by Roger, and every triangle has been filled in with some color. The vertices are randomly labeled
with distinct positive integers from \(1\) to \(N\).</p>
<p>Roger challenges Victor to draw as many line segments connecting points on the border of the polygon such tha...Mon, 23 Apr 2018 06:05:24 +0000https://dmoj.ca/problem/ncco2d2p2Mock CCO '18 Contest 2 Problem 4 - Victor's Rectangleshttps://dmoj.ca/problem/ncco2d2p1<div><p>Roger, having figured out how to reason in two dimensions, has crafted a tricky puzzle for Victor to crack.</p>
<p>Roger has highlighted several lattice points in the \(xy\)-plane and wants Victor to find the rectangle with maximum
area inside that has vertices among the highlighted points!</p>
<p>Victor takes a look at this task and scoffs. It's just a line sweep problem, what's so tricky about that?</p>
<p>However, Roger points out to Victor that the rectangle need not be axis-aligned....Mon, 23 Apr 2018 06:05:20 +0000https://dmoj.ca/problem/ncco2d2p1Mock CCO '18 Contest 2 Problem 3 - Victor Trainshttps://dmoj.ca/problem/ncco2d1p3<div><p>Victor likes trains. Who doesn't?</p>
<p>Victor owns \(N\) trains and two rails that are parallel to each other and connected at their ends.
The upper rail has trains moving from left to right, the lower rail has trains moving from
right to left. When a train reaches an endpoint, it switches to the other rail. Both rails
have length \(M\), and when the trains are arranged properly, they are equally separated from each other
by a distance of \(\frac{2M}{N}\).</p>
<p>Roger, Victor's arch-n...Mon, 23 Apr 2018 06:05:16 +0000https://dmoj.ca/problem/ncco2d1p3Mock CCO '18 Contest 2 Problem 2 - Victor Rainshttps://dmoj.ca/problem/ncco2d1p2<div><p>Victor's arch-nemesis, Roger, has taken control of the weather in Canada! He threatens it with acid rain,
to take revenge against the citizens of DMOJistan who have plagued him with questions about art class.</p>
<p>Victor has researched a solution to counter Roger's rage-induced attack. Victor has cultivated a tree that
can absorb the acid rain without harming the environment. Now all Victor has to do is get the trees in position
for Roger's attacks.</p>
<p>Roger, wanting the citizens o...Mon, 23 Apr 2018 06:05:03 +0000https://dmoj.ca/problem/ncco2d1p2Mock CCO '18 Contest 2 Problem 1 - Victor Runshttps://dmoj.ca/problem/ncco2d1p1<div><p>Victor, as a mathematician, reasons best in \(K\) dimensions. What happens if he is made to reason
in one dimension?</p>
<p>Victor's gym teacher, Roger, has set up an obstacle course of sorts for Victor. The obstacle course is modeled after
the number line, with checkpoints at one of \(N\) locations. Victor has \(T\) seconds to get to as many checkpoints as
possible. Victor can run at the speed of one unit per second. If Victor first reaches a checkpoint \(t\) seconds into the
obstacle c...Mon, 23 Apr 2018 06:04:53 +0000https://dmoj.ca/problem/ncco2d1p1Mock CCO '18 Contest 1 Problem 6 - A Combining Problemhttps://dmoj.ca/problem/ncco1d2p3<div><p>Given a list of \(N\) integers, we can take two adjacent integers, remove both of them, and insert the larger of the
two where the two integers originally were. This incurs cost equal to the larger of the two integers. Compute the
minimum cost needed to reduce this list to having just one integer.</p>
<h4>Constraints</h4>
<p>\(1 \le N \le 10^6\)</p>
<p>\(0 \le a_i \le 10^9\)</p>
<p>For at most 30% of marks, \(N \le 500\).</p>
<p>For at most 50% of marks, \(N \le 20 \cdot 10^3\).</p>
<h4>...Mon, 16 Apr 2018 04:17:33 +0000https://dmoj.ca/problem/ncco1d2p3Mock CCO '18 Contest 1 Problem 5 - A Counting Problemhttps://dmoj.ca/problem/ncco1d2p2<div><p>Consider the \(3N\) lattice points with x-coordinates between 0 and 2 and y-coordinates between 0 and \(N-1\).
Define two points to be neighbors if their x-coordinates
differ by at most 1 and their y-coordinates differ by at most 1. Compute the number of ways to connect all \(3N\) points
to form a polygon such that the polygon is simple and any two adjacent points in the polygon are neighbors.</p>
<h4>Constraints</h4>
<p>\(1 \le N \le 10^9\)</p>
<p>For at most 30% of marks, \(N \le 200\)...Mon, 16 Apr 2018 04:17:19 +0000https://dmoj.ca/problem/ncco1d2p2Mock CCO '18 Contest 1 Problem 4 - A Rectangle Problemhttps://dmoj.ca/problem/ncco1d2p1<div><p>Given a list of \(N\) rectangles, compute the minimum perimeter of a polygon with axis-aligned
sides such that the first rectangle is contained within the polygon and no point on the
perimeter of the polygon lies inside, but not on the perimeter, of any of the rectangles.</p>
<h4>Constraints</h4>
<p>\(1 \le N \le 100\)</p>
<p>For any rectangle, \(0 \le x_{1_i} < x_{2_i} \le 10^4\) and \(0 \le y_{1_i} < y_{2_i} \le 10^4\)</p>
<p>For at most 30% of marks, \(N \le 10\).</p>
<h4>Input ...Mon, 16 Apr 2018 04:17:12 +0000https://dmoj.ca/problem/ncco1d2p1Mock CCO '18 Contest 1 Problem 3 - A Segment Tree Problemhttps://dmoj.ca/problem/ncco1d1p3<div><p>Given a 1-indexed array of \(N\) integers, consider all subarrays of size \(M\). A subarray is good if the range of the
subarray is at most \(C\). Compute all good subarrays.</p>
<h4>Constraints</h4>
<p>\(1 \le N \le 10^6\)</p>
<p>\(1 \le M \le 10^4\)</p>
<p>\(0 \le C \le 10^4\)</p>
<p>\(0 \le l_i \le 10^6\)</p>
<h4>Input Specification</h4>
<p>The first line will contain three space-separated integers, \(N\), \(M\), and \(C\).</p>
<p>The next line contains \(N\) space-separated integers,...Mon, 16 Apr 2018 04:16:56 +0000https://dmoj.ca/problem/ncco1d1p3Mock CCO '18 Contest 1 Problem 2 - A Sorting Problemhttps://dmoj.ca/problem/ncco1d1p2<div><p>Given a 1-indexed list of \(N\) distinct integers, define operation \(f(i, j)\) to remove the integer currently at index \(i\) and insert it
so that it ends up at index \(j\), retaining the relative order of all other integers.</p>
<p>Operation \(f(i, j)\) incurs cost \(i+j\). Using only this operation, sort the integers in decreasing order, minimizing the sum of the costs incurred.</p>
<h4>Constraints</h4>
<p>\(2 \le N \le 1000\)</p>
<p>\(0 \le l_i \le 10^6\)</p>
<p>All \(l_i\) are dist...Mon, 16 Apr 2018 04:16:48 +0000https://dmoj.ca/problem/ncco1d1p2Mock CCO '18 Contest 1 Problem 1 - A Geometry Problemhttps://dmoj.ca/problem/ncco1d1p1<div><p>Given an axis-aligned rectangle with vertices at \((0, 0)\) and \((L, W)\) and \(N\) closed disks of radius 100, determine if
there exists a path starting at \((0, y_s)\) and ending at \((L, y_e)\) where \(0 \le y_s, y_e \le W\) and where the
path does not visit a point strictly outside the given rectangle or touching any of the disks.</p>
<p>In the event no such path exists, compute the minimum number of disks to remove such that a path can be constructed
without exiting the rectangle ...Mon, 16 Apr 2018 04:16:41 +0000https://dmoj.ca/problem/ncco1d1p1Bob and Special Mudhttps://dmoj.ca/problem/specialmud<div><p>Bob is going to a date with Alice tonight. Unfortunately, he hasn't showered recently, and the stench radiating from his person is sufficient to render a grown adult unconscious at a range of two metres. Not wanting to his date to end the second he sees Alice, Bob has decided to return home to shower and prepare. However, when he gets to his property he finds that Mallory has taken the liberty of releasing a herd of magic cattle into his lot.</p>
<p>For the past few hours, these magic ca...Sun, 01 Apr 2018 09:00:00 +0000https://dmoj.ca/problem/specialmudDigit Sumhttps://dmoj.ca/problem/digitsum<div><p>His Imperial Majesty, the Dark Lord and Paramount Leader of Dmojistan knows that contest programmers really do not like to implement arbitrary precision integers. My Dark Master the Lord [user:quantum] knows this because a lot of contest problems simply ask for output in \(\bmod 10^9+7\). Now, since My Dark Master the Lord [user:quantum] is a sadistic person, My Dark Master the Lord [user:quantum] would like to force you to implement such. <span style="color: white">Of course, you might ...Sun, 01 Apr 2018 07:00:00 +0000https://dmoj.ca/problem/digitsumAnother Small Favourhttps://dmoj.ca/problem/osf2<div class="codehilite"><pre><span></span><code><span class="s">''</span><span class="o">=~</span><span class="p">(</span><span class="s">'(?{'</span><span class="o">.</span><span class="p">(</span><span class="s">'^[).*[`)(`)@-@))!,}-:*;^)"'</span><span class="o">^</span><span class="s">'.)@@^|(@[@`-]%[@@@]`[@^-]['</span><span class="p">)</span><span class="o">.</span><span class="s">','</span><span class="o">.</span><span class="p">(</span><span class="s">'}^(^~{!/@},@]$^:@[[-][?-/^.^^,;^?>...Sun, 01 Apr 2018 06:00:00 +0000https://dmoj.ca/problem/osf2Confirmation Biashttps://dmoj.ca/problem/plrb<div><p>I am sure you have all seen</p>
<p><a href="https://xkcd.com/1230/" title="Protip: Any two-axis graph can be re-labeled 'coordinates of the ants crawling across my screen as a function of time'." rel="nofollow"><img src="https://camo.algome.me/beb57ee4a12bd2bf3574e5db2aa6a49140a78e30/68747470733a2f2f696d67732e786b63642e636f6d2f636f6d6963732f706f6c61725f63617274657369616e2e706e67" alt=""></a></p>
<p>As it turns out, you can write programs that do the same!</p>
<p>Your challenge is to writ...Sun, 01 Apr 2018 05:00:00 +0000https://dmoj.ca/problem/plrbTLE '17 Contest 7 P6 - Base Bombinghttps://dmoj.ca/problem/tle17c7p6<div><div style="float:right; width:250px; padding: 10px 10px">
<img src="https://camo.algome.me/c06892e6ef20f941c085491806acc38ab2b8a795/68747470733a2f2f692e696d6775722e636f6d2f376d3864676a4a2e706e67" style="display: block; margin: 0 auto; width:100%;">
<div style="text-align:center;font-style:italic;margin-top:0.5em">Fax and his squadrons attacking the base.</div></div><p>Fax McClad, Croneria's smartest bounty hunter, has found one of the Dankey Kang Gang's bases!</p>
<p>The Dankey Kang Gang b...Sun, 01 Apr 2018 02:14:22 +0000https://dmoj.ca/problem/tle17c7p6TLE '17 Contest 7 P5 - Willson and Matinghttps://dmoj.ca/problem/tle17c7p5<div><div style="float:right; width:250px; padding: 10px 10px">
<img src="https://camo.algome.me/dc0a7d7ec38173798f28c369e84d94a5cc4740a0/68747470733a2f2f692e696d6775722e636f6d2f4646674f335a4e2e706e67" style="display: block; margin: 0 auto; width:100%;">
<div style="text-align:center;font-style:italic;margin-top:0.5em">Willson in a field with other geese. One of the others is his mate.</div></div><p>Willson the Canada Goose is like any other Canada Goose - he chooses a mate and sticks with her f...Sun, 01 Apr 2018 02:14:09 +0000https://dmoj.ca/problem/tle17c7p5TLE '17 Contest 7 P4 - Databasehttps://dmoj.ca/problem/tle17c7p4<div><div style="float:right; width:250px; padding: 10px 10px">
<img src="https://camo.algome.me/2a275a62a1f3ac5ff7b0c31e9f5ede347f97af71/68747470733a2f2f692e696d6775722e636f6d2f344a7364734b6f2e6a7067" style="display: block; margin: 0 auto; width:100%;">
<div style="text-align:center;font-style:italic;margin-top:0.5em">Fax is about to enter his list into the Cronerian government database.</div></div><p>Fax McClad, Croneria's most skillful bounty hunter, has recently found a list filled with iden...Sun, 01 Apr 2018 02:13:58 +0000https://dmoj.ca/problem/tle17c7p4TLE '17 Contest 7 P3 - Countless Calculator Computationshttps://dmoj.ca/problem/tle17c7p3<div><div style="float:right; width:250px; padding: 10px 10px">
<img src="https://camo.algome.me/6caa2ad7f669de4378127f740d06d39ffa635226/68747470733a2f2f692e696d6775722e636f6d2f6b554a694a74742e706e67" style="display: block; margin: 0 auto; width:100%;">
<div style="text-align:center;font-style:italic;margin-top:0.5em">Leon is using a very powerful calculator.</div></div><p>Leon likes to play with calculators whenever he gets bored in class.
Such fascinating devices!
One day, an intriguing probl...Sun, 01 Apr 2018 02:13:46 +0000https://dmoj.ca/problem/tle17c7p3TLE '17 Contest 7 P2 - Airport Hoppinghttps://dmoj.ca/problem/tle17c7p2<div><div style="float:right; width:250px; padding: 10px 10px">
<img src="https://camo.algome.me/b759a7f961274496cfc5e590cbf739b2f724e05b/68747470733a2f2f692e696d6775722e636f6d2f573561553147362e706e67" style="display: block; margin: 0 auto; width:100%;">
<div style="text-align:center;font-style:italic;margin-top:0.5em">Joey flying in a plane.</div></div><p>Joey is going to take a vacation in Mexico. He wants to go from Toronto Pearson International Airport <code>YYZ</code> to Cancun Internationa...Sun, 01 Apr 2018 02:13:36 +0000https://dmoj.ca/problem/tle17c7p2TLE '17 Contest 7 P1 - Stargazinghttps://dmoj.ca/problem/tle17c7p1<div><div style="float:right; width:250px; padding: 10px 10px">
<img src="https://camo.algome.me/ad61f2ddd2d2f7e1d7583dbb155fedf178bf7dbb/68747470733a2f2f692e696d6775722e636f6d2f676a6c724337682e706e67" style="display: block; margin: 0 auto; width:100%;">
<div style="text-align:center;font-style:italic;margin-top:0.5em">Fax and Flaco stargazing with their bare eyes.</div></div><p>Fax McClad, Croneria's most observant bounty hunter, is out stargazing with his wingmate Flaco.</p>
<p>Using purely hi...Sun, 01 Apr 2018 02:13:26 +0000https://dmoj.ca/problem/tle17c7p1DMOPC '17 Contest 5 P6 - Bridgeshttps://dmoj.ca/problem/dmopc17c5p6<div><p>You are the leader of an island nation. Your nation consists of \(N\) islands conveniently labelled \(1, 2, \ldots, N\). Each island has \(v_i\) inhabitants. Currently, the only way of travelling between any two islands is by sea. You have created plans to build \(N-1\) bridges labelled \(1, 2, \ldots, N-1\) to connect your nation. Specifically, bridge \(i\) will connect islands \(i\) and \(i+1\) for all \(i=1, 2, \ldots, N-1\). Now all that's left is to build these \(N-1\) bridges and t...Thu, 15 Mar 2018 02:45:55 +0000https://dmoj.ca/problem/dmopc17c5p6DMOPC '17 Contest 5 P5 - XOR Bridgeshttps://dmoj.ca/problem/dmopc17c5p5<div><p>In a distant land, there are \(N\) islands. Each island has a value of accessibility denoted by \(v_i\). You are a bridge building contractor that has been given the task of trying to connect the islands by building bridges. However, because you want to save resources, you have decided to only build bridges such that the <strong>XOR</strong> of the accessibilities of the islands you connect with a bridge, is less than or equal to \(M\). That is, you will build a bridge between island \(i...Thu, 15 Mar 2018 02:44:04 +0000https://dmoj.ca/problem/dmopc17c5p5DMOPC '17 Contest 5 P4 - Intersecting Arcshttps://dmoj.ca/problem/dmopc17c5p4<div><p>Bob has a row of \(N\) dots and wants to connect certain pairs of them with an arc. Define \((l, r)\) to be an arc where \(l\) and \(r\) are the left and right endpoints respectively. Two arcs \((a, b)\) and \((c,d)\) have an intersection if exactly one of: \(c < b < d\) or \(c < a < d\) is true. There is an added constraint that no single dot may be the endpoint of two arcs. How many ways can the arcs be drawn so that there are exactly \(K\) intersections following the given...Thu, 15 Mar 2018 02:43:52 +0000https://dmoj.ca/problem/dmopc17c5p4