Given K variables, $a_1, a_2, a_3 \dots a_K$ and a value $N$, how many ways can we write $a_1 + a_2 + a_3 \dots a_K = N$, where $a_1, a_2, a_3 \dots a_K$ are non-negative integers?
For example, if $K = 3$ and $N=2$, there are 6 solutions.
a b c ----- 2 0 0 0 2 0 0 0 2 1 1 0 1 0 1 0 1 1
Last week (2015-08-21) we practiced with this set. Some of the problems didn’t have proper constraints, which caused some headaches. This contest originally followed Google Code Jam format with two subproblems ( small and large ) for each problem. Each of the sub-problems had a different constraint on them. But when they uploaded it online, they removed both constraints from some problems, making things confusing. We ended up guessing the constraints when solving them.
During contest time, we managed to solve $B, E$, and $H$. I was stuck with $F$. Should have moved on. $C$ and $D$ were far easier than $F$. Bad decision from my end.
Complexity: $O(logN)$
Category: Segment Tree, DFS, LCA
At first, it seemed like a problem of Heavy Light Decomposition. But after a moment I realized it can be done without HLD.
Run a dfs from any node and make the tree rooted tree. Now consider the color $X$. For every node that has color $X$, the edge from its parent will have cost $1$. Since the root can also have color $X$, we need to add a dummy node $0$ and make that root. Now, run another dfs and calculate the distance from the root to each node. We repeat this for all $10$ color and build $10$ trees. Let us call tree with the color of node $X$, $T_X$.
Now, whenever we have an update to change node $u$ from color $X$ to color $Y$, it means that the edge entering $u$ in tree $T_X$ will now have a cost $0$. Since its cost decreased, the distance from the root of all the nodes in the subtree of $u$ will be lowered by $1$. We can apply this change using preorder traversal dfs + segment tree. Do the opposite for $T_Y$. Increase the value of all nodes under subtree $u$ in $T_Y$.
And for query $u$ and $v$, find the distance between these two nodes in each of the $10$ trees. This can be done in $O(logN)$ using LCA + Segment Tree.
Code: http://ideone.com/UEU9J4
Complexity: $O(\sqrt{N} + \sqrt[3]{N} \times \text{Complexity of } \phi (N) )$
Category: Number Theory, Euler Phi, GCD
So for given integers $N$ and $X$, we have to find out how many number $I$ are there such that $gcd(N, I) \leq X$.
In order to calculate $gcd(N,I) \leq X$, I first need to be able to calculate how many numbers are there such that $gcd(N,I) = Y$. I started with a small value of $Y$ first. So the first thing I asked myself, how many numbers are there such that $gcd(N, I) = 1$? The answer is $\phi (N)$. Then I asked how many are there such that $gcd(N, I) = 2$?
This took a moment, but I soon realized, if $gcd(N,I)$ is equal $2$, then if I divide both $N$ and $I$ by $2$, then $gcd(\frac{N}{2},\frac{I}{2})$ will be equal to $1$. Now, all I had to calculate how many $I$ are there such that $gcd(\frac{N}{2},\frac{I}{2}) = 1$. The answer is $\phi (\frac{N}{2})$.
Therefore, there are $\phi (\frac{N}{Y})$ number of $I$ such that $gcd(N,I) = Y$.
Great. Now we can calculate number of $I$ such that $gcd(N,I) = Y$. Now, all we need to do is find the sum of all number of $I$ for which $gcd(N, I) = Y$ and $Y \leq X$. GCD of $N$ and $I$ can be as high as $10^{12}$, so running a loop won’t do.
Next I thought, what are the possible values of $g = gcd(N,I)$? Since $g$ is a number that divides $N$ and $I$, $g$ must be a divisor of $N$. So I simply calculated all the divisors of $N$ using a $\sqrt{N}$ loop. Next for each divisor $d$, I calculated $\phi ( \frac{N}{d})$ which is the number of ways to chose $I$ such that $gcd(N,I) = d$.
Now, for each query $X$, all I needed to do was find sum of $\phi ( \frac{N}{d} )$, where $d$ is a divisor of $N$ and $d \leq X$. Since all values of $\phi ( \frac{N}{d} )$ was precalculated, using cumalitive sum I answered it in $O(1)$.
Code: http://ideone.com/WrIH0C
Complexity: $O(N^2logN)$
Category: Two Pointer, Geo, Binary Search
We need to choose three points of a convex hull such that the area does not exceed $K$.
First, we need to know, for two points $i$ and $j$, $j>i$, what is the point $m$ such that $(i,j,m)$ forms the largest triangle possible. This can be done by selecting two points with two loops and then using a ternary search. But I used two pointer technique to find $m$ for every pair of $(i,j)$ in $O(N)$.
After that, for ever pair of $(i,j)$ I used binary search twice. Once on points $[j+1,m]$ and once on points $[m+1,n]$. Using binary search I found the point $x$ which gives the highest area that does not exceed $K$. Then I added $x-j-1$ in the first BS and $n-1-m$ in the second case.
Careful about not adding a degenerate triangle. Handle the edge cases properly.
Code: http://ideone.com/JtJjt9
Complexity: $O(1)$
Category: Game Theory, Combinatorics, Nim Game, Bogus Nim
This game can be converted to into a game of pile. Let the distance between the left boundary and gold coin be $x$ and the distance between diamond and silver coin be $y$. Now, instead of playing on the board, we can play with two piles of height $x$ (first pile) and $y$ (second pile).
Moving gold coin left is same as removing one coin from the first pile. Moving diamond coin left is the same as increasing second pile by one. Moving silver coin left is same as removing one coin from the second pile. Moving gold and silver coin left is same as removing one coin from both first and second pile.
Now, note that is a state of $(x,y)$ is losing and I try to increase the second pile by one, my opponent then can simply take one from the second pile and put me back to the same situation. That is, increasing the second pile has no effect in this game. This is a “Bogus” move. We will ignore this move.
Next, I drew a $5 \times 5$ table and calculated the Win or Lose state of each possible $(x,y)$. I found that only when both $x$ and $y$ are even, the first person loses. That is the second person, me, wins the game when $x$ and $y$ both are even.
What are the possible values of $x$? $x$ can only be between $a_1$ and $a_2$. Find the number of even numbers in this range. Let this be $r_1$. Next, $y$ can be between $c_1$ and $c_2$. Let the number of even numbers in this range be $r_2$. The distance between gold and diamond has no effect in this game. So we can put any amount of gap there.
Therefore, number of possible combination is $r_1 \times r_2 \times (b_2 – b_1 + 1 )$.
Code: http://ideone.com/6q2LZT
Complexity: $O(\sqrt{M})$
Category: Adhoc
This was the easiest problem in the set. In this problem, we are given $N$ nodes and $M$ edges, we have to find out how many leaves can this graph have if we maximize leaves.
The problem says the graph will be connected. So I created a star-shaped graph with it using $N-1$ edges. Let the center node be $0$ and remaining nodes be the numbers from $1$ to $N-1$. This gives me $N-1$ critical edges. Then I checked if I still have more edges left? If I do, then I need to sacrifice a critical edge.
The first edge that gets sacrifice is a special case. This is because, no matter which two nodes you connect, it will reduce the number of critical edges by $2$. There is no helping it. So let’s connect $1$ and $2$ and reduce our edge by $1$ and critical edge by $2$.
Then if we still have more edges left, then we need to sacrifice another critical length. From now on, at each step, only one critical edge will be removed. Also, this time we can add $2$ edges to the graph by removing one critical edge. Connect an edge between $(3,1)$ and $(3,2)$. Reduce $M$ by $2$ and critical edge by $1$.
Next is node $4$. We can add $3$ edges by removing $1$ critical edge now. We need to keep on doing this until all edges finish.
I guess it is possible to solve the problem in $O(1)$ but I didn’t bother with it. The number of test case was small anyway.
Code: http://ideone.com/X3bWyZ
Complexity: $O(N:logN)$
Category: Binary Indexed Tree, Number Theory
We have to find the number of triplets such that $a + b^2 \equiv c^3$ and $a \leq b \leq c$. Here is what I did.
Iterate over $c$ from $N$ to $1$ using a loop. Let the loop iterator be $i$. Now for each $i$, we do the following:
Let $y = \frac{i}{k}$. This means we have $y$ segments, in which value of $a$ spans from $0$ to $k-1$. So we add $y$ for each possible $c$ we take from BIT. Let $total$ be number of $c$ we have inserted till now. So we add $total \times y$ to $result$.
But it’s not over yet. What about the values of $a$ that we did not use. To be more exact, let $r = i \mod k$. If $r > 0$, then we have unused values of $a$. We need to use these.
But we have to be careful. We have used up values of $a$ from $1$ to $y \times k$. So the remaining $a$ we have is $1$ to $r$. $0$ is not included.
Since we don’t have all the values from $0$ to $k-1$, we are not able to handle all possible values $c$ anymore. How many can we handle exactly?
$a + b \equiv c$
$a \equiv c – b$
But we need $a$ can only be between $1$ and $r$.
$1 \leq c – b \leq r$
$\therefore 1+b \leq c \leq r + b$
Find out how many $c$ are there with values between $1+b$ and $r+b$ from BIT. Let this value be $z$. For each of those $c$ we can use one value of $a$ between $1$ to $r$. So add $z$ to $result$.
And that’s it. Be careful when handling edge cases in BIT.
Code: http://ideone.com/iMBUmU
Complexity: $O(N logN)$
Category: DFS, Bicoloring, Binary Search
The constraint was missing. I assumed $N <= 10^6$.
We have to remove some edges and then assign guards such that no edge is left unguarded and no edge has guards on both ends. We have to output the maximize the value of the edges that we remove.
Binary search over the value of edges which we need to remove. Now, let’s say we removed all edges with the value greater or equal to $x$. How do we decide that a valid assignment of guards is possible in this problem?
Suppose all the nodes in the graph are colored white. If we assign guard in a node, then we color it black. Now, two white nodes cannot be adjacent cause that would mean the edge is left unguarded. Two black nodes cannot be adjacent otherwise guards will chat with each other. That is both ends of an edge cannot have the same color in the graph. This is possible when the graph has no cycle of odd length. If a graph has no cycle, then it is bi-colorable. So all we need to do is check if the graph is bi-colorable.
Now, two special cases. If we can bicolor the graph without removing any edge, then answer is $0$. If we have to remove all edges then answer is $-1$. Why? Cause in the problem it is said we can remove proper subset of edges. The full set is not a proper subset.
Code: http://ideone.com/R6lkje
Complexity: $O(log^2N)$
Category: Divide and Conquor, Modular Exponentiation, Repeated Squaring
We have to find the value of:
$( d \times b^0 + d \times b^1 + d \times b^2 + … + d \times b^{n-1} ) \mod M$
$( d ( b^0 + b^1 + b^2 + … + b^{n-1} ) ) \mod M$.
Therefore, the problem boils down to finding the value of $( b^0 + b^1 + b^2 + … + b^{n-1} ) \mod M$. We cannot use the formula of geometric progression since $M$ and $b-1$ may not be coprime. So what do we do? We can use divide and conquer. How? Let me show you an example.
Suppose $f(n) = (b^0 + b^1 + b^2 + … + b^n)$. Let us find $f(5)$.
$f(5) = b^0 + b^1 + b^2 + b^3 + b^4 + b^5$
$f(5) = (b^0 + b^1 + b^2) + b^3 ( b^0 + b^1 + b^2)$
$f(5) = f(2) + b^3 \times f(2)$
$f(5) = f(2) \times (1 + b^3)$.
From this we can design a D&C in following way:
$\text{n is odd: }f(n) = f(\frac{n}{2}) \times ( 1 + b^{n/2 + 1 })$
$\text{n is even: }f(n) = f(n-1) + b^n$
$f(0) = 1$
Just apply modular arithmetic with the whole things. Also, note that $M$ can be as large as $10^{12}$, so $(a \times b)$ will overflow if they are multiplied directly, even after making them small by modulus $M$. So use repeated squaring method to multiply them.
Code: http://ideone.com/Fn6vzW
Complexity: Unknown
Category: Unknown
I didn’t try this problem yet. I guess this was the stopper.
It was a good set. I especially enjoyed solving $B, D$, and $F$.
I participated in this contest last year. Our team “NSU Shinobis” managed to solve 5 and placed in the top 10 ( failed to find the rank list ). The IUT 7th ICT National Fest 2015 is going to be held next month, so I thought I would try to up solve the remaining problems. I tried to compile detailed hints for the problems here.
Complexity: $O(N^3)$
Category: Loop, DP, Kadane’s Algorithm
Given $N$ points, we have to find the largest area of the rectangle which can fit such that there is no point inside the rectangle. Points on boundaries of the rectangle are allowed.
Now imagine a rectangle which has no point inside it and also no point on its boundary. Now focus on the top boundary of that rectangle. Since there is no point on that boundary, we can extend it up until it hits a point or limit. Same can be said for the bottom, left and right boundary. That is, the largest rectangle will have its boundary aligned with the limits or points.
Now let us fix the top and lower boundary of the rectangle. How many possible values can they take? Each boundary can take values of $y$-coordinate from one of the $N$ points or the limits $0$ and $W$. Using two nested loops, we can fix them.
Next we need to fix the left and right boundary. Lets us sort the points according to $x$ first and then according to $y$. Next we iterate over the points. Initially set the left boundary of rectangle aligned to $y$-axis, that is aligned with the left boundary of Sand Kingdom.
Now, for each point, if the $y$ coordinate of the point is above or below or on the boundary we fixed then we ignore them, cause they don’t cause any problem. But if they fall inside, then we need to process this point. We put the right boundary aligned to the $x$ coordinate of this point and calculate this rectangle.
But it’s not over. We shift the left boundary over to current right boundary and continue to process remaining points.
This is a classical problem of Kadane’s Algorithm. With two nested loops to fix upper and lower boundary and another loop inside iterating over $N$ points makes the complexity $O(N^3)$.
$O(N^2)$ solution is possible, by constructing a histogram for each row ( $O(N)$ ) and the calculating area of histogram in $O(N)$. But that’s not necessary here.
Code: http://ideone.com/FjvTN2
Complexity: $O(\sqrt{V}E)$
Category: Max Flow, Bipartite Matching, Dinic’s Algorithm, Path Cover
Another classical problem, though we had a hard time solving this one. Mainly cause we didn’t realize this was a path cover problem which can be solved using Max Flow.
Take each number provided and generate all child. Consider each number a node and if it possible to generate $B$ from $A$, then add a directed edge from $A$ to $B$. When you are done, you will have DAG.
Now split all the nodes in two. We are going to create a bipartite graph now. On the left side, we will have all the original nodes and on the right side we will have the copy we got by splitting the nodes. Now, for each edge between $A$ and $B$, add an edge in the bipartite graph from $A$ on the left side to $B$ on the right side.
Find the matching ( or maximum flow ) of this graph by running Dinic’s Algorithm. The answer will be $\text{Total Nodes} – \text{Matching}$.
Code: http://ideone.com/U1VPNB
Complexity: $O(M)$
Category: Expected Value, Probability, DP, Combination
If a shop can make $N$ different items, and in a single day prepares $K$ items from those $N$ items, then how many different sets of menus ($total$) can they make? $total = C^N_K$. Now, if they decide to make chicken that day for sure, how many sets of menus ( $chicken$ ) can they make now? $chicken = C^{N-1}_{K-1}$. So what is the probability $P$ that if I visit a shop I will get to eat chicken? $P = \frac{chicken}{total}$. And what is the probability that I will not eat chicken? $Q = 1- P$.
So now I know the probability of eating chicken for each shop. How do we find the expected value? We will find it using dynamic programming.
The states of dp only be the shop number. $dp(x)$ will give me the expected number of chicken that I can eat if I visit all shops starting from $x$. Our result will be $dp(1)$.
At each state, I have $P_i$ probability that I will eat chicken and $Q$ probability that I will not. So result for each state will be:
$dp ( pos ) = P \times ( 1 + dp ( pos + 1 ) + Q \times dp ( pos + 1 )$
$dp ( pos ) = P + P \times dp ( pos + 1 ) + Q \times dp ( pos + 1 )$
$dp ( pos ) = P + dp ( pos + 1 ) \times ( P + Q )$
$dp ( pos ) = P + dp ( pos + 1 )$.
In order to print the result in $\frac{A}{B}$ form, we need to avoid $double$ and use integer arithmetic in all places. I implemented my own fraction class for that purpose.
Code: http://ideone.com/mGKwuL
Complexity: $O(26 \times N)$
Category: String, Manacher’s Algorithm
For each query, we have to count the number of palindromes which are the substring of $S$, starts and ends with given $C$ and has exactly $X$ occurrences of $C$ in it. Since it deals with palindrome, perhaps it has something to do with Manacher’s Algorithm?
With Manacher’s Algorithm, we can find out the maximum length of palindrome in $O(N)$. But what’s more, we can actually generate an array $M$ which gives us, for each center in the extended string $E$, ( $aba$ when extended becomes ^#a#b#a#$ ) the maximum length of palindrome with that particular center. How can we use this knowledge to solve our problem?
Let us consider the character $’a’$ only. We can easily extend it for other characters by repeating the whole process $26$ \times.
Suppose we are working with center $x$. It has a palindrome from it with length $y$. Therefore, in the extended string of manacher, the palindrome starts from $x-y$ and ends in $x+y$. Now, how many \times does $’a’$ occurs in this palindrome? Using Cumulative Sum it is possible to answer in $O(1)$. Let that occurrence be $f = \text{# of times ‘a’ occurs in palindrome with center x}$. Let us mark this in another array $freq$. That is we mark it like $\text{freq[f]++}$, meaning we have $freq[f]$ palindromes where $’a’$ occurs $f$ times. But wait, what if the palindrome does not start and end with $’a’$? Simple, we keep on throwing the leading and trailing character until it starts and ends with $’a’$ and it will still have $f$ occurrences of $’a’$ in it.
So we repeat this for all possible center. Now, if the query is to find the number of palindromes that starts and ends with $’a’$ and $’a’$ occurs exactly $X$ \times, how do we solve it?
First of all, our result will contain $res = freq[X]$ in it. What’s more, our result will also contain $res \text{+=} freq[X+2] + freq[X+4] + freq[X+6] + …$. Why is that? Take any palindrome that contains more than $X$ occurrences of $’a’$. Since they start and end with $’a’$, we can just throw them out of that palindrome and reduce the occurrence of $’a’$ in it by $2$. After that, we keep on trimming down head and tail of that palindrome until we reach $’a’$ again. That is, a palindrome with $Y$ occurrences of $’a’$ can be trimmed down to palindrome with $Y-2$, $Y-4$, $Y-6$, $…$ occurrences of $’a’$.
Instead of getting the result $res = freq[X] + freq[X+2] + freq[X+4] + \dots$ we can just use cumulative sum again to find it in $O(1)$ here. Just find the cumulative sum of alternate terms.
Code: http://ideone.com/brZKXL
Complexity: $O(N: logN )$
Category: Adhoc
This was the easiest problem. Each shop gives me some money ($income$) and then for that shop I have to give Godfather some cut ($expense$). So for each shop I get $profit = income – expense$. So I calculate profit for each shop and then sort them. I can now skip $K$ shops. I will of course skip shops for which profit is negative as long as I am allowed to skip.
Code: http://ideone.com/s3iHGz
Complexity: $O(N!: N^2)$
Category: Geometry, Trigonometry, Permutation, Packing Problem
It’s a packing problem. At first glance, it seems like a tough problem but it’s not. Let us first define a few variables first.
This is the polygon. Each polygon has two horizontal lines through it. We will call them the low and top line. Each side of the polygon has a length of $x$. The radius of the polygon is $r = \frac{x}{2} + y$.
We are given the height of each polygon. But first, we will need to calculate the value of $x$ and $y$. We can find their values using trigonometry.
$y^2 + y^2 = x^2$
$2y^2 = x^2$
$x = \sqrt{2y^2}$
We also know that $h = y + x + y$. From that we can derive:
$y + x + y = h$
$2y+x = h$
$2y + \sqrt{2y^2} = h$
$2y + y\sqrt{2} = h$
$y( 2 + \sqrt{2} ) = h$
$y = \frac{h}{2} +\sqrt{2}$
With the above, we can find the value of $y = \frac{h}{2} +\sqrt{2}$ and $x = \sqrt{2y^2}$ But why did we find their values?
Okay, what happens when we put to polygon side by side? In order to solve this problem, we need to be able to find the distance between the center of two polygons $A$ and $B$.
Now if two polygons are of the same height and they are placed side by side, then the difference between their centers will be $d = r_a + r_b$. What happens when two polygons of arbitrary height come beside each other?
$3$ things can happen when two polygon $A$ and $B$ are placed side by side. $A$ is on left of $B$.
We need to calculate the value of $d$ for step $1$ and $2$. That can also be easily done using trigonometry. Try to draw some diagram yourself.
So we used $x$ and $y$ to find the value of $d$ between two polygons. How do we use this to find the minimum width of the box?
Suppose we are trying to pack the polygons in some order. Which order? We don’t know which order will give us minimum width so we try them all. There will be $N!$ order.
So for each order, what will be the minimum of width. First let’s take the first polygon, and put it inside the empty box such that it touches the left side of the box. We will calculate the center of each polygon relative to the left side of the box. The first box will have the center at $r_0$.
Now take the second box. First, imagine there is no polygon in the box. There where will be the center of the second polygon? Ar $r_1$. Now, since there is a polygon, we will try to put it besides that one. Where will be the center now? $r_0 + d$. We will take the maximum possible center.
Repeat this for the third polygon. Empty box, besides the first polygon, besides the second polygon. Take the maximum again. Repeat this for all polygon.
From all polygon, find the one with the maximum center position. Add radius of that polygon to its center to find the width.
Take the minimum width from all permutation.
Code: http://ideone.com/kphGx5
Complexity: $O(N^2)$
Category: Interval DP, LIS, Knuth Optimization
First, we need to calculate the power of each Deatheater. We can do that by calculating LIS from both directions and then adding them.
Once we calculate the power, we run an interval dp between $1$ and $N$. The dp will have states $start$ and $end$. Inside the dp a loop between start and end will run, choosing different cut sections. We will take the one with minimum value.
But this results in $O(N^3)$ solution. Using Knuth’s optimization we can reduce it to $O(N^2)$.
Code: http://ideone.com/XD6hZP
Complexity: $O(100 \times |S|^2 )$
Category: String, Trie, Data Structure
We will create two trie trees. The first one will contain all the queries. Take a query and concatenate them in a special way. Take the first string of the query and add a $\text{‘#’}$ and then reverse the second string of the query and attach it to result. That is, if we have $abc$ and $pqr$ as query, then special string will be $\text{abc#rqp}$. Insert all special strings for each query in the first tries.
Now, let us process the main string $S$. We will take each of its suffixes and insert into the second trie. Now, when inserting the suffixes, each time a new node is created, we can say that we found a unique substring.
Each time we find a unique substring we will process it further. Take the unique substring, and using brute force generate all possible special strings ( the one we made using query strings ) with the first and last characters of the unique string. We don’t need to take more than $10$ characters from each end.
For each of those special string we made from unique substring, we will query the first trie with it and find the node where it ends. We will add one to that node number in a global array.
Once we finish processing all nodes in the second trie, we will simply traverse the first trie according to each query and print the result found in that node.
Code: http://ideone.com/fsYMxI
Complexity: Unknown
Category: Matching on General Graph
I didn’t manage to solve this yet. It looks like matching on a general graph.
Complexity: $O(N:logN)$
Category: Data Structure, Heap
We want to minimize the waiting time for each person. So first we will sort the people in descending order. Next, we will create a priority queue, which will contain all the service center along with the information about when that service center will be free. Initially, all service centers are free.
Now, we take each person and take out the service center that will get free at the earliest time. The person had to originally wait $x$ minutes and it took $y$ minutes for the service to get free again. So the person had to wait for $x+y$ minutes. We insert the service again inside the heap and update its free time by the time it takes to serve one person.
Repeat and keep track of the highest time a person had to wait.
Code: http://ideone.com/KVHnTX
I hope the details are clear enough for everyone to understand. Let me know if you find any mistakes.
