Recently Added WLMOJ Problemshttps://mcpt.ca/The latest problems added on the William Lyon Mackenzie Online Judge websiteen-caSun, 19 May 2019 02:08:43 +0000Fast Heavy-Light Decompositionhttps://mcpt.ca/problem/hldfast<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 \(i\) a...Sun, 19 May 2019 02:08:43 +0000https://mcpt.ca/problem/hldfastA Cousin Problemhttps://mcpt.ca/problem/cousin<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 if and...Thu, 18 Apr 2019 13:33:59 +0000https://mcpt.ca/problem/cousinGirls Invitational '19 J1 - Ecalevol Tripletshttps://mcpt.ca/problem/gi19j1<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.</p>
...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19j1Girls Invitational '19 J2 - Emily Whohttps://mcpt.ca/problem/gi19j2<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 messagi...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19j2Girls Invitational '19 J4 - Who Will Win?https://mcpt.ca/problem/gi19j4<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>
<div st...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19j4Girls Invitational '19 J5 - Divisiblityhttps://mcpt.ca/problem/gi19j5<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\) that a...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19j5Girls Invitational '19 S4 - Miniature Sudokuhttps://mcpt.ca/problem/gi19s4<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="//mcpt.ca/texoid/9fa4d695e7d5deb4f38a4e383fa4a3ecc9b7d546/svg" onerror="this.src='//mcpt.ca/texoid/9fa4d695e7d5...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19s4Girls Invitational '19 S1 - Evan's Essayhttps://mcpt.ca/problem/gi19s1<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 to sea...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19s1Girls Invitational '19 S3 - GOTOhttps://mcpt.ca/problem/gi19s3<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> Out...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19s3Girls Invitational '19 S2 - Road Triphttps://mcpt.ca/problem/gi19s2<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 integer, ...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19s2Girls Invitational '19 J3 - Essay Scoreshttps://mcpt.ca/problem/gi19j3<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 the e...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19j3Girls Invitational '19 S5 - Dodgeball Clubhttps://mcpt.ca/problem/gi19s5<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 practices...Wed, 17 Apr 2019 02:56:30 +0000https://mcpt.ca/problem/gi19s5Data Compressionhttps://mcpt.ca/problem/datacompression<p>This week, we will try to compress a string! You are to output the string given in the Pastebin link? Easy right? But there are five catches:</p>
<ul>
<li>Your score will be based on the number of characters in your program.</li>
<li>Only java is allowed for this question.</li>
<li>You will be able to see the program that generates the string.</li>
<li>The person with the lowest character AC by 11:59 next Sunday (April 14th) will win $25. </li>
<li>If two people have a solution with the same ...Fri, 05 Apr 2019 15:37:00 +0000https://mcpt.ca/problem/datacompressionA Euclid Problemhttps://mcpt.ca/problem/euclid1<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 of <...Tue, 02 Apr 2019 23:19:50 +0000https://mcpt.ca/problem/euclid1A Subarray Problem 2https://mcpt.ca/problem/asubarrayproblem2<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 the su...Sun, 24 Mar 2019 17:25:56 +0000https://mcpt.ca/problem/asubarrayproblem2A Subarray Problemhttps://mcpt.ca/problem/asubarrayproblem<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 integers,...Sun, 24 Mar 2019 17:25:56 +0000https://mcpt.ca/problem/asubarrayproblemAn XOR Problemhttps://mcpt.ca/problem/anxorproblem<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>The ...Sun, 24 Mar 2019 17:25:56 +0000https://mcpt.ca/problem/anxorproblemGraph Theory 5https://mcpt.ca/problem/graphtheory5<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 each...Sun, 24 Mar 2019 17:25:56 +0000https://mcpt.ca/problem/graphtheory5A Base Problemhttps://mcpt.ca/problem/abaseproblem<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 contain ...Sun, 24 Mar 2019 17:25:56 +0000https://mcpt.ca/problem/abaseproblemFast Bit Duplicationhttps://mcpt.ca/problem/bitduplication<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 class="kt...Sun, 24 Mar 2019 14:47:50 +0000https://mcpt.ca/problem/bitduplicationGirls Invitational '18 J3 - Ski Chair Challengehttps://mcpt.ca/problem/gi18j3<p>Every winter break, Mackenzie students go on a trip to the Lyon ski resort. Ms.
William and her students are all suited up and ready to get onto the ski lift. All
chairs hold two people with a certain maximum weight. Help Ms. William determine
the minimum number of chairs she needs in order to send up the maximum number
of students.</p>
<h4>Input Specification</h4>
<p>The first line will contain an integer that indicates the maximum weight capacity, \(C\ (0 \le C \le 150)\), a
chair can hold....Mon, 11 Mar 2019 00:58:28 +0000https://mcpt.ca/problem/gi18j3Girls Invitational '18 J2 - Munara’s Magnificent Math Machinehttps://mcpt.ca/problem/gi18j2<p>Munara has created a Magnificent Math Machine. Her machine will take any integer, \(I\ (0 \le I \le 100)\), and perform 3 operations on it: addition, multiplication, and subtraction.</p>
<p>Each time she feeds a number, \(N\ (1 \le N \le 100)\), through the machine, Munara must indicate which numbers by which she is multiplying, adding, and subtracting and in which order these operations are occurring.</p>
<h4>Input Specification</h4>
<p>The first line of input is the number she feeds into th...Mon, 11 Mar 2019 00:58:28 +0000https://mcpt.ca/problem/gi18j2Girls Invitational '18 J1 - Not Not Very Veryhttps://mcpt.ca/problem/gi18j1<p>Olivia strongly dislikes her co-worker Noah. This morning, Noah asked Olivia what she thinks of him. In response, she has decided to send a message with a long string, \(S\ (1 \le |S| \le 400)\), of <code>not</code>s and <code>very</code>s to confuse him about how she feels. However, Olivia is very particular about the words she chooses and, thus, her message must fulfill these requirements:</p>
<ul>
<li>Olivia must use the same number of <code>not</code>s and <code>very</code>s in her respon...Mon, 11 Mar 2019 00:58:28 +0000https://mcpt.ca/problem/gi18j1Girls Invitational '18 J5 - Kstar and Partyhttps://mcpt.ca/problem/gi18j5<p>Kstar is hosting a party and knows that exactly \(N\ (1 \le N \le 500\ 000)\) people will
come, and the order in which they will enter the house. Each person has an integer
energy level, \(E_i\ (−2000 \le E_i \le 2000)\) which is also known to Kstar.</p>
<p>The <em>synergy</em> level between a pair of people is the product of the two people’s energy
levels. The combined <em>synergy</em> in the house is equal to the sum of the <em>synergy</em> levels of
all distinct pairs of people in the hous...Mon, 11 Mar 2019 00:58:28 +0000https://mcpt.ca/problem/gi18j5Girls Invitational '18 J4 - Elections in Ada Landhttps://mcpt.ca/problem/gi18j4<p>The country of Ada Land is holding their general election!</p>
<p>Ada Land uses a different voting system than Canada, and you have been tasked with figuring out the winners.</p>
<p>In the Ada Landian elections, one election is held for each of the \(N\) ridings. Each riding elects one candidate. Each election has \(V_i\) voters and \(C_i\) candidates.</p>
<p>Each of the \(V_i\) voters writes the names of all \(C_i\) candidates in order of preference on their ballot.</p>
<p>In order to be ele...Mon, 11 Mar 2019 00:58:28 +0000https://mcpt.ca/problem/gi18j4