## Monday, August 31, 2015

### Bit Manipulation

On this post, we will look into how to use "Bitwise Operators" to manipulate bits of a number. Bit manipulation is a useful tool that can sometimes perform complicated tasks in a simple manner.

We will work on integer values and assume each number has $32$ bits in them. If a number has only $0$ or $1$ as its digit, then assume that it is in binary form. All position of bits is $0$ indexed.

Since binary values can only be $0$ or $1$, we sometimes refer them like light bulbs. A bit being "Off" means it has value $0$ and being "On" means it has value $1$. Bit $1$ is also referred as "Set" and bit $0$ as "Reset".

We need to have a strong grasp of how AND, OR, Negation, XOR and Shift Operators work to understand how bit manipulation works. If you have forgotten about them, then make sure you revise.

## Checking Bit at Position X

Given a number $N$, find the value of its bit at position $X$. For example, if $N=12=(1100)_2$ and $X=2$, then value of bit is $1$.

So how do we find it? We can find this value in three steps:
1. Let, $mask = 1 << X$
2. Let, $res = N \: \& \: mask$
3. If $res$ is $0$, then bit is $0$ at that position, else bit is $1$.
Let us see it in action with the example above, $N = 12$ and $X = 2$.

$1100$
$\underline{0100} \:\&$ ( $1 << 2$ is just $1$ shifted to left twice )
$0100$

Now, what happened here? In step $1$, when we left shifted $1$ $X$ times, we created a number $mask$ which has bit $1$ only at position $X$. This is a useful application of left shift operator. Using this, we can move $1$ bit anywhere we want.

Next, at step $2$, we find the result of performing AND operator between $N$ and $mask$. Since $mask$ has $0$ in all positions except $X$, the result will have $0$ in all places other than $X$. That's because performing AND with $0$ will always give $0$. Now, what about position $X$. Will the result at position $X$ have $0$ too? That depends on the bit of $N$ at position $X$. Since, the $X$ bit in the mask is $1$, the only way result will have $0$ at that position if $N$ has $0$ in that position.

So, when all position of $res$ is $0$, that is $res$ has value $0$, we can say that $N$ has $0$ bit in position $X$, otherwise it doesn't.

## Set Bit at Position $X$

Given a value $N$, turn the bit at position $X$ of $N$ to $1$. For example, $N=12=1100$ and $X=0$, then $N$ will become $13=1101$.

This can be done in two steps:
1. Let, $mask = 1 << X$
2. $N = N \:|\: mask$
$1100$
$\underline{0001}\:|$
$1101$

In step $1$, we shift a $1$ bit to position $X$. Then we perform OR between $N$ and $mask$. Since $mask$ has 0 in all places except $X$, in result all those places remain unchanged. But $mask$ has $1$ in position $X$, so in result position $X$ will be $1$.

## Reset Bit at Position $X$

Given a value $N$, turn the bit at position $X$ of $N$ to $0$. For example, $N=12=1100$ and $X=3$, then $N$ will become $4=0100$.

This cane be done in three steps:
1. Let, $mask = 1 << X$
2. $mask = \sim mask$
3. $N = N \:\&\: mask$
$1100$
$\underline{0111}\:\&$ ( We first got $1000$ from step $1$. Then used negation from step 2.)
$0100$

In step $1$ we move $1$ bit to position $X$. This gives us a number with $1$ in position $X$ and $0$ in all other places. Next we negate the $mask$. This flips all bits of $mask$. So now we have $0$ in position $X$ and $1$ in all other places. Now when we perform AND between $mask$ and $N$, it forces the bit at the $X$ position to $0$ and all other bits stay intact.

## Toggle Bit at Position X

Given a value $N$, toggle the bit at position $X$, i.e, if bit at $X$ is $0$ then make it $1$ and if it is already $1$, make it $0$.

