Recently added DMOJ problemshttps://dmoj.ca/The latest problems added on the DMOJ: Modern Online Judge websiteen-caMon, 22 May 2017 13:10:01 +0000DMPG '17 G4 - Timelinehttps://dmoj.ca/problem/dmpg17g4<html><head><style>
@media print {
#cancer-spacer { height: 5em; display: block; }
}
</style></head><body><p>Harold is, like the rest of his coworkers, working hard to ensure all records are "accurate". To do this they must change some labels here and there, but more importantly, change the time that certain events occurred... in the database.</p>
<p>Unfortunately for you, many students are looking up "information" for their projects at the same time, and all the queries are grouped together...Mon, 22 May 2017 13:10:01 +0000https://dmoj.ca/problem/dmpg17g4DMPG '17 G1 - FatalWhale and Candieshttps://dmoj.ca/problem/dmpg17g1<html><head><style>
@media print {
#cancer-spacer { height: 5em; }
}
</style></head><body><p>Molly is trying to steal some candy from her best friend FatalWhale. Unfortunately, FatalWhale is very organized and will immediately notice if the total sweetness of candies Molly takes is not a multiple of \(P\). Help Molly determine which candies out of the \(N\) FatalWhale has in order to take the maximum sweetness!</p>
<h4>Constraints</h4>
<ul>
<li>\(N, P \le 4096\)</li>
<li>You will receive \(2...Mon, 22 May 2017 13:09:23 +0000https://dmoj.ca/problem/dmpg17g1DMPG '17 G2 - Holy Grail Warhttps://dmoj.ca/problem/dmpg17g2<div><p>Arthuria is preparing to fight Gilgamesh for the Holy Grail! Unfortunately, Gilgamesh activates his Noble Phantasm, <em>Gate of Babylon</em>, and summons \(N\) swords, and the \(i^{th}\) has destructive power \(d_i\). Luckily for Arthuria, her Noble Phantasm, <em>Excalibur</em>, is capable of destroying any contiguous subsequence of Gilgamesh's swords. As such, Arthuria gives you \(Q\) queries of two possible forms:</p>
<ol>
<li><code>S i x</code>: Gilgamesh swaps out the \(i^{th}\) swor...Tue, 16 May 2017 21:51:55 +0000https://dmoj.ca/problem/dmpg17g2DMPG '17 S6 - Brackets, Braces, and Boxeshttps://dmoj.ca/problem/dmpg17s6<div><p>Molly was experimenting with bracket strings, when she made a mistake and accidentally changed some of the characters. Now, she needs your help to fix her bracket sequence.</p>
<p>To begin, here are Molly's definitions:</p>
<ul>
<li>A bracket string consists of the following six symbols: <code>()[]{}</code>. The characters <code>([{</code> are considered left brackets, and <code>)]}</code> are considered right brackets.</li>
<li>There are three distinct matching pairs: <code>()</code>, <...Tue, 16 May 2017 21:51:10 +0000https://dmoj.ca/problem/dmpg17s6DMPG '17 S5 - Bit Matrixhttps://dmoj.ca/problem/dmpg17s5<div><p>Ruby likes binary numbers. She also likes matrices. Therefore, she definitely likes matrices filled with binary numbers!</p>
<p>After thinking about them for a while, she comes up with an interesting question:</p>
<blockquote><p>Given integers \(N\) and \(M\), find an \(N\times M\) matrix of distinct numbers, where each number in the matrix differs by exactly one bit from its adjacent (up, down, left, right) numbers in the matrix.</p>
</blockquote>
<p>Since Ruby knows you like matrices a...Tue, 16 May 2017 21:50:58 +0000https://dmoj.ca/problem/dmpg17s5DMPG '17 S4 - Artillery Batteryhttps://dmoj.ca/problem/dmpg17s4<div><p>One sunny afternoon, you find yourself in your Geography class watching your teacher Mr. Singh play against a fellow classmate.</p>
<p>Instead of studying for your exams, you decide to visualize the maximum number \(p\), out of the \(E\) opposing pieces Mr. Singh would be able to capture using just his Cannon. You have also decided to find the minimum number of legal moves \(m\) required to accomplish such a feat.</p>
<p>Since everybody plays this board game in their spare time, it is co...Tue, 16 May 2017 21:50:57 +0000https://dmoj.ca/problem/dmpg17s4DMPG '17 S3 - Black and White IIIhttps://dmoj.ca/problem/dmpg17s3<div><p>Ruby is playing with the board from a board game.</p>
<p>The board has \(2^N\times 2^N\) cells, originally coloured some assortment of black and white. Ruby takes this board and folds it a number of times, once on the middle vertical axis followed by once on the middle horizontal axis, resulting in a board of size \(2^{N-1}\times 2^{N-1}\). When she folds on the vertical, she always keeps the left side stationary, and folds the right half onto it. She does the same for horizontal folds, ...Tue, 16 May 2017 21:50:31 +0000https://dmoj.ca/problem/dmpg17s3DMPG '17 S2 - Anime Conventionshttps://dmoj.ca/problem/dmpg17s2<div><p>In the distant land of yore, there lived a weeb king. As a weeb king, he valued anime above all else including roads. And so it came to be that, when it came time to go to the anime conventions, he realised his folly: <strong>there were no roads in his kingdom, whatsoever</strong>! Angered, he went to his chief adviser (you) and asked them to simulate \(Q\) actions:</p>
<ul>
<li><code>A x y</code>: Build a road between cities \(x\) and \(y\). </li>
<li><code>Q x y</code>: Check if citie...Tue, 16 May 2017 21:50:12 +0000https://dmoj.ca/problem/dmpg17s2DMPG '17 S1 - Molly and Differencehttps://dmoj.ca/problem/dmpg17s1<div><p>Molly loves subtraction. She also loves non-negative numbers. For her birthday, Molly received an array \(A_1, A_2, \ldots, A_N\) of integers. To make up for the fact that you forgot to bring her a present, you decide to tell her the minimum value of \(d\) such that \(d = \left|A_i - A_j\right|\), such that \(1 \le i, j \le N\).</p>
<h4>Subtasks</h4>
<p>For all subtasks, \(-10^9 \le A_i \le 10^9\).</p>
<h5>Subtask 1 [40%]</h5>
<p>\(2 \le N \le 1\,000\)</p>
<h5>Subtask 2 [60%]</h5>
<p>\(2...Tue, 16 May 2017 21:49:50 +0000https://dmoj.ca/problem/dmpg17s1DMPG '17 B6 - Multiply and Surrenderhttps://dmoj.ca/problem/dmpg17b6<div><p>Roger has found \(N\) numbers, numbered \(A_1, A_2, A_3, \ldots A_{N-1}, A_N\). Roger wants to know how many digits there are in the the binary representation of the product \(A_1 \times A_2 \times A_3 \times \ldots \times A_{N-1} \times A_N\). Help Roger find this number!</p>
<h4>Input Specification</h4>
<p>The first line will consist of a single integer, \(N\).<br>
The next line will consist of \(N\) space separated integers, \(A_1, A_2, \ldots A_{N-1}, A_N\).</p>
<h4>Output Specificat...Tue, 16 May 2017 21:49:30 +0000https://dmoj.ca/problem/dmpg17b6DMPG '17 B5 - Hackathonshttps://dmoj.ca/problem/dmpg17b5<html><head><style>
@media print {
#cancer-spacer { height: 13em; }
}
</style></head><body><p>Roger is going to a hackathon again! Unlike last time, he has prepared a possible list of projects and has an estimate of how long each project takes, as well as its <em>wow factor</em>. However, his partner, Joey, wishes to go for very long coffee breaks, and thus gives him \(Q\) queries to answer: if they only have \(T\) minutes to complete their project, what is the maximum <em>wow factor</em> of...Tue, 16 May 2017 21:48:57 +0000https://dmoj.ca/problem/dmpg17b5DMPG '17 B4 - Bad Sorthttps://dmoj.ca/problem/dmpg17b4<div><p>Roger is teaching his CS club how to sort! This algorithm looks like this:</p>
<div class="codehilite"><pre><span></span><code><span class="n">function</span> <span class="n">sort</span><span class="p">(</span><span class="n">A</span><span class="p">[</span><span class="mi">0</span> <span class="o">..</span> <span class="n">N</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]):</span>
<span class="n">pivot</span> <span class="o"><-</span> <span class="n">A<...Tue, 16 May 2017 21:48:40 +0000https://dmoj.ca/problem/dmpg17b4DMPG '17 B1 - Whale and Soulhttps://dmoj.ca/problem/dmpg17b1<div><p>In the context of online games, a <strong>whale</strong> is a player who spends great sums of real money on video games. A <em>certain whale</em> has discovered \(N\) different membership options for a game they play, with the \(i\)-th costing \(c_i\) dollars and lasting \(d_i\) days. Keeping in mind that this whale would like to have membership for as long as possible while minimizing how much they swipe their credit card for, can you help them determine the best membership option?</p>
...Tue, 16 May 2017 21:47:50 +0000https://dmoj.ca/problem/dmpg17b1DMPG '17 B3 - Heroeshttps://dmoj.ca/problem/dmpg17b3<div><p><span title="Thanks, Andrew">Roger is addicted to the game Fire Emblem Heroes!</span> His main hero is <span style="color:green">Hector</span>, who has \(h_H\) health and deals \(d_H\) damage per turn. Hector is up against a foe who deals \(d_F\) damage per turn, and has \(h_F\) health. However, Hector's special, <em>Buckler</em>, activates every 4th turn and negates all damage done against him in that turn, as well as continues to deal the regular amount of damage.</p>
<p>Given \(N\) of...Tue, 16 May 2017 21:47:35 +0000https://dmoj.ca/problem/dmpg17b3Google Code Jam World Finals 2016 - Integeregexhttps://dmoj.ca/problem/cjwf16a<div><p>In this problem, a valid regular expression is one of the following. In the following descriptions, \(E_1\), \(E_2\), etc. denote (not necessarily different) valid regular expressions.</p>
<ul>
<li>A decimal digit: that is, one of \(0, 1, 2, 3, 4, 5, 6, 7, 8, 9\). </li>
<li>Concatenation: \(E_1E_2\). </li>
<li>Disjunction: \((E_1|E_2 |\ldots|E_N)\), for at least two expressions. Note that the outer parentheses are required. </li>
<li>Repetition: \((E_1)*\). Note that the outer parenth...Sun, 14 May 2017 17:51:00 +0000https://dmoj.ca/problem/cjwf16aECOO '17 R3 P3 - Region Selectionhttps://dmoj.ca/problem/ecoo17r3p3<div><p>The semi-final of the <code>OCEE</code> provincial competition happens at two different locations in Ontario. Ontario is a big place, so the locations need to be carefully chosen to accommodate the participants as best as possible.</p>
<p>In particular, a school's travel cost to the competition is equal to the square of the distance between the school and the nearest semi-final location. An optimal location selection would minimize the sum of these squared distances for every school.</p>...Sun, 14 May 2017 06:03:04 +0000https://dmoj.ca/problem/ecoo17r3p3ECOO '17 R3 P2 - Family Treeshttps://dmoj.ca/problem/ecoo17r3p2<div><p>Family trees are trees that show relationships between family members. They begin with a root ancestor and show that ancestor's children, then every child's children, and so on. For example, Bob, the root ancestor, can have two daughters Alice and Eve. Alice can then have two children Jenna and Brian, and Eve can have one daughter Sarah. To help find people in the tree, we give each family member a family ID, formatted as a series of integers separated by dots (e.g. <code>0.1</code>, <co...Sun, 14 May 2017 04:02:00 +0000https://dmoj.ca/problem/ecoo17r3p2ECOO '17 R3 P1 - Baker Briehttps://dmoj.ca/problem/ecoo17r3p1<div><h5>Author: Andrew Seidel</h5>
<p><em>Baker Brie</em> is holding a celebration for being in business for \(13\) years, and having opened its \(130^{th}\) franchise. <em>Baker Brie</em> wants to congratulate franchises that have performed well throughout the years. <em>Baker Brie</em> also wants to congratulate everyone for performing well on certain days of the year!</p>
<p><em>Baker Brie</em> wants to offer congratulations as follows:</p>
<ul>
<li>If, in a single day, all franchises combin...Sun, 14 May 2017 04:01:00 +0000https://dmoj.ca/problem/ecoo17r3p1CCO '17 - Professional Networkhttps://dmoj.ca/problem/cco17p5<div><h5>Canadian Computing Olympiad: 2017 Day 2, Problem 2</h5>
<p>Kevin is developing his professional network within a certain community. Unfortunately, he has not connected with anybody yet. But he has his eyes on \(N\) potentially valuable connections, numbered from \(1\) to \(N\). He is determined to connect with them all.</p>
<p>However, few people in this community are willing to friend an outsider. Each of the \(N\) people Kevin wants to connect with has similar, but different criteria ...Sat, 13 May 2017 03:12:37 +0000https://dmoj.ca/problem/cco17p5CCO '17 - Rainfall Storagehttps://dmoj.ca/problem/cco17p4<div><h5>Canadian Computing Olympiad: 2017 Day 2, Problem 1</h5>
<p>It was a dark and stormy night. It also rained, and rained, and rained.</p>
<p>Lucy wants to capture some of the rain, but she only has limited materials. She has a collection of pillars, of various heights, which she can configure to capture the rain. Each pillar is an integer
height and has length and width of \(1\). Once Lucy has her configuration of pillars, she has enough other siding material to enclose the front and back ...Sat, 13 May 2017 03:12:19 +0000https://dmoj.ca/problem/cco17p4CCO '17 - Vera and Modern Arthttps://dmoj.ca/problem/cco17p3<div><h5>Canadian Computing Olympiad: 2017 Day 1, Problem 3</h5>
<p>After being inspired by the great painter Picowso, Vera decided to make her own masterpiece. She has an empty painting surface which can be modeled as an infinite 2D coordinate plane. Vera likes powers of two \((1, 2, 4, 8, 16, \ldots)\) and will paint some some points in a repeated manner using step sizes which are a power of two.</p>
<p>Vera will paint \(N\) times. The \(i\)-th time can be described by three integers \(x_i\), ...Sat, 13 May 2017 03:12:02 +0000https://dmoj.ca/problem/cco17p3CCO '17 - Shifty Gridhttps://dmoj.ca/problem/cco17p6<div><h5>Canadian Computing Olympiad: 2017 Day 2, Problem 3</h5>
<p>You are given a rectangular grid of numbered tiles, with no empty spaces. This grid can only be
manipulated using a sequence of <em>shift</em> operations. A shift involves either moving an entire row left
or right by some number of units, or moving an entire column up or down by some number of
units. Tiles which move outside of the rectangular boundaries wrap around to the opposite side of
the grid. For example, in the grid</p>
...Sat, 13 May 2017 03:12:00 +0000https://dmoj.ca/problem/cco17p6CCO '17 - Cartesian Conquesthttps://dmoj.ca/problem/cco17p2<div><h5>Canadian Computing Olympiad: 2017 Day 1, Problem 2</h5>
<p>Long ago, in the land of Cartesia, there ruled the Rectangle Empire. The Empire was large and prosperous, and it had great success with expanding its territory through frequent conquests. The citizens of this ancient civilization followed many curious customs. Unfortunately, the significance of these are now shrouded in mystery.</p>
<p>The Rectangle Empire operated under a system of rectangular districts. These districts were ca...Sat, 13 May 2017 03:11:48 +0000https://dmoj.ca/problem/cco17p2CCO '17 - Vera and Trail Buildinghttps://dmoj.ca/problem/cco17p1<div><h5>Canadian Computing Olympiad: 2017 Day 1, Problem 1</h5>
<p>Vera loves hiking and is going to build her own trail network. It will consist of \(V\) places numbered from \(1\) to \(V\), and \(E\) bidirectional trails where the \(i\)-th trail directly joins two distinct places \(a_i\) and \(b_i\). Vera would like her network to be connected so it should be possible to hike between any two places using the trails. It is possible that there could be more than one trail directly joining the
s...Sat, 13 May 2017 03:11:25 +0000https://dmoj.ca/problem/cco17p1ECOO '17 R2 P4 - Zig Zaghttps://dmoj.ca/problem/ecoo17r2p4<div><p>A sequence of integers from \(1\) to \(N\) is said to be zig zag if the sequence contains each integer exactly once and, indexing from one, every element at an even index is greater than the preceding one, and every element at an odd index is less than the preceding one.</p>
<p>For example:</p>
<table class="table" style="max-width:70%">
<thead>
<tr>
<th>Sequence</th>
<th></th></tr></thead>
<tbody>
<tr>
<td>\(1, 3, 2, 5, 4\)</td>
<td>is zig zag</td></tr>
<tr>
<td>\(2, 5, 3, 4, ...Tue, 09 May 2017 22:00:00 +0000https://dmoj.ca/problem/ecoo17r2p4