Recently Added MCPT Problemshttps://mcpt.ca/The latest problems added on the MCPT's Online Judge websiteen-caMon, 19 Aug 2019 01:15:20 +0000Froghttps://mcpt.ca/problem/frog<div><p>There are \(N\) stones, numbered \(1, 2, \ldots, N\). For each \(i\ (1 \le i \le N)\), the height of Stone \(i\) is \(h_i\). Here, \(h_1 \lt h_2 \lt \ldots \lt h_N\) holds.</p>
<p>There is a frog who is initially at Stone \(1\). He will repeat the following action some number of times to reach Stone \(N\):</p>
<ul>
<li>If the frog is currently on Stone \(i\), jump to one of the following stones: Stone \(i+1, i+2, \ldots, N\). Here, a cost of \((h_j - h_i)^2 + C\) is incurred, where \(j\)...Mon, 19 Aug 2019 01:15:20 +0000https://mcpt.ca/problem/frogToo Much Memory!https://mcpt.ca/problem/mle<div><p>Everybody loves using memory: <a href="https://files.larry.science/f/wzhe1h3i.png" rel="nofollow">Chrome does it</a>, <a href="https://files.larry.science/f/y0z4m1nq.png" rel="nofollow">Discord loves it</a> and <a href="https://files.larry.science/f/oj37tu6j.png" rel="nofollow">Java is even infamous for it</a>. So today you are given a challenge: to use more then \(32\) megabytes of it!</p>
<p>There is just one catch: your code must only consist of exactly \(1\) character.</p>
<p>Good lu...Sat, 17 Aug 2019 03:51:03 +0000https://mcpt.ca/problem/mleA Harder Coin Problemhttps://mcpt.ca/problem/ahardercoinproblem<div><p>Angie is going shopping!</p>
<p>She has \(N\) different types of coins in her pocket, with the \(i^{th}\) type of coin being worth \(d_i\) dollars, and she's going to \(V\) stores. From the \(j^{th}\) store, she wants to buy \(c_j\) dollars worth of stuff from store \(j\), but store \(j\) only accepts the first \(l_j\) types of coins in her pocket!</p>
<p>Can you help her figure out the minimum number of coins to pay for each transaction in exact change?</p>
<p>Note that for the purpose...Sun, 11 Aug 2019 17:03:24 +0000https://mcpt.ca/problem/ahardercoinproblemMaintaining an Envelopehttps://mcpt.ca/problem/lines<div><p>There is a 2D-plane where only lattice points with their x-coordinates from \(1\) to \(N\) are of interest.</p>
<p>Support the following operations:</p>
<ul>
<li><code>1 n m b</code> Add a line with an ID of \(n\) \((1 \leq n \leq Q)\) in the form of \(y = mx + b\) to the plane. All line IDs are guaranteed to be distinct.</li>
<li><code>2 n</code> Delete the line with an ID of \(n\). It is guaranteed that the line exists at this time.</li>
<li><code>3 c</code> Output the ID of the line t...Mon, 29 Jul 2019 12:34:42 +0000https://mcpt.ca/problem/linesTripleshttps://mcpt.ca/problem/triples<div><p>Given an array of integers, \(a\), compute the number of unique ways to satisfy the equation \(a_i + a_j = a_k\), where \(i \neq j \neq k\) and \(a_i \leq a_j\). To be unique, each counted equation after being filled in must never have been counted before.</p>
<h4>Input Specification</h4>
<p>The first line will contain a single integer \(N\), \(3 \leq N \leq 5000\).</p>
<p>The next line will contain \(N\) space separated integers, describing the array. \(1 \leq a_i \leq 10^6\)</p>
<h4>Ou...Thu, 25 Jul 2019 02:27:06 +0000https://mcpt.ca/problem/triplesStatic Tree Testhttps://mcpt.ca/problem/ds189<div><p>Given a unweighted tree rooted at of \(N\) nodes numbered from \(1\) to \(N\), rooted at Node \(1\), and each node \(u\) has a given initial value \(v_u\), support the following operations:</p>
<ul>
<li><code>1 u x</code>: Increment the subtree of node \(u\) by the value \(x\)</li>
<li><code>2 u v x</code>: Increment all nodes along the path from \(u\) to \(v\) by the value \(x\)</li>
<li><code>3 u</code>: Output the maximum value of all nodes in the subtree of \(u\)</li>
<li><code>4 u v...Sat, 20 Jul 2019 20:28:34 +0000https://mcpt.ca/problem/ds189Fast Heavy-Light Decompositionhttps://mcpt.ca/problem/hldfast<div><p>On an unweighted tree, there are \(N\) nodes and \(N - 1\) edges. The nodes are numbered from \(1\) to \(N\). All nodes \(i\) have a parent \(p_i\), except for the root node, for which \(p_i\) is \(0\). All nodes are able to reach the root by repeatedly going up the parent of the current node.</p>
<p>Initially, all nodes have a value of \(0\). Perform the following operation on each node \(i\):</p>
<p>Add \(x_i\) to the value of all nodes on the path from \(i\) to the root, including \(...Sun, 19 May 2019 02:08:43 +0000https://mcpt.ca/problem/hldfastA Cousin Problemhttps://mcpt.ca/problem/cousin<div><p>There are \(N\) nodes with IDs from \(1\) to \(N\). All nodes, with the exception of Node \(1\), has a parent node with an ID less than itself. Each node has a value. The \(i^{\text{th}}\) node has a value of \(V_i\).</p>
<p>A \(k^{\text{th}}\) ancestor of a node is defined as follows:</p>
<ul>
<li>If \(k = 1\), the parent of the node</li>
<li>If \(k > 1\), the parent of the \((k - 1)^{\text{th}}\) ancestor of the node</li>
</ul>
<p>Two nodes are considered \(k^{\text{th}}\) cousins i...Thu, 18 Apr 2019 13:33:59 +0000https://mcpt.ca/problem/cousinGirls Invitational '19 J1 - Ecalevol Tripletshttps://mcpt.ca/problem/gi19j1<div><p>Finding Reppoh Ecarg too difficult a game, the children of Ada Land prefer to play the game of Ecalevol. This game is a lot simpler: a player draws \(3\) cards, and then exclaims <code>Ecalevol!</code> if they win, or <code>I lost.</code> if they lose.</p>
<p>All cards have an integer \(K\ (-100 \leq K \leq 100)\) on them. A hand is a winning hand if they can be arranged in an order where the first card divided by the second card, and then divided by the third card results in an integer....Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19j1Girls Invitational '19 J2 - Emily Whohttps://mcpt.ca/problem/gi19j2<div><p>Catherine has just gotten a new SIM card and is asking friends to text her their names so she can add their contacts to her new phone. However, she has run into a big problem: two of her friends are both named Emily Hu! Catherine knows that each Emily will get mad if she is mixed up with the other Emily, so she doesn't want to ask which Emily is messaging her. Instead, she decides to analyze their messages to see if she can use her knowledge of their personalities to figure out who is me...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19j2Girls Invitational '19 J4 - Who Will Win?https://mcpt.ca/problem/gi19j4<div><p>Here at Mackenzie, we take great pride in our sports teams. Since winter has come to an end, our school's attention has shifted to the basketball team. They'll be competing for the best team in our region as they hope to make provincials.</p>
<p>In MCPT, we like to analyze other schools and assign power levels to each high school basketball team in our region, including ourselves. There is an upcoming single elimination round robin tournament where \(2^N\) teams will be competing.</p>
<d...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19j4Girls Invitational '19 J5 - Divisiblityhttps://mcpt.ca/problem/gi19j5<div><p>Winnie has run out of backstory to give you, so she just gave you a question instead.</p>
<blockquote><p>Given a string \(A\) consisting of only integers, find the number of substrings of \(A\) that are divisible by \(9216\).</p>
</blockquote>
<h4>Input Specification</h4>
<p>The first line will contain a string \(A\ (1 \le |A| \le 2\ 000)\). \(A\) will only contain digits, and will not contain leading \(0\)s.</p>
<h4>Output Specification</h4>
<p>Output the number of substrings of \(A\) t...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19j5Girls Invitational '19 S4 - Miniature Sudokuhttps://mcpt.ca/problem/gi19s4<div><p>The puzzle game Sudoku is a classical game. In the puzzle, the player is given a partially filled \(9 \times 9\) grid. The objective of the game is to fill in the grid such that each row, column, and each of the nine \(3 \times 3\) subgrids contain all the digits from \(1\) to \(9\).</p>
<div style="max-width: 100%;height: 275;max-height: 275;width: 275;text-align: center"><img src="https://mcpt.ca/texoid/9fa4d695e7d5deb4f38a4e383fa4a3ecc9b7d546/svg" onerror="this.src='//mcpt.ca/texoid/9...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19s4Girls Invitational '19 S1 - Evan's Essayhttps://mcpt.ca/problem/gi19s1<div><p>Evan has just just finished writing an English essay about the importance of computer security and realizes that he used some words too much!</p>
<p>Can you help Evan write a program that finds the number of occurrences of a substring in a string and replace the \(N^{th}\) occurrence with a different string?</p>
<p>Evan would really appreciate it!</p>
<h4>Input Specification</h4>
<p>The first line will contain the string to search within.
<br>
The second line will contain the substring t...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19s1Girls Invitational '19 S3 - GOTOhttps://mcpt.ca/problem/gi19s3<div><p>You are given a piece of code consisting of \(N\) lines from your friend! Unfortunately, your friend only knows the <code>GOTO</code>, <code>PRINT</code>, and <code>QUIT</code> statements, and has created a jumbled mess that you must now debug!</p>
<p>The description of each statement is as follows:</p>
<ul>
<li><code>GOTO i</code> Jump to line \(i\). If this statement is on line \(j\), it is guaranteed \(1 \le i \le N, i \ne j\). The lines are \(1\)-indexed.</li>
<li><code>PRINT k</code...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19s3Girls Invitational '19 S2 - Road Triphttps://mcpt.ca/problem/gi19s2<div><p>April is taking a road trip with her friends! April's world can be represented by a coordinate plane, where she starts at \((0,0)\). There are \(N\) attractions with coordinate positions she would like to visit. She must visit these coordinates in order, and can travel in a straight line between attractions.</p>
<p>Given a list of attractions to visit in order, can you calculate the total distance traveled?</p>
<h4>Input Specification</h4>
<p>The first line of input will contain one inte...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19s2Girls Invitational '19 J3 - Essay Scoreshttps://mcpt.ca/problem/gi19j3<div><p>You have just written an \(N\) line essay for English. Each line is numbered from \(1\) to \(N\), and line \(i\) is given a <em>value</em> of \(v_i\).</p>
<p>A paragraph is defined as a <em>subarray</em> of lines from the essay. Note that a paragraph may contain of a single line. The <em>score</em> of a paragraph is maximum <em>value</em> of any line in the paragraph. The <em>total score</em> of the essay is the sum of the <em>scores</em> of all the paragraphs.</p>
<p>Your teacher wants ...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19j3Girls Invitational '19 S5 - Dodgeball Clubhttps://mcpt.ca/problem/gi19s5<div><p>Kstar has found a new dodgeball club called the Anonymous Dodgeball Association (or ADA). The ADA loves laces, but more importantly, they love dodgeball, so let's focus on that.</p>
<p>The ADA has \(N\) members, who each have a unique ID from \(1\) to \(N\). Person \(i\) has a dodgeball skill level of \(A[i]\).
Some people are so bad that their skill level is negative.</p>
<p>There are two types of meetings: training meetings and game meetings.</p>
<p>At a training meeting, everyone prac...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19s5A Euclid Problemhttps://mcpt.ca/problem/euclid1<div><h5>Euclid 2016 Problem 9a</h5>
<p>The string <code>AAABBBAABB</code> is a string of <strong>ten</strong> letters, each of which is <code>A</code> or <code>B</code>,
that does not include the consecutive letters <code>ABBA</code>.</p>
<p>The string <code>AAABBAAABB</code> is a string of <strong>ten</strong> letters, each of which is <code>A</code> or <code>B</code>,
that does include the consecutive letters <code>ABBA</code>.</p>
<p>Determine, with justification, the total number of strings...Tue, 02 Apr 2019 23:19:50 +0000https://mcpt.ca/problem/euclid1A Subarray Problem 2https://mcpt.ca/problem/asubarrayproblem2<div><p>You are given an array \(a\) of length \(N\). You want to count the number of subarrays of length \(K\) whose sum is strictly larger than the sum of any subarray of length \(K-1\).</p>
<h4>Input Specification</h4>
<p>The first line will contain the integers \(N, K\ (2 \le K \le N \le 10^5)\).</p>
<p>The second line will contain \(N\) integers, \(a_i\ (|a_i| \le 10^4)\).</p>
<h4>Output Specification</h4>
<p>Output the number of subarrays of length \(K\) whose sum is strictly larger than t...Sun, 24 Mar 2019 17:25:56 +0000https://mcpt.ca/problem/asubarrayproblem2A Subarray Problemhttps://mcpt.ca/problem/asubarrayproblem<div><p>You are given a permutation \(a\) of the integers from \(1\) to \(N\). You want to find</p>
<p>\[ \displaystyle \sum_{l=1}^{N}{\sum_{r=l}^{N}{\min(a_l,a_{l+1},\ldots,a_r)}} \]</p>
<p>In other words, let \(M_{l,r} = \min(a_l,a_{l+1},\ldots,a_r)\). You want to find the sum of \(M_{l,r}\) for all \(1 \le l \le r \le N\).</p>
<h4>Input Specification</h4>
<p>The first line will contain the integer \(N\ (1 \le N \le 2 \times 10^5)\).</p>
<p>The next line will contain \(N\) space-separated inte...Sun, 24 Mar 2019 17:25:56 +0000https://mcpt.ca/problem/asubarrayproblemAn XOR Problemhttps://mcpt.ca/problem/anxorproblem<div><p>You are given an array \(a\) of length \(N\). You repeatedly perform the following operation:</p>
<ul>
<li>Let the XOR of all elements in \(a\) be \(x\). Select an integer \(i\ (1 \le i \le N)\) and replace \(a_i\) with \(x\).</li>
</ul>
<p>Your goal is to match \(a\) with another array \(b\). Determine if it is possible to achieve the goal, and the minimum number of operations required.</p>
<h4>Input Specification</h4>
<p>The first line will contain the \(N\ (1 \le N \le 10^5)\).</p>
<p...Sun, 24 Mar 2019 17:25:56 +0000https://mcpt.ca/problem/anxorproblemGraph Theory 5https://mcpt.ca/problem/graphtheory5<div><p>Given a connected graph of \(N\) nodes and \(M\) weighted bidirectional edges, print the maximum Greatest Common Divisor (GCD) of the weights of the edges of any connected subgraph. A connnected subgraph is a graph such that there is at least \(1\) path between any two nodes, and all edges in the subgraph are in the original graph.</p>
<h4>Input Specification</h4>
<p>The first line will contain two integers, \(N, M\ (2 \le N \le 10^4, 1 \le M \le 10^5)\).</p>
<p>The next \(M\) lines will...Sun, 24 Mar 2019 17:25:56 +0000https://mcpt.ca/problem/graphtheory5A Base Problemhttps://mcpt.ca/problem/abaseproblem<div><p>You are given \(2\) integers \(x\) and \(y\), which are in base \(b\). Please print out the sum, and product of \(x\) and \(y\) in base \(b\).</p>
<h4>Input Specification</h4>
<p>The first line will contain the integer \(b\ (2 \le b \le 10)\).</p>
<p>The second line will contain the integer \(x\).</p>
<p>The third line will contain the integer \(y\).</p>
<p>\(x\) and \(y\) will each contain at most \(5\) digits, and each digit will be in the range \([0, b)\). \(x\) and \(y\) will not con...Sun, 24 Mar 2019 17:25:56 +0000https://mcpt.ca/problem/abaseproblemFast Bit Duplicationhttps://mcpt.ca/problem/bitduplication<div><p>Given 32-bit unsigned integers, duplicate each bit in-place in the integer.</p>
<p>For example:</p>
<ul>
<li>\(10001_2\) becomes \(1100000011_2\)</li>
<li>\(11110_2\) becomes \(1111111100_2\) </li>
</ul>
<h4>Implementation</h4>
<p>One function:</p>
<div class="codehilite"><pre><span></span><code><span class="kt">unsigned</span> <span class="kt">long</span> <span class="kt">long</span> <span class="nf">duplicatebits</span><span class="p">(</span><span class="kt">unsigned</span> <span clas...Sun, 24 Mar 2019 14:47:50 +0000https://mcpt.ca/problem/bitduplication