This can be done in two steps:
1. Let, $mask = 1 << X$
2. $N = N \:\wedge\: mask$
First we shift bit $1$ to our desired position $X$ in step $1$. When XOR is performed between a bit and $0$, the bit remains unchanged. But when XOR performed between a bit and $1$, it toggles. So all position except $X$ toggles during step 2, since all position in mask except $X$ is $0$.

## Coding Tips

When coding these in C++, make sure you use lots of brackets. Bitwise operators have lower precedence than $==$ and $!=$ operator which often causes trouble. See here

What would be the output of this code:
if ( 0 & 6 != 7 ) printf ( "True\n" );
else printf ( "False\n" );

You might expect things to follow this order: $0 \:\&\: 6 = 0$ and $0 \:!= 7$, so "True" will be output. But due to precedence of operators, the output comes out "False". First $6\: != 7$ is checked. This is true, so $1$ is returned. Next $0 \:\&\:1$ is performed which is $0$.

The best way to avoid these kind of mishaps is to use brackets whenever you are using bitwise operators. The correct way to write the code above is:
if ( (0 & 6) != 7 ) printf ( "True\n" );
else printf ( "False\n" );

This prints "True" which is our desired result.

## Conclusion

These are the basics of bit manipulation and by no means the end of it. There are lots of other tricks that are yet to be seen, such as "Check Odd or Even", "Check Power of Two", "Right Most Bit". We will look into them some other day.

## Reference

1. forthright48 - Bitwise Operators
2. CPPReference - C++ Operator Precedence

## Thursday, August 27, 2015

### Bitwise Operators

We know about arithmetic operators. The operators $+,-,/$ and $\times$ adds, subtracts, divides and multiplies respectively. We also have another operator $\%$ which finds the modulus.

Today, we going to look at $6$ more operators called "Bitwise Operators". Why are they called "Bitwise Operators"? That's because they work using the binary numerals (bits, which are the individual digits of the binary number) of their operands. Why do we have such operators? That's because in computers all information is stored as strings of bits, that is, binary numbers. Having operators that work directly on them is pretty useful.

We need to have a good idea how Binary Number System works in order to understand how these operators work. Read more on number system in [1]Introduction to Number Systems. Use the $decimalToBase()$ function from [1] to convert the decimal numbers to binary and see how they are affected.

## Bitwise AND ($\&$) Operator

The $\&$ operator is a binary operator. It takes two operands and returns single integer as the result. Here is how it affects the bits.

$0 \: \& \: 0 = 0$
$0 \: \& \: 1 = 0$
$1 \: \& \: 0 = 0$
$1 \: \& \: 1 = 1$

It takes two bits and returns another bit. The $\&$ operator will take two bits $a, b$ and return $1$ only if both $a$ AND $b$ are $1$. Otherwise, it will return $0$.

But that's only for bits. What happens when we perform $\&$ operation on two integer number?

For example, what is the result of  $A \: \& \: B$ when $A = 12$ and  $B =10$?

Since $\&$ operator works on bits of binary numbers we have to convert $A$ and $B$ to binary numbers.

$A = (12)_{10} = (1100)_2$
$B = (10)_{10} = (1010)_2$

We know how to perform $\&$ on individual bits, but how do we perform $\&$ operation on strings of bits? Simple, take each position of the string and perform and operations using bits of that position.

$1100$
$\underline{1010}\: \&$
$1000$

Therefore, $12 \: \& \: 10 = 8$.

In C++, it's equivalent code is:
printf ("%d\n", 12 & 10 );

## Bitwise OR ($|$) Operator

The $|$ operator is also a binary operator. It takes two operands and returns single integer as the result. Here is how it affects the bits:

$0 \: | \: 0 = 0$
$0 \: | \: 1 = 1$
$1 \: | \: 0 = 1$
$1 \: | \: 1 = 1$

The $|$ operator takes two bits $a, b$ and return $1$ if $a$ OR $b$ is $1$. Therefore, it return $0$ only when both $a$ and $b$ are $0$.

