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.

UVa 12424 – Answering Queries on a Tree

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

UVa 12425 – Best Friend

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

UVa 12426 – Counting Triangles

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

UVa 12427 – Donkey of the Sultan

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

UVa 12428 – Enemy at the Gates

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

UVa 12429 – Finding Magic Triplets

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:

1. Find $x = ( i \times i \times i ) \mod k$ and store $x$ in a BIT. BIT stores all occurrences of $c$ and by iterating in reverse order we make sure that all $c$ in BIT is greater or equal to $i$.
2. Let $b = ( i \times i ) \mod k$. This is the current $b$ we are working with. In BIT we have $c$ which are $c geq b$. Now all we need is to find possible values of $a$.
3. Now, take any value of $c$ from BIT. For this $c$ and current $b$, how many ways can we choose $a$ so that $a + b \equiv c$. Notice that $a$ can be anything from $1$ to $k$, or $0$ to $k-1$. Therefore, no matter what is the value of $c$ we can chose $1$ number from $0$ to $k-1$ so that $a + b \equiv c$.

   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$.

4. 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

UVa 12430 – Grand Wedding

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

UVa 12431 – Happy 10/9 Day

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

UVa 12432 – Inked Carpets

Complexity: Unknown
Category: Unknown

I didn’t try this problem yet. I guess this was the stopper.

Conclusion

It was a good set. I especially enjoyed solving $B, D$, and $F$.

• Category: CPPS
• Tag: editorial, uva