Recently Added DMOJ Problemshttps://dmoj.ca/The latest problems added on the DMOJ: Modern Online Judge websiteenMon, 17 Dec 2018 00:46:11 +0000Creating a Sequencehttps://dmoj.ca/problem/seq3<div><p>Kirito is tired of <a href="/problem/seq2">maintaining sequences</a>, so he decides to create them instead!</p>
<p>He thinks of two positive integers, \(N\) and \(K\), and then creates a sequence of \(N\) non-negative integers that sums to \(K\).</p>
<p>Because he finds this so relaxing, he invites you to join him! However, you find this just <em>a bit</em> boring, so you decide to also <strong>minimize the product of your sequence</strong>. Can you write a program that creates such a se...Mon, 17 Dec 2018 00:46:11 +0000https://dmoj.ca/problem/seq3Expected Valuehttps://dmoj.ca/problem/expectedvalue<div><p>Shinmyoumaru has gotten out of bed and needs to go fetch the Miracle Mallet. To do this, she needs
to travel from the top-left corner of an \(N \times N\) grid to the bottom-right corner.</p>
<p>With probability \(p\), Shinmyoumaru will be facing to the right, and with probability \(1-p\),
she will be facing down. She will take a single step, and then with probability \(p\), she will
swap the direction she is facing from either right to down, or from down to right. If her next
step would...Sat, 15 Dec 2018 02:23:58 +0000https://dmoj.ca/problem/expectedvalueDMOPC '18 Contest 4 P2 - Dr. Henri and Responsibilityhttps://dmoj.ca/problem/dmopc18c4p2<div><p>Dr. Henri is a very busy person. He has \(N\) responsibilities to attend to over the next two days. Being a very organized person, he wants to split the tasks evenly between the two days. More specifically, if the tasks on day 1 take \(t_1\) seconds, and the tasks on day 2 take \(t_2\) seconds, he wants to minimize the value of \(|t_1 - t_2|\).</p>
<p>The \(i^{\text{th}}\) task takes him \(A_i\) seconds, and <strong>must be completed within a single day</strong>. Dr. Henri, being very bu...Mon, 10 Dec 2018 17:06:32 +0000https://dmoj.ca/problem/dmopc18c4p2DMOPC '18 Contest 4 P0 - Dr. Henri and Seeing Starshttps://dmoj.ca/problem/dmopc18c4p0<div><p>Dr. Henri is looking through his telescope at the MRD Observatory. His telescope is positioned so that it can see all the stars inside a circle of radius \(R\) centred at the coordinates \((X, Y)\) in the night sky. The telescope <strong>cannot</strong> see a star if it is on the edge of the circle.</p>
<p>Dr. Henri is interested in 3 particular stars: \(A\), \(B\), and \(C\). Referring to his star charts, he notes that their coordinates are \((x_A, y_A)\), \((x_B, y_B)\), and \((x_C, y_...Thu, 06 Dec 2018 17:48:47 +0000https://dmoj.ca/problem/dmopc18c4p0DMOPC '18 Contest 4 P4 - Dr. Henri and Lab Datahttps://dmoj.ca/problem/dmopc18c4p4<div><p>Dr. Henri is working on a new method of analyzing lab data! He has collected \(N\) data points: \(A_1, A_2, A_3, \ldots A_N\), and has defined the \(k-\textbf{interest}\) of a subarray as the sum of all numbers greater than or equal to \(k\) minus the sum of all numbers less than \(k\).</p>
<p>For example, the \(5-\text{interest}\) of the array \([4, 2, 6, 5, 1]\) is \((6 + 5) - (4 + 2 + 1) = 4\).</p>
<p>Dr. Henri knows that some of the data might be outliers, so he asks you \(Q\) querie...Thu, 06 Dec 2018 16:55:25 +0000https://dmoj.ca/problem/dmopc18c4p4DMOPC '18 Contest 4 P1 - Dr. Henri and Differential Photometryhttps://dmoj.ca/problem/dmopc18c4p1<div><p>Dr. Henri is looking through his telescope at the MRD Observatory. He is observing a certain star \(Y\) and wants to find its <strong>magnitude</strong> (a measure of brightness), \(m_Y\). The magnitude of a star can be any real number.</p>
<p>Dr. Henri is using a device called a <strong>differential photometer</strong> to measure magnitude. Although this device is very precise, it cannot directly measure the magnitude of a star; it can only measure the <strong>difference in magnitudes</...Thu, 06 Dec 2018 16:16:58 +0000https://dmoj.ca/problem/dmopc18c4p1Another Contest 3 Problem 4 - Range Updates and Range Querieshttps://dmoj.ca/problem/acc3p4<div><p>You have an array of \(N\) integers, initialized all to zero to begin with. Support two operations.</p>
<p><code>INCREMENT l r a</code> - For each index \(i\) between \(l\) and \(r\), increase the \(i\)th element of the array by \(a \cdot (i-l+1)\).</p>
<p><code>SUM l r</code> - Compute the sum of the integers between indices \(l\) and \(r\), inclusive.</p>
<h4>Constraints</h4>
<p>\(1 \le N \le 10^6\)</p>
<p>\(1 \le Q \le 10^5\)</p>
<p>\(1 \le l_i \le r_i \le N\)</p>
<p>\(1 \le a_i \le 5...Tue, 27 Nov 2018 05:00:04 +0000https://dmoj.ca/problem/acc3p4Another Contest 3 Problem 3 - Lexicographically Largest Common Subsequencehttps://dmoj.ca/problem/acc3p3<div><p>Given \(N\) strings of lowercase letters, compute the lexicographically largest string that is a
subsequence of all \(N\) strings.</p>
<p>String \(s\) is a subsequence of string \(t\) if \(s\) can be obtained by deleting some of the letters in \(t\).
It is not required to delete any letters.</p>
<p>String \(s\) is lexicographically larger than \(t\) if \(t\) is a prefix of \(s\) or, given that index \(i\) is the first
mismatch in strings \(s\) and \(t\), the \(i\)th character of \(s\) i...Tue, 27 Nov 2018 05:00:03 +0000https://dmoj.ca/problem/acc3p3Another Contest 3 Problem 2 - Camelothttps://dmoj.ca/problem/acc3p2<div><p>In the game of chess, a king can move horizontally, vertically, or diagonally by one unit.
More specifically, if a king is at \((x, y)\), their \(x\)-coordinate can change by at most one
and their \(y\)-coordinate can change by at most one in a single move.</p>
<p>There are \(N\) kings on an infinite chessboard where each square can fit an infinite
number of kings, and they wish to meet up at a single location. In one second, exactly one king
can move by one unit - all other kings must s...Tue, 27 Nov 2018 05:00:02 +0000https://dmoj.ca/problem/acc3p2Another Contest 3 Problem 1 - Diverse Arrayshttps://dmoj.ca/problem/acc3p1<div><p>Call an array of integers <em>diverse</em> if it has length at least 1 and it has at least \(K\) distinct integers.</p>
<p>Given an array of \(N\) integers and a parameter \(K\), compute the number of subarrays that are diverse.</p>
<h4>Constraints</h4>
<p>\(1 \le K \le N \le 10^6\)</p>
<p>\(1 \le a_i \le N\)</p>
<h4>Input Specification</h4>
<p>The first line contains two positive integers, \(N\) and \(K\).</p>
<p>Each of the next \(N\) lines contains a positive integer, \(a_i\). These i...Tue, 27 Nov 2018 05:00:01 +0000https://dmoj.ca/problem/acc3p1COCI '17 Contest 1 #4 Hokejhttps://dmoj.ca/problem/coci17c1p4<div><p>The date of a major marathon ice hockey tournament is approaching. As it is often the case in marathon ice hockey, the game is \(M\) minutes long. On the field (ice) are, as in regular ice hockey, at each given moment, <strong>six players</strong> from each team. However, a game of marathon ice hockey can last a very long time, so the coaches brought a bunch of players in buses and planes so they can perform substitutions when the players get tired.</p>
<p>One of the coaches is the hero ...Wed, 21 Nov 2018 17:25:14 +0000https://dmoj.ca/problem/coci17c1p4COCI '17 Contest 1 #3 Lozinkehttps://dmoj.ca/problem/coci17c1p3<div><p>Recently, there has been a breach of user information from the mega-popular social network <em>Secret Network</em>. Among the confidential information are the passwords of all users.</p>
<p>Mihael, a young student who has been exploring computer security lately, found the whole thing really interesting. While experimenting with the social network, he found another security breach! When you input any string of characters that contains a substring equal to the actual password, the login wi...Wed, 21 Nov 2018 03:47:28 +0000https://dmoj.ca/problem/coci17c1p3Another Contest 2 Problem 3 - Poutinehttps://dmoj.ca/problem/acc2p3<div><p>Fast Fingers Thomas is delivering poutine to Wilson's restaurants!</p>
<p>Fast Fingers Thomas will drive a truck on a weighted tree with \(N\) vertices.</p>
<p>Each trip has two parameters, a source vertex \(s_i\) and a destination vertex \(t_i\). Thomas does not like driving along long edges, so he seeks to minimize the length
of the second-longest edge that he travels on. Formally, if the weights of the edges that Thomas traverses are \(W_1, \dots, W_K\) in nondecreasing order, he seek...Wed, 14 Nov 2018 06:15:02 +0000https://dmoj.ca/problem/acc2p3Another Contest 2 Problem 2 - Poutinehttps://dmoj.ca/problem/acc2p2<div><p>Fast Fingers Thomas has just finished conducting an tryout for a poutine-eating contest, and needs to produce a ranklist. However,
the scoreboard has crashed and the rankings are lost! Individual \(i\) beat individual \(j\) if individual \(i\) ate more poutine
than individual \(j\). He vaguely remembers that some individuals ate more poutine than other individuals, but might not have enough data to fully
reconstruct the ranklist. He does remember that there were no ties in the contest.</...Wed, 14 Nov 2018 06:13:50 +0000https://dmoj.ca/problem/acc2p2Another Contest 2 Problem 1 - Poutinehttps://dmoj.ca/problem/acc2p1<div><p>Fast Fingers Thomas is delivering poutine to Wilson's restaurants!</p>
<p>Fast Fingers Thomas will drive a truck on a directed, weighted graph with \(N\) vertices. The weight of each edge in the graph is the length of the edge. He has \(Q\) trips he needs to make.</p>
<p>Each trip has three parameters, a source vertex \(s_i\), a destination vertex \(t_i\), and a number of days \(d_i\). Thomas has \(d_i\) days to travel
from vertex \(s_i\) to vertex \(t_i\). In a given day, Thomas starts ...Wed, 14 Nov 2018 06:13:07 +0000https://dmoj.ca/problem/acc2p1DMOPC '18 Contest 3 P3 - Bob and Math Classhttps://dmoj.ca/problem/dmopc18c3p3<div><p>Bob has a pop quiz in math! Fortunately, it's only a true and false quiz. He has already finished and is checking over his answers to the \(N\) questions. His answers are a string of \(N\) <code>T</code>s and <code>F</code>s. Bob calls an array <em>suspicious</em> if it contains a subarray of only <code>T</code>s or only <code>F</code>s such that the length of the subarray is at least half of the length of the entire array. For example, <code>TTTTFTF</code> is a suspicious subarray since...Mon, 12 Nov 2018 17:12:58 +0000https://dmoj.ca/problem/dmopc18c3p3DMOPC '18 Contest 3 P2 - Bob and French Classhttps://dmoj.ca/problem/dmopc18c3p2<div><p>Bob has to write an essay for French class! He has already written it in English. All that's left is for him to translate it to French. Unfortunately, he is <em title="very bad">très mal</em> at French, and needs to rely on Google Translate to write his essay.</p>
<p>His French teacher is well aware of this, and will know that Bob used Google Translate if any 3 consecutive words are in French.</p>
<p>Bob is very clever, and has stolen the marking scheme, which states that the \(i^{\text{...Mon, 12 Nov 2018 01:11:27 +0000https://dmoj.ca/problem/dmopc18c3p2GlobeX Cup '18 S Sample - Chair Stackinghttps://dmoj.ca/problem/globexcup18s0<div><p>Junya has just finished her trigonometry test. Her teacher asks her kindly to move the chairs into one stack at some location in the \(10^9 \times 10^9\) metre classroom. However, her teacher only wants her to move the chairs either along the \(x\) axis or the \(y\) axis of the classroom. That is, she is <strong>not</strong> allowed to move the chair diagonally. Additionally, because she is not that strong, she can only move one chair at a time. For each metre she pushes the chair, it ta...Sun, 11 Nov 2018 17:47:40 +0000https://dmoj.ca/problem/globexcup18s0GlobeX Cup '18 J Sample - Farming Simulatorhttps://dmoj.ca/problem/globexcup18j0<div><p>Farmer Yunji owns \(N\) farms. Each farm produces \(X_i\) dollars per day. Due to tax issues, he has to sell \(M\) of his farms. What is the maximum amount of money he can earn per day from his farms, after he sells \(M\) of them?</p>
<h4>Input Specification</h4>
<p>The first line will contain two space-separated integers, \(N, M\ (1 \le M \le N \le 10^5)\), the number of farms, and the number of farms Yunji has to sell, respectively.</p>
<p>The next line will contain \(N\) integers, \(X...Sun, 11 Nov 2018 17:47:32 +0000https://dmoj.ca/problem/globexcup18j0DMOPC '18 Contest 4 P5 - Dr. Henri and Wormholeshttps://dmoj.ca/problem/dmopc18c4p5<div><p>Dr. Henri has recently been studying <strong>wormholes</strong>, tunnels in the fabric of spacetime. A wormhole connects two different galaxies, may be traversed in either direction, and allows one to travel between the two galaxies in mere minutes. Wormholes are very rare and contain all sorts of exotic matter.</p>
<p>One day, Dr. Henri and his team discover a cluster of \(N\) galaxies connected by \(N - 1\) wormholes! Wormhole \(i\) connects galaxies \(a_i\) and \(b_i\) and takes \(t_i...Sat, 10 Nov 2018 14:12:23 +0000https://dmoj.ca/problem/dmopc18c4p5DMOPC '18 Contest 3 P1 - Bob and Music Classhttps://dmoj.ca/problem/dmopc18c3p1<div><p>Bob is studying for his music theory exam and needs your help!</p>
<p>In music, there are 12 distinct <strong>tones</strong>. They are named, in ascending order, <code>A, A#, B, C, C#, D, D#, E, F, F#, G,</code> and <code>G#</code>. (Note that there is no <code>B#</code> or <code>E#</code>.) After <code>G#</code>, the sequence cycles back to <code>A</code> and repeats. The distance between two adjacent tones is one <strong>semitone</strong>.</p>
<p>The <strong>interval</strong> between t...Fri, 09 Nov 2018 16:22:53 +0000https://dmoj.ca/problem/dmopc18c3p1DMOPC '18 Contest 3 P0 - Bob and ICS Classhttps://dmoj.ca/problem/dmopc18c3p0<div><p>Bob is trying to live-stream a video in his ICS class! He's learned that colours are represented by a triple \((R, G, B)\), where \(R\) is the intensity of red, \(G\) is the intensity of green, and \(B\) is the intensity of blue.
He knows that humans don't perceive the higher end of the spectrum well, so the data can be compressed into \((\lfloor\sqrt R\rfloor, \lfloor\sqrt G\rfloor, \lfloor\sqrt B\rfloor)\), where \(\lfloor x \rfloor\) is the largest integer less than or equal to \(x\),...Fri, 09 Nov 2018 06:28:48 +0000https://dmoj.ca/problem/dmopc18c3p0DMOPC '18 Contest 3 P4 - Bob and English Classhttps://dmoj.ca/problem/dmopc18c3p4<div><p>Bob's English class has been given a project which must be done in pairs. The class size, \(K\), is even. Each pair needs to meet outside class to do the project.</p>
<p>The city which Bob and his classmates live in is a tree. It has \(N\) zones labelled \(1, 2, \ldots, N\). There are \(N-1\) roads so that one can travel from any zone to any other. The \(i^{\text{th}}\) road connects zones \(a_i\) and \(b_i\) and has distance \(d_i\).</p>
<p>The \(i^{\text{th}}\) student lives in zone \(...Sat, 03 Nov 2018 20:49:40 +0000https://dmoj.ca/problem/dmopc18c3p4COCI '17 Contest 1 #1 Cezarhttps://dmoj.ca/problem/coci17c1p1<div><p>Little Caesar likes card games. Everytime he comes to Zagreb, he plays blackjack, the famous card game, with his friends.</p>
<p>In this game, the player draws cards while the sum of the cards in his hand is less than or equal to \(21\) or until he says <code>DOSTA</code> (Croatian for “STOP”).</p>
<p>At the beginning of the game, there are \(52\) cards in the deck, thirteen ranks of each of the four suits. The card ranks are two, three, …, ten, Jack, Queen, King and Ace. The card values...Tue, 30 Oct 2018 15:52:09 +0000https://dmoj.ca/problem/coci17c1p1Ternary Search Treehttps://dmoj.ca/problem/ternarysearchtree<div><p>Antonio likes top trees, and hates all other types of trees. One day, his algorithms professor gives him an assignment to build a ternary search tree. The algorithm for building a ternary search tree is as follows:</p>
<p>A ternary search tree has a root node, and each node has three children, a left child, a middle child, and a right child. Each node also has an integer key associated with it. To insert a node with a given key into the tree, check if the given key is less than, equal to...Sat, 27 Oct 2018 05:28:12 +0000https://dmoj.ca/problem/ternarysearchtree