What is the value of $A\:|\:B$ if $A=12$ and $B=10$? Same as before, convert them into binary numbers and apply $|$ operator on both bits of each position.

$1100$
$\underline{1010}\: |$
$1110$

Therefore $12\:|\:10 = 14$.
printf ( "%d\n", 12 | 10 );

## Bitwise XOR ($\wedge$) Operator

Another binary operator that takes two integers as operands and returns integer. Here is how it affects two bits:

$0 \: \wedge \: 0 = 0$
$0 \: \wedge \: 1 = 1$
$1 \: \wedge \: 0 = 1$
$1 \: \wedge \: 1 = 0$

XOR stands for Exclusive-OR. This operator returns $1$ only when both operand bits are not same. Otherwise, it returns $0$.

What is the value of $A\:\wedge\:B$ if $A=12$ and $B=10$?

$1100$
$\underline{1010}\: \wedge$
$0110$

Therefore, $12\:\wedge\:10 = 6$.

In mathematics, XOR is represented with $\oplus$, but I used $\wedge$ cause in C++ XOR is performed with $\wedge$.
printf ( "%d\n", 12 ^ 10 );

## Bitwise Negation ($\sim$) Operator

This is a unary operator. It works on a single integer and flips all its bits. Here is how it affects individual bits:

$\sim\:0 = 1$
$\sim\: 1 = 0$

What is the value of $\sim \: A$ if $A = 12$?

$\sim \: (1100)_2 = (0011)_2 = (3)_{10}$

But this will not work in code cause $12$ in C++ is not $1100$, it is $0000...1100$. Each integer is $32$ bits long. So when each of the bits of the integer is flipped it becomes $11111...0011$. If you don't take unsigned int, the value will even come out negative.
printf ( "%d\n", ~12 );

## Bitwise Left Shift ($<<$) Operator

The left shift operator is a binary operator. It takes two integers $a$ and $b$ and shifts the bits of $a$ towards LEFT $b$ times and adds $b$ zeroes to the end of $a$ in its binary system.

For example, $(13)_{10} << 3 = (1101)_2 << 3 = (110100)_2$.

Shifting the bits of a number $A$ left once is same as multiplying it by $2$. Shifting it left three times is same as multiplying the number by $2^3$.

Therefore, the value of $A << B = A \times 2^B$.
printf ( "%d\n", 1 << 3 );

## Bitwise Right Shift ($>>$) Operator

The $>>$ Operator does opposite of $<<$ operator. It takes two integer $a$ and $b$ and shifts the bits of $a$ towards RIGHT $b$ times. The rightmost $b$ bits are lost and $b$ zeroes are added to the left end.

For example, $(13)_{10} >> 3 = (1101)_2 >> 3 = (1)_2$.

Shifting the bits of a number $A$ right once is same as dividing it by $2$. Shifting it right three times is same as dividing the number by $2^3$.

Therefore, the value of $A >> B = \lfloor \frac{A}{2^B} \rfloor$.
printf ( "%d\n", 31 >> 3 );

## Tips and Tricks

1. When using $<<$ operator, careful about overflow. If $A << B$ does not fit into $int$, make sure you type cast $A$ into $long\:long$. Typecasting $B$ into $long\:long$ does not work.
2. $A \:\&\:B \leq MIN(A,B)$
3. $A\:|\:B \geq MAX(A,B)$

That's all about bitwise operations. These operators will come useful during "Bits Manipulation". We will look into it on next post.

## Problem

Given $n$, calculate the sum $LCM(1,n) + LCM(2,n) + ... + LCM(n,n)$, where $LCM(i,n)$ denotes the Least Common Multiple of the integers $i$ and $n$.

## Solution

I recently solved this problem and found the solution really interesting. You can find the formula that solves this problem on OEIS. I will show you the derivation here.

In order to solve this problem, you need to know about Euler Phi Function, finding Divisor using Sieve and some properties of LCM and GCD.

