Recently Added DMOJ Problemshttps://dmoj.ca/The latest problems added on the DMOJ: Modern Online Judge websiteenTue, 05 Jun 2018 22:40:26 +0000DOOM 2018https://dmoj.ca/problem/doom<div><p>In a universe not that far away, people fight for their lives and for their freedom. No one understands exactly how this universe came to be, but it is rumored that a single constant rules this domain. Valiantly have the people in this universe tried to compute this constant, yet they don't know why the constant exists or what it is convenient for.</p>
<p>Some years ago, a legend with last name starting with C discovered this constant. Quietly, he discovered the true power of this consta...Tue, 05 Jun 2018 22:40:26 +0000https://dmoj.ca/problem/doomFibonacci Sequence (Harder)https://dmoj.ca/problem/fibonacci2<div><p>[user:quantum] is not feeling well today, and has decided to create a more painful version of the <a href="/problem/fibonacci">simple Fibonacci problem</a>.</p>
<p>Recall that the Fibonacci sequence is a well known sequence of numbers in which</p>
<p>\[F(n) = \begin{cases} 0, & \text{if } n = 0 \\ 1, & \text{if } n = 1 \\ F(n-2) + F(n-1), & \text{if } n \ge 2 \end{cases}\]</p>
<p>You are given a number \(N\) \((1 \le N \le 10^{100\,000})\), find the \(N^{th}\) Fibonacci numbe...Tue, 05 Jun 2018 02:28:43 +0000https://dmoj.ca/problem/fibonacci2CCO '18 P5 - Boring Lectures (Online Version)https://dmoj.ca/problem/cco18p5online<div><p><strong>Note: This problem is an online version of the <a href="https://dmoj.ca/problem/cco18p5">original version</a> held in CCO. Differences in the problem statement will be bolded. Note that the specifics of this problem are not set in stone, so constraints/limits/test data may change without notice. Feel free to submit strong test data for this problem if non-intended solutions AC.</strong></p>
<h5>Canadian Computing Olympiad: 2018 Day 2, Problem 2</h5>
<p>You have a schedule of \(N\...Fri, 01 Jun 2018 16:33:12 +0000https://dmoj.ca/problem/cco18p5onlineAPIO '13 P1 - Robotshttps://dmoj.ca/problem/apio13p1<div><p>The engineers at VRI (Voltron Robotics Institute) have built a swarm of \(n\) robots. Any two compatible robots that stands on the same grid can merge to form another composite robot.</p>
<p>We label the robots with number \(1\) to \(n\) \((n ≤ 9)\). Two robots are compatible if they have labels that are consecutive. Originally, each of the n robot has one unique label. A composite robot that is formed after merging two or more robots is assigned two labels, consisting of the minimum and...Mon, 28 May 2018 18:36:35 +0000https://dmoj.ca/problem/apio13p1CCO '18 P6 - Flop Sortinghttps://dmoj.ca/problem/cco18p6<div><h5>Canadian Computing Olympiad: 2018 Day 2, Problem 3</h5>
<p>Desperate to contribute to the CCO, Robert tried inventing a segment tree problem. The specification for that problem is:</p>
<blockquote><p>You are given a list of \(N\) distinct integers between \(1\) and \(N\). These are arranged in a row such that the \(i\)-th integer from the left is \(a_i\) , where \(1 \leq i \leq N\). We define a flop operation on a set of elements as swapping the minimum element of the set with the maxim...Sun, 20 May 2018 01:17:24 +0000https://dmoj.ca/problem/cco18p6CCO '18 P5 - Boring Lectureshttps://dmoj.ca/problem/cco18p5<div><h5>Canadian Computing Olympiad: 2018 Day 2, Problem 2</h5>
<p>You have a schedule of \(N\) upcoming lectures that you have the option of attending. The lectures are numbered from \(1\) to \(N\) and are in chronological order. From the current schedule, you expect that the \(i^{th}\) lecture will have quality \(a_i\). Since most of the lectures will be boring, you are only willing to attend some group of \(K\) consecutive lectures. You will skip the remaining lectures so that you can catch ...Sun, 20 May 2018 00:21:07 +0000https://dmoj.ca/problem/cco18p5CCO '18 P4 - Gradient Descenthttps://dmoj.ca/problem/cco18p4<div><h5>Canadian Computing Olympiad: 2018 Day 2, Problem 1</h5>
<p>Troy wants to play the following game with you.</p>
<p>He has a grid with \(R\) rows and \(C\) columns. Rows are numbered from \(1\) to \(R\) and columns are numbered from \(1\) to \(C\). Let the cell at row \(p\) and column \(q\) be denoted as \((p, q)\).</p>
<p>There are \(N\) tokens numbered from \(1\) to \(N\). Token \(i\) is placed at \((X_i, Y_i)\) where \(1\leq X_i\leq R\) and \(1\leq Y_i \leq C\). There may be multiple t...Sun, 20 May 2018 00:17:45 +0000https://dmoj.ca/problem/cco18p4CCO '18 P3 - Fun Palacehttps://dmoj.ca/problem/cco18p3<div><h5>Canadian Computing Olympiad: 2018 Day 1, Problem 3</h5>
<p>You are working hard to prepare a fun party for your fun friends. Fortunately, you have just located the perfect venue for your fun party: a <em>fun palace</em>. The fun palace has \(N\) <em>fun rooms</em> connected in a linear structure. The fun rooms are numbered from \(1\) to \(N\), and for \(1\leq i\leq N-1\), fun rooms \(i\) and \(i+1\) are connected by a <em>fun tunnel</em>. We say that such a fun tunnel is <em>incident</e...Sun, 20 May 2018 00:08:13 +0000https://dmoj.ca/problem/cco18p3CCO '18 P2 - Wrong Answerhttps://dmoj.ca/problem/cco18p2<div><h5>Canadian Computing Olympiad: 2018 Day 1, Problem 2</h5>
<p>Troy made the following problem (titled WA) for a programming contest:</p>
<blockquote><p>There is a game with \(N\) levels numbered from \(1\) to \(N\). There are two characters, both are initially at level 1. For \(i<j\), it costs \(A_{i,j}\) coins to move a character from level \(i\) to level \(j\). It is not allowed to move a character from level \(i\) to level \(j\) if \(i>j\). To win the game, every level (except lev...Sun, 20 May 2018 00:07:08 +0000https://dmoj.ca/problem/cco18p2CCO '18 P1 - Geese vs. Hawkshttps://dmoj.ca/problem/cco18p1<div><h5>Canadian Computing Olympiad: 2018 Day 1, Problem 1</h5>
<p>Troy and JP are big hockey fans. Every hockey team played \(N\) games this season. Each game was between two teams and the team that scored more points won. No game ended in a tie.</p>
<p>Troy's favourite team is the Waterloo Geese and he recorded the outcome of all their games as a string \(S\). \(S_i=\)<code>W</code> if the Geese won their \(i\)-th game; otherwise \(S_i=\)<code>L</code> if the Geese lost their \(i\)-th game. H...Sun, 20 May 2018 00:06:59 +0000https://dmoj.ca/problem/cco18p1ECOO '18 R2 P1 - Artificial Photosynthesystemhttps://dmoj.ca/problem/ecoo18r2p1<div><p>The technology world is currently working on a way to generate oxygen so that we can combat the effects of climate change. One of the ways that this is being done is through the creation of an artificial photosynthesystem.</p>
<p>the basic idea behind the process is that you need an artificial "leaf" and an artificial "fish" submerged into a vat of carbonated sugar water, which consists of sugar (\(S\)), water (\(W\)), oxygen (\(O\)), and carbon dioxide (\(C\)). The leaf is capable of ph...Sat, 12 May 2018 23:47:08 +0000https://dmoj.ca/problem/ecoo18r2p1ECOO '18 R2 P2 - Homeworkhttps://dmoj.ca/problem/ecoo18r2p2<div><p>George has procrastinated too much on his \(N\) homework assignments, and now he is running out of time to finish them all.</p>
<p>Each of George's \(N\) assignments has a weight that it contributes to his grade and a deadline in days from today. George will need one day to finish any of the assignments and he must complete an assignment before its deadline in order to submit it (he can't complete it the day an assignment is due).</p>
<p>Help George figure out the order in which he shoul...Sat, 12 May 2018 23:42:11 +0000https://dmoj.ca/problem/ecoo18r2p2ECOO '18 R2 P3 - Factorialhttps://dmoj.ca/problem/ecoo18r2p3<div><p>The factorial of a number \(N\), denoted as \(N!\), is equal to the product of all natural numbers up to and including \(N\). For example,</p>
<ul>
<li>\(1!=1\)</li>
<li>\(2!=1\times2=2\)</li>
<li>\(3!=1\times2\times3=6\)</li>
<li>\(4!=1\times2\times3\times4=24\)</li>
</ul>
<p>Given two numbers \(K\) and \(M\), what is the smallest value of \(N\) such that \(N!\) has at least \(M\) factors of \(K\) (that is, \(K^M\) divides evenly into \(N!\))?</p>
<h4>Input Specifications</h4>
<p>The st...Sat, 12 May 2018 23:38:05 +0000https://dmoj.ca/problem/ecoo18r2p3ECOO '18 R2 P4 - Three Squareshttps://dmoj.ca/problem/ecoo18r2p4<div><p>Given \(N\) distinct points on a 2D plane, you would like to place three identical, axis-aligned squares on the plane such that every point is either inside or on the border on one of the squares.</p>
<p>Let \(L\) be the side length of the squares. What is the minimum possible value of \(L\) such that all the points can be covered?</p>
<h4>Input Specifications</h4>
<p>The standard input will contain 10 datasets. Each dataset begins with an integer \(N\,(4\leq N\leq100\text{,}000)\). The ...Sat, 12 May 2018 23:37:18 +0000https://dmoj.ca/problem/ecoo18r2p4ECOO '18 R3 P4 - Circular Citieshttps://dmoj.ca/problem/ecoo18r3p4<div><p>In Ringworld, there are \(M\) cities numbered from \(1\) to \(M\) which lie uniformly spaced along a circular, two-way road. It takes one hour to travel between city \(i\) and city \(i+1\) for \(1\leq i\leq M\) and one hour to travel between city \(1\) and city \(M\).</p>
<p>Thre are \(N\) students and \(N\) teachers living in the cities. You would like to assign every teacher to a distinct student such that the sum of the times needed for each student to travel to their assigned teacher...Sat, 12 May 2018 23:29:13 +0000https://dmoj.ca/problem/ecoo18r3p4ECOO '18 R3 P2 - Vegenèrehttps://dmoj.ca/problem/ecoo18r3p2<div><p>The Vegenère cipher is a famous cipher which uses a keyboard to shift the value of each character of the message by some amount. For example, if the message is <code>HELLOWORLD</code>, and the keyword is <code>CODE</code>, then the Vegenère cipher first repeats the keyword until its the same length as the message, then encrypts the message by "adding" the two strings together:</p>
<pre><code> HELLOWORLD
+ CODECODECO
= KTPQRLSWOS</code></pre>
<p>To add the strings together, we "shift" e...Sat, 12 May 2018 23:09:14 +0000https://dmoj.ca/problem/ecoo18r3p2ECOO '18 R3 P1 - Balancedhttps://dmoj.ca/problem/ecoo18r3p1<div><p>Ms. Daisy teaches a class of \(B\) boys and \(G\) girls that need to line up every morning to take attendance. Ms. Daisy thinks that a line is "balanced" if at least one of the boys is equidistant from two of the girls in the line. For example, a <em>girl-boy-boy-girl</em> line is not balanced because both boys are closer to one of the girls, but a <em>girl-girl-boy-boy-girl</em> line is balanced because the first boy is equidistant from the first and last girls.</p>
<p>Ms. Daisy likes i...Sat, 12 May 2018 21:54:20 +0000https://dmoj.ca/problem/ecoo18r3p1Mock CCO '18 Contest 4 Problem 6 - Splitting Droneshttps://dmoj.ca/problem/ncco4d2p3<div><p>As we know, the art of splitting workers to separate mineral patches is a tricky one.</p>
<p>There are \(N\) mineral patches in order, each has \(A_i\) minerals to be mined. Our StarCraft player
will split \(L\) drones to mine \(L\) contiguous mineral patches.</p>
<p>The StarCraft player notes that for some values of \(L\), over the \(N-L+1\) ways to send drones to
mine minerals, the sequence of values corresponding to the mineral patches being mined is the same.</p>
<p>The StarCraft pla...Mon, 07 May 2018 04:33:08 +0000https://dmoj.ca/problem/ncco4d2p3Mock CCO '18 Contest 4 Problem 5 - Spawn More Overlordshttps://dmoj.ca/problem/ncco4d2p2<div><p>Richard has built a very large Zerg army. He has \(N\) different types of units in his army, specifically he has \(U_i\) units
that each provide \(S_i\) units of supply.</p>
<p>Due to a supply crunch, he must give away some of his units. He wishes to free up exactly \(T\) units of supply. He can do this by
sacrificing some of his existing units and spawning other units. He wants to minimize the sum of number of units he has to
sacrifice and number of units he has to spawn. Help him!</p>
...Mon, 07 May 2018 04:32:49 +0000https://dmoj.ca/problem/ncco4d2p2Mock CCO '18 Contest 4 Problem 4 - Time Travelhttps://dmoj.ca/problem/ncco4d2p1<div><p>A zergling is sent on a dangerous journey - as part of a 4-pool build, the zergling has to
run to the Protoss base to harass the mining probes.</p>
<p>On the way to the Protoss base, the zergling encounters some wormholes that teleport the zergling
to a different space and time. The zergling comes up with an ingenious idea - if she can return to the
Zerg main before she was born, then she could attack the Protoss base whenever she wanted to!</p>
<p>Can she?</p>
<p>Note that beforehand, t...Mon, 07 May 2018 04:32:32 +0000https://dmoj.ca/problem/ncco4d2p1Mock CCO '18 Contest 4 Problem 3 - Counterattackhttps://dmoj.ca/problem/ncco4d1p3<div><p>The Zerg, having held off the Protoss timing attack, is preparing to counterattack!
However, they don't wish to be all that obvious, so they will not take the shortest path
to the Protoss natural to counterattack. Instead, they will take the second-shortest path!
It is guaranteed there are at least two paths with distinct lengths.</p>
<p>To be clear about what this means, we model the map the Zerg is on as an undirected weighted graph.
Let \(L_1\) be the length of the shortest path from ...Mon, 07 May 2018 04:32:15 +0000https://dmoj.ca/problem/ncco4d1p3Mock CCO '18 Contest 4 Problem 2 - Sunken Colonieshttps://dmoj.ca/problem/ncco4d1p2<div><p>The incoming Protoss army just finished its +1 ground attack upgrade and zealot speed upgrade, and is
bearing down on the Zerg natural with a nasty timing attack.</p>
<p>The Zerg army has a bunch of creep colonies already built, and will convert some of them into sunken
colonies in an attempt at holding the attack. Due to the nature of the timing attack and limited resources,
the Zerg will refuse to convert creep colonies that are directly adjacent to each other.</p>
<p>The Zerg base is ...Mon, 07 May 2018 04:31:58 +0000https://dmoj.ca/problem/ncco4d1p2Mock CCO '18 Contest 4 Problem 1 - Mining for Mineralshttps://dmoj.ca/problem/ncco4d1p1<div><p>The Zerg army is working on mining more minerals. They have found a mineral patch of length \(L\).
They have a single drone who will mine the minerals.</p>
<p>This drone needs to divide this mineral patch into sections of length \(L_1\) through \(L_N\). The drone
can cut a mineral patch of length \(x\) into two mineral patches, one with length \(y\) and the other
with length \(x-y\). It will take the drone \(x\) seconds to perform one such cut. It is guaranteed
that \(\sum_{i=1}^N L_i = ...Mon, 07 May 2018 04:31:41 +0000https://dmoj.ca/problem/ncco4d1p1Dynamic Tree Testhttps://dmoj.ca/problem/ds5<div><p>Today, we'll be practicing modifications on a tree!</p>
<h4>Input</h4>
<p>The first line contains two integers, \(N\) and \(M\), denoting that there are \(N\) vertices and \(M\) queries.</p>
<p>Then there are \(N - 1\) lines, each line containing two integers \(x\) and \(y\), denoting that there is an edge between \(x\) and \(y\) in the tree.</p>
<p>Then there are \(N\) more lines, each containing one number: the initial weight of each vertex.</p>
<p>Then next line contains the root.</p>...Sat, 05 May 2018 21:56:52 +0000https://dmoj.ca/problem/ds5TLE '17 Contest 8 P6 - Willson and Nesting Seasonhttps://dmoj.ca/problem/tle17c8p6<div><div style="float:right; width:250px; padding: 10px 10px">
<img src="https://camo.algome.me/210a6cab82ee7d611837aae2bff26368ae8f6369/68747470733a2f2f692e696d6775722e636f6d2f78496e7831395a2e706e67" style="display: block; margin: 0 auto; width:100%;">
<div style="text-align:center;font-style:italic;margin-top:0.5em">Willson with his cute and fluffy baby geese.</div></div><p>Willson the Canada Goose is like any other Canada Goose - he now has several goslings (baby geese) to take care of!</p>
...Fri, 04 May 2018 04:22:32 +0000https://dmoj.ca/problem/tle17c8p6