Recently Added DMOJ Problemshttps://dmoj.ca/The latest problems added on the DMOJ: Modern Online Judge websiteenTue, 28 Jan 2020 23:17:43 +0000Link Cut Treehttps://dmoj.ca/problem/lct<div><p>Larry was playing with a link cut tree last night. He has made \(Q\) LCA queries to his link cut tree. Each time, the link cut tree responded with the integer representing the lowest common ancestor. He cut one too many edges and now he can't restore his tree. However, he will be satisfied with any tree that will give him the same results when asked the LCA queries again. Your task is to help him restore his tree. You will be given the \(Q\) queries, and the result of those queries.</p>
...Tue, 28 Jan 2020 23:17:43 +0000https://dmoj.ca/problem/lctFigurineshttps://dmoj.ca/problem/figurines<div><p>Riolku has \(N\) friends, labelled from \(1\) to \(N\). Him and his \(N\) friends recently got into collecting figurines! However, since their parents don't want them wasting all their money, they can only have two figurines at a time.</p>
<p>Each friend has one figurine that they consider "prized", and would never willingly give away, whereas they have another that they could trade, which we will call their "trade" figurine.</p>
<p>Being figurine connoisseurs, Riolku and his friends kno...Tue, 21 Jan 2020 18:06:38 +0000https://dmoj.ca/problem/figurinesJSB '19 - P4https://dmoj.ca/problem/jsb19p4<div><p>Please output the flag.</p>
<p>Download the Java agent <a href="https://dmoj.algome.me/data/jsb19/p4/p4_agent.jar" rel="nofollow">here</a>.</p>
<p>Download the source code of the agent <a href="https://dmoj.algome.me/data/jsb19/p4/p4_source.zip" rel="nofollow">here</a>.</p>
<p>You can test locally using the command <code>java -javaagent:p4_agent.jar YourClass</code>.</p>
<h4>Source Code</h4>
<h6>File: <code>Agent.java</code></h6>
<div class="codehilite"><pre><span></span><code><span clas...Tue, 07 Jan 2020 02:23:33 +0000https://dmoj.ca/problem/jsb19p4JSB '19 - P3https://dmoj.ca/problem/jsb19p3<div><p>Please call the method <code>flag()</code> in the class <code>Secret</code>.</p>
<p>Download the Java agent <a href="https://dmoj.algome.me/data/jsb19/p3/p3_agent.jar" rel="nofollow">here</a>.</p>
<p>Download the source code of the agent <a href="https://dmoj.algome.me/data/jsb19/p3/p3_source.zip" rel="nofollow">here</a>.</p>
<p>You can test locally using the command <code>java -javaagent:p3_agent.jar YourClass</code>.</p>
<h4>Source Code</h4>
<h6>File: <code>Agent.java</code></h6>
<div ...Tue, 07 Jan 2020 02:23:32 +0000https://dmoj.ca/problem/jsb19p3JSB '19 - P2https://dmoj.ca/problem/jsb19p2<div><p>Please call the method <code>flag()</code> in the class <code>Secret</code>.</p>
<p>Download the Java agent <a href="https://dmoj.algome.me/data/jsb19/p2/p2_agent.jar" rel="nofollow">here</a>.</p>
<p>Download the source code of the agent <a href="https://dmoj.algome.me/data/jsb19/p2/p2_source.zip" rel="nofollow">here</a>.</p>
<p>You can test locally using the command <code>java -javaagent:p2_agent.jar YourClass</code>.</p>
<h4>Source Code</h4>
<h6>File: <code>Agent.java</code></h6>
<div ...Tue, 07 Jan 2020 02:23:28 +0000https://dmoj.ca/problem/jsb19p2JSB '19 - P1https://dmoj.ca/problem/jsb19p1<div><p>Please call the method <code>flag()</code> in the class <code>Secret</code>.</p>
<p>Download the Java agent <a href="https://dmoj.algome.me/data/jsb19/p1/p1_agent.jar" rel="nofollow">here</a>.</p>
<p>Download the source code of the agent <a href="https://dmoj.algome.me/data/jsb19/p1/p1_source.zip" rel="nofollow">here</a>.</p>
<p>You can test locally using the command <code>java -javaagent:p1_agent.jar YourClass</code>.</p>
<h4>Source Code</h4>
<h6>File: <code>Agent.java</code></h6>
<div ...Tue, 07 Jan 2020 02:23:24 +0000https://dmoj.ca/problem/jsb19p1Bubble Cup V18 A Splitting Moneyhttps://dmoj.ca/problem/bbc18a<div><p>After finding and moving to the new planet that supports human life, discussions started on
which currency should be used. After long negotiations, Bitcoin was ultimately chosen as the
universal currency.</p>
<p>These were the great news for Alice, whose grandfather got into Bitcoin mining in 2013, and
accumulated a lot of them throughout the years. Unfortunately, when paying something in
bitcoin everyone can see how many bitcoins you have in your public address wallet.</p>
<p>This worri...Sun, 05 Jan 2020 15:57:35 +0000https://dmoj.ca/problem/bbc18aString Finding (Python 3 Version)https://dmoj.ca/problem/bf5<div><p>To celebrate Python 2's death, Roger challenges you to find all occurrences of a string \(T\) in \(S\). Of course, you may only use Python 3.</p>
<h4>Input Specification</h4>
<p>The first line contains a string \(S\).</p>
<p>The second line contains a string \(T\).</p>
<p>Both strings will only contain lowercase letters. You may assume \(1 \le |T| \le |S| \le 10^6\).</p>
<h4>Output Specification</h4>
<p>Let \(A\) be the sum of all 1-indexed occurrences of \(T\) in \(S\) and let \(B\) be ...Wed, 01 Jan 2020 09:38:25 +0000https://dmoj.ca/problem/bf5Strict Evaluationhttps://dmoj.ca/problem/lazy<div><p>You have an array of \(N\) \((1 \le N \le 100\,000)\) elements, indexed from \(1\) to \(N\). There are \(Q\) \((1 \le Q \le 100\,000)\) operations you need to perform on it.</p>
<p>Each operation is one of the following:</p>
<ul>
<li><code>1 l r v</code> Increment each value in the range \([l,r]\) by \(v\).</li>
<li><code>2 l r v</code> Make each value in the range \([l,r]\) equal to \(v\) (i.e. for each element \(a_i\), such that \(l \leq i \leq r\), set \(a_i:=v\)).</li>
<li><code>3 l ...Wed, 01 Jan 2020 06:47:33 +0000https://dmoj.ca/problem/lazyWesley's Anger Contest 1 Problem 4 (Hard Version) - A Red-Black Tree Problemhttps://dmoj.ca/problem/wac1p4hard<div><p>It is well known that Wesley is bad at dynamic programming. Six months after the <a href="https://dmoj.ca/contest/wac1">contest</a>, Wesley learned that you can solve the <a href="https://dmoj.ca/problem/wac1p4">original problem</a> with a significantly better time complexity. He decided to create a new problem with tighter contraints. <strong>The only differences between this problem and the original are the bounds on \(N\) and \(K\), as well as the time and memory limits. In addition, ...Sat, 28 Dec 2019 15:22:36 +0000https://dmoj.ca/problem/wac1p4hard2-Dimensional Range Minimum Queryhttps://dmoj.ca/problem/2drmq<div><p>You are given a \(2\)-dimensional array of integers of size \(N \times N\). We will call this array \(arr\). You are then required to answer multiple queries for the minimum integer in a given submatrix.</p>
<p>Formally, given \(4\) integers \(a, b, c, d\), determine \(\min{\{ arr[i][j] \ | \ a \le i \le b, c \le j \le d \}}\).</p>
<h4>Implementation Details</h4>
<p>You should implement the following functions:</p>
<pre><code>void init(std::vector<std::vector<int>> arr);</co...Wed, 25 Dec 2019 13:34:12 +0000https://dmoj.ca/problem/2drmqDMOPC '19 Contest 4 P4 - Math Classhttps://dmoj.ca/problem/dmopc19c4p4<div><p>Veshy is taking a class in linear algebra! He comes across a problem about the rotations of points with respect to the origin. However, he deems this too trivial so he comes up with the following problem instead:</p>
<blockquote><p>Veshy chooses two points located at integer coordinates, \(A\) and \(B\), on the 2D plane. There is initially a token at \(A\). Veshy also has a sequence of \(N\) points, all located at integer coordinates, on this plane, \(a_1, a_2, \ldots , a_N\). One operat...Wed, 25 Dec 2019 01:41:12 +0000https://dmoj.ca/problem/dmopc19c4p4DMOPC '19 Contest 4 P5 - Financial Troublehttps://dmoj.ca/problem/dmopc19c4p5<div><p>After days of reckless spending, Zawaex has found himself in some deep trouble, and is close to going into debt. He currently has \(M\) dollars left and he finds a list of \(N\) events that he had predicted would happen to him over the next few days. The \(i\)th event can be characterized by a single integer \(d_i\), the amount of money in dollars that he would gain from it. (If \(d_i\) was negative, he would instead lose money). If Zawaex's amount of money were to become negative after ...Tue, 24 Dec 2019 19:51:52 +0000https://dmoj.ca/problem/dmopc19c4p5DMOPC ‘19 Contest 4 P1 - Valid Stringshttps://dmoj.ca/problem/dmopc19c4p1<div><p>Veshy is entering strings into his calculator consisting of only <code>(</code>, <code>)</code>, and decimal digits; however, some strings are invalid and produce an error.</p>
<p>A valid string must either be:</p>
<ol>
<li>Nothing (an empty string).</li>
<li>A non-negative integer expressed in decimal digits (e.g. <code>5</code>, <code>230</code>, <code>0032</code>), optionally followed by another valid string.</li>
<li>A pair of brackets enclosing a valid string (e.g. <code>(5)</code>)...Tue, 24 Dec 2019 17:12:36 +0000https://dmoj.ca/problem/dmopc19c4p1DMOPC '19 Contest 4 P3 - Taking Cueshttps://dmoj.ca/problem/dmopc19c4p3<div><p>Veshy has been playing too much 8-ball pool recently, so to cure his addiction, he has turned to collecting pool cue balls instead. While looking into the market for cue balls, he realizes that there is a lot of money to be made. Each month, he can buy and sell a maximum of \(X_i\) and \(Y_i\) cue balls at a price of \(b_i\) and \(s_i\) respectively for each month \(m_i\). Cue balls, being very valuable, also cost \(M\) maintenance (per held cue ball) to upkeep per month. Being Veshy's b...Tue, 24 Dec 2019 07:22:51 +0000https://dmoj.ca/problem/dmopc19c4p3A Sum Problemhttps://dmoj.ca/problem/asumproblem<div><p>At school, Max is learning how to add numbers together! He finds the task of adding numbers too easy, so he gives you the following problem: sum an array of \(N\) (\(1 \leq N \leq 5 \cdot 10^4\)) integers (\(0 \leq a_i \leq 10^7\)), <em>without looking at the array</em>. Instead, you're only allowed to ask the following question: "How many numbers in the array are greater than or equal to \(k\)?" Because he is impatient, Max says you can only ask up to \(5 \cdot 10^5\) questions.</p>
<h4...Tue, 24 Dec 2019 04:30:26 +0000https://dmoj.ca/problem/asumproblemClassified!https://dmoj.ca/problem/classified<div><p>Ben was having a great time <del>self-advertising</del> playing his own game, <strong>Classified</strong>, when he suddenly encountered a strange bug which caused him to somehow lose. After months of interrogation, he soon realized that the cause of his loss was not a bug, but simply him being bad at his own game. Since Ben was so tired of losing over, and over, and over again, he has asked YOU to perform this task for him - Create a program which will output the highest amount of damage...Fri, 20 Dec 2019 18:19:35 +0000https://dmoj.ca/problem/classifiedAPIO '08 P2 - Roadshttps://dmoj.ca/problem/apio08p2<div><p>The Kingdom of New Asia contains \(N\) villages connected by \(M\) roads. Some roads are made of
cobblestones, and others are made of concrete. Keeping roads free-of-charge needs a lot of money, and
it seems impossible for the Kingdom to maintain every road. A new road maintaining plan is needed.</p>
<p>The King has decided that the Kingdom will keep as few free roads as possible, but every two
distinct villages must be connected by <em>one and only one</em> path of free roads. Also, alt...Wed, 11 Dec 2019 01:54:58 +0000https://dmoj.ca/problem/apio08p2GlobeX Cup '19 S5 - Alien Navigationhttps://dmoj.ca/problem/globexcup19s5<div><p>There are \(N\) non-moving planets in the galaxy and can be represented as a 3D coordinate. Each planet is colonized by one and only one of the \(K\) alien colonies that exist in the galaxy. The tension between the colonies is high, so recently, the god of the galaxy decided to hold a meeting at the center of the galaxy \((0, 0, 0)\). As a result, each <strong>colony</strong> must send one and only one alien representative to the meeting.</p>
<p>To get to the center of the galaxy, the al...Mon, 09 Dec 2019 00:53:35 +0000https://dmoj.ca/problem/globexcup19s5GlobeX Cup '19 S4 - Ninjaclasher's Wrath 2https://dmoj.ca/problem/globexcup19s4<div><p>You may have heard of "spooky action at a distance", or you may have not. It doesn't matter. There exists a line of \(N\) particles, of which the \(i^\text{th}\) particle and the \(N-i+1^\text{th}\) particle are quantum entangled. <em>Note that what is described in this problem is not how quantum entanglement really works</em>. Each particle has an electric charge \(e_i\). You happen to know the electric charges of all \(N\) particles in order.</p>
<p>When you look at a particle \(i\), d...Mon, 09 Dec 2019 00:53:23 +0000https://dmoj.ca/problem/globexcup19s4GlobeX Cup '19 S3 - Ninjaclasher's Wrathhttps://dmoj.ca/problem/globexcup19s3<div><p>You are going on vacation to your local group of exoplanets. In this group, there are \(N\) exoplanets lined up in a row. Each exoplanet is an ellipse, consisting of a vertical radius of \(h_i\) kilometres and a horizontal radius that is infinitesimal. The \(i^\text{th}\) exoplanet is \(d_i\) kilometres away from the \(i+1^\text{th}\) exoplanet.</p>
<p>You plan to travel to each exoplanet, starting with exoplanet \(1\). On each one, you will stand at the very "top" of the exoplanet, and ...Mon, 09 Dec 2019 00:53:15 +0000https://dmoj.ca/problem/globexcup19s3GlobeX Cup '19 S2 - Predicting Collisionshttps://dmoj.ca/problem/globexcup19s2<div><p>The intergalactic war has started! Willie lives in a war zone and he is a soldier who wants to protect his planet. The planet's peacekeepers have gathered intel on the immediate missile launch that may affect Willie's city. This missile launch is composed of two advanced projectiles. There is a secret operation in the planet that Willie lives in. The operation involves extremely reactive substances that may destroy the planet if the two projectiles collide within a specific area. Willie ...Mon, 09 Dec 2019 00:52:41 +0000https://dmoj.ca/problem/globexcup19s2GlobeX Cup '19 S1 - Planet Classificationhttps://dmoj.ca/problem/globexcup19s1<div><p>Andy is travelling through the galaxy. His mission is to categorize the planets that he passes. There are \(K\) types of planets. He passes by \(N\) different planets. Each of these planets can be classified as one of these \(K\) types. You would like to help Andy on his mission by programming a computer assistant for him. Whenever he passes a planet, he will tell the assistant the type of this planet. The assistant must then tell him how many previous planets are of this type. At the en...Mon, 09 Dec 2019 00:52:22 +0000https://dmoj.ca/problem/globexcup19s1GlobeX Cup '19 J5 - Alienshttps://dmoj.ca/problem/globexcup19j5hard<div><p>Scientists are constantly listening for aliens. Because of the great distances, some things may come more delayed than others. Thus they need an algorithm that when given two strings, \(a\), and \(b\) \((2 \leq |a|, |b| \leq 1000\), where \(|a| = |b|)\), determines whether it is possible to make \(b\) by taking a single substring of \(a\) and moving it to another index. It should also detect aliens when the two strings are the same.</p>
<p><strong>Note: The constraints and data have chan...Mon, 09 Dec 2019 00:52:02 +0000https://dmoj.ca/problem/globexcup19j5hardGlobeX Cup '19 J4 - Winni's Lonely Card Gamehttps://dmoj.ca/problem/globexcup19j4<div><p>Winni is playing a card game with herself since she lost all of her friends when travelling to outer space. Winni lays \(N\) cards face up on the table. Each card has a non-unique number on it from \(1\) to \(M\). Winni proceeds to pick up \(K\) cards from the table one at a time. Whenever Winni picks up a card, she recieves \(O\) dollars where \(O\) is the number of cards with the same number that she has already picked up. Can you help Winni determine the maximum amount of money she ca...Mon, 09 Dec 2019 00:51:45 +0000https://dmoj.ca/problem/globexcup19j4