### Define SUM

Let us define a variable SUM which we need to find.

$SUM = LCM(1,n) + LCM(2,n) + ... + LCM(n,n)$ (take $LCM(n,n)$ to the other side for now )
$SUM - LCM(n,n) = LCM(1,n) + LCM(2,n) + ... + LCM(n-1,n)$

We know that $LCM(n,n) = n$.

$SUM - n = LCM(1,n) + LCM(2,n) + ... + LCM(n-1,n)$ ($eq 1$)

$SUM - n = LCM(1,n) + LCM(2,n) + ... + LCM(n-1,n)$ (Reverse $eq 1$ to get $eq 2$)
$SUM - n = LCM(n-1,n) + LCM(n-2,n) + ... + LCM(1,n)$ ( $eq 2$ )

No what will we get if we add $eq 1$ with $eq 2$? Well, we need to do more work to find that.

### Sum of $LCM(a,n) + LCM(n-a,n)$

$x = LCM(a,n) + LCM(n-a,n)$
$x = \frac{an}{gcd(a,n)} + \frac{(n-a)n}{gcd(n-a,n)}$ ($eq 3$)

Arghh. Now we need to prove that $gcd(a,n)$ is equal to $gcd(n-a,n)$.

If $c$ divides $a$ and $b$, then, $c$ will divide $a+b$ and $a-b$. This is common property of division. So, if $g = gcd(a,n)$ divides $a$ and $n$, then it will also divide $n-a$. Hence, $gcd(a,n)=gcd(n-a,n)$.

So $eq 3$ becomes:

$x = \frac{an}{gcd(a,n)} + \frac{(n-a)n}{gcd(a,n)}$
$x = \frac{an + n^2 -an}{gcd(a,n)}$.
$x = \frac{n^2}{gcd(a,n)}$.

Now, we can continue adding $eq 1$ with $eq 2$.

$SUM - n = LCM(1,n) + LCM(2,n) + ... + LCM(n-1,n)$ ($eq 1$)
$SUM - n = LCM(n-1,n) + LCM(n-2,n) + ... + LCM(1,n)$ ( $eq 2$ Add them )
$2(SUM-n)= \frac{n^2}{gcd(1,n)} + \frac{n^2}{gcd(2,n)} + ... \frac{n^2}{gcd(n-1,n)}$
$2(SUM-n ) = \sum_{i=1}^{n-1}\frac{n^2}{gcd(i,n)}$
$2(SUM-n ) = n\sum_{i=1}^{n-1}\frac{n}{gcd(i,n)}$  ( take $n$ common )

### Group Similar GCD

What are the possible values of $g = gcd(i,n)$? Since $g$ must divide $n$, $g$ needs to be a divisor of $n$. So we can list the possible values of $gcd(i,n)$ by finding the divisors of $n$.

Let $Z = n\sum_{i=1}^{n-1}\frac{n}{gcd(i,n)}$. Now, every time $gcd(i,n) = d$, where $d$ is a divisior of $n$, $n \times \frac{n}{d}$ is added to $Z$. Therefore, we just need to find, for each divisor $d$, how many times $n \times \frac{n}{d}$ is added to $Z$.

How many values $i$ can we put such that $gcd(i,n) = d$? There are $\phi(\frac{n}{d})$ possible values of $i$ for which we get $gcd(i,n)=d$. Therefore:

$2(SUM-n ) = n\sum_{i=1}^{n-1}\frac{n}{gcd(i,n)}$
$2(SUM-n ) = n\sum_{d\:|\:n, d \neq n } \phi(\frac{n}{d}) \times \frac{n}{d}$ (but, $\frac{n}{d}$ is also a divisor of $n$ )
$2(SUM-n ) = n\sum_{d\:|\:n, d \neq 1 } \phi(d) \times d$ ( when $d = 1$, we get $\phi(1)\times 1$ )
$2(SUM-n ) = n( \sum_{d\:|\:n } ( \phi(d) \times d ) -1 )$
$2(SUM-n ) = n \sum_{d\:|\:n } (\phi(d) \times d ) - n$
$2SUM - 2n + n = n\sum_{d\:|\:n } \phi(d) \times d$
$2SUM - n = n\sum_{d\:|\:n } \phi(d) \times d$
$$2SUM = n( \sum_{d\:|\:n } \phi(d) \times d )+ n \\2SUM = n ( \sum_{d\:|\:n } ( \phi(d) \times d ) + 1 )\\ \therefore SUM = \frac{n}{2} ( \sum_{d\:|\:n } ( \phi(d) \times d ) + 1 )$$
Using this formula we can solve the problem.

## Code

#include <bits/stdc++.h>

#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)

using namespace std;
typedef long long vlong;

vlong res[1000010];
vlong phi[1000010];

void precal( int n ) {
///Calculate phi from 1 to n using sieve
FOR(i,1,n) phi[i] = i;
FOR(i,2,n) {
if ( phi[i] == i ) {
for ( int j = i; j <= n; j += i ) {
phi[j] /= i;
phi[j] *= i - 1;
}
}
}

///Calculate partial result using sieve
///For each divisor d of n, add phi(d)*d to result array
FOR(i,1,n){
for ( int j = i; j <= n; j += i ) {
res[j] += ( i * phi[i] );
}
}
}

int main () {
precal( 1000000 );

int kase;
scanf ( "%d", &kase );

while ( kase-- ) {
vlong n;
scanf ( "%lld", &n );

///We already have partial result in res[n]
vlong ans = res[n] + 1;
ans *= n;
ans /= 2;

printf ( "%lld\n", ans );
}

return 0;
}

We nee to precalculate partial result using a sieve for all values of $N$. Precalculation has a complexity of $O(N\: lnN)$. After pre-calculation, for each $N$ we can answer in $O(1)$.

## Reference

1. OEIS - A051193

## Tuesday, August 25, 2015

### Contest Analysis: BUET Inter-University Programming Contest - 2011, UVa 12424 - 12432

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 on 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 have 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 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 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)$.

## UVa 12426 - Counting Triangles

Complexity: $O(N^2\:logN)$
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 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 first BS and $n-1-m$ in second case.

Careful about not adding a degenerate triangle. Hanlde the edge cases properly.

## 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 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 second pile and put me back to 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 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})$

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 edge 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. 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 ) \:\%\: 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 ) \: \% \: 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 \: \% \: 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 values from $0$ to $k-1$, we are not able to handle all possible values $c$ any more. 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

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 in 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 value greater or equal to $x$. How do we decide that a valid assignment of guard 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 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 bicolorable. So all we need to do is check if the graph is bicolorable.

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.

## UVa 12431 - Happy 10/9 Day

Complexity: $O(\:(logN)^2\:)$
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} ) \: \%\: M$
$( d ( b^0 + b^1 + b^2 + ... + b^{n-1} ) ) \: \%\: M$.

Therefore, the problem boils down to finding the value of $( b^0 + b^1 + b^2 + ... + b^{n-1} ) \: \%\: 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 conquor. 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 arithmatic with the whole things. Also note that $M$ can be as larg 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 metho to multiply them.

## UVa 12432 - Inked Carpets

Complexity:
Category:

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

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

## Thursday, August 20, 2015

### Contest Analysis: IUT 6th National ICT Fest 2014, UVa 12830 - 12839

I participated in this contest last year. Our team "NSU Shinobis" managed to solve 5 and placed in 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.

## UVa 12830 - A Football Stadium

Complexity: $O(N^3)$

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

## UVa 12831 - Bob the Builder

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

## UVa 12832 - Chicken Lover

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

## UVa 12833 - Daily Potato

Complexity: $O(26 \times N)$
Category: String, Manacher's Algorithm

For each query, we have to count the number of palindromes which are 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?