SPOJ GUANGGUN

Problem link: SPOJ Problem Set (classical): 9952. 111…1 Squared

Interesting and fun problem. This is one of those problems that you can sense a pattern from miles away. Just do some bruteforce and print the patterns. You can use pen and paper too, but Python is surely a better option when you have it. All I did is write some bruteforce in my python interpreter, and the pattern is instantly visible, here is the output of f(n)² for n = 1 to 50:

1
121
12321
1234321
123454321
12345654321
1234567654321
123456787654321
12345678987654321
1234567900987654321
123456790120987654321
12345679012320987654321
1234567901234320987654321
123456790123454320987654321
12345679012345654320987654321
1234567901234567654320987654321
123456790123456787654320987654321
12345679012345678987654320987654321
1234567901234567900987654320987654321
123456790123456790120987654320987654321
12345679012345679012320987654320987654321
1234567901234567901234320987654320987654321
123456790123456790123454320987654320987654321
12345679012345679012345654320987654320987654321
1234567901234567901234567654320987654320987654321
123456790123456790123456787654320987654320987654321
12345679012345679012345678987654320987654320987654321
1234567901234567901234567900987654320987654320987654321
123456790123456790123456790120987654320987654320987654321
12345679012345679012345679012320987654320987654320987654321
1234567901234567901234567901234320987654320987654320987654321
123456790123456790123456790123454320987654320987654320987654321
12345679012345679012345679012345654320987654320987654320987654321
1234567901234567901234567901234567654320987654320987654320987654321
123456790123456790123456790123456787654320987654320987654320987654321
12345679012345679012345679012345678987654320987654320987654320987654321
1234567901234567901234567901234567900987654320987654320987654320987654321
123456790123456790123456790123456790120987654320987654320987654320987654321
12345679012345679012345679012345679012320987654320987654320987654320987654321
1234567901234567901234567901234567901234320987654320987654320987654320987654321
123456790123456790123456790123456790123454320987654320987654320987654320987654321
12345679012345679012345679012345679012345654320987654320987654320987654320987654321
1234567901234567901234567901234567901234567654320987654320987654320987654320987654321
123456790123456790123456790123456790123456787654320987654320987654320987654320987654321
12345679012345679012345679012345679012345678987654320987654320987654320987654320987654321
1234567901234567901234567901234567901234567900987654320987654320987654320987654320987654321
123456790123456790123456790123456790123456790120987654320987654320987654320987654320987654321
12345679012345679012345679012345679012345679012320987654320987654320987654320987654320987654321
1234567901234567901234567901234567901234567901234320987654320987654320987654320987654320987654321
123456790123456790123456790123456790123456790123454320987654320987654320987654320987654320987654321

Beautiful, isn't it?

SPOJ DCEPC206

Problem link: SPOJ Problem Set (classical): 10810. Its a Murder!

Given a sequence of integers (at most 10⁵ integers ranging from 0 to 10⁶. You have to go from left to right, and for each position, you have to add the sum of all the numbers before current position which are strictly smaller than the number in current position.

Well, if the numbers where sorted, then we could do it more easily, i.e. keep an array for cumulative sum, and then calculate the answer in O(n) time. However, this is not the case. So, what can we do? According the problem, you have to maintain the cumulative sum anyway. So for each number in the sequence, if we keep adding them one by one, we can break down the problem in two parts. Let's think of a data structure which keeps cumulative sums, and we can add numbers anywhere and still maintain the sum. Segment tree / or binary indexed tree could come handy in this situation, where, the later one is more straight forward and less memory hungry. Now the steps are:

1 ⇒ Query: When a number is to be added, what is the sum of numbers smaller than current one? Note, as we are adding one by one in the order they appear, so the question whether there are any numbers which came after current number is eliminated. It is guaranteed that, when you are adding the i^th number, all the numbers already present in the data-structure came before position i.

2 ⇒ Update: Once you have taken the partial sum for current number, it is now time to add the number in proper place, and update the cumulative sum structure. Here, clearly, appropriate position means, the position where the number would be placed when sorted. Now, we can do two things here. (a), we can sort the number and give each number an unique id to indicate its position in the sorted array. And (b), as the numbers are up to 10⁶, we can use the numbers as their indices or positions in the sorted array. It is faster and the memory overhead is not that of a big issue here.

Now, here are two more things to be taken care about, (a), there can be duplicate numbers, and (b), 0 can be present in the input sequence, which can cause some trouble if you use BIT. However, (a) is handled naturally, because the problem wanted you to add only strictly smaller numbers, so it doesn't matter if you add same numbers in the same positions. There will be no query points in-between the equal numbers. And for (b), there is really no need to worry about 0, cause it contributes nothing at all, just ignore 0.

So, the overall algorithm looks like the following:

for each number ai:
    if ai > 0:
        ans += BIT_Query(ai - 1)
        BIT_Update(ai, ai)

Here: BIT_Query(pos) returns the sum up to position pos and BIT_Update(pos, val) adds val in pos in the BIT structure. Solutions involving the segment tree is also similar. Just keep the tree of total sums, whenever you are trying to add a number, read the partial sum, and then update the structure.

Happy coding..

SPOJ ABCLOG

Problem link: SPOJ Problem Set (classical): 17659. Time to get a job

This problem should go to the Riddle section or what-so-ever, not worthy for classical. Just reverse the bit string.

SPOJ POLCONST

Problem link: SPOJ Problem Set (classical): 17707. Constructible Regular Polygons

As stated in the problem description, you are required to utilize this page. As there are only 5 Fermat Primes, you can easily do a pre-processing up to 10⁶ in constant time (2⁵×5) and answer each query in O(1).

SPOJ HOLI

Problem link: SPOJ Problem Set (classical): 9942. Holiday Accommodation

Given a weighted tree, consider there are N people in N nodes. You have to rearrange these N people such that everyone is in a new node, and no node contains more than one people and maximizes the cost. Here cost is the distance travelled for each person.

First observation is, in order to maximize cost, all edges will be used to travel around. So, if we can calculate how many times each edge will be used, we can calculate the cost.

Now for any edge E_i, we can partition the whole tree into two subtrees, if one side has n nodes, the other side will have N - n nodes. Also, note that, min(n, N-n) people will be crossing the edge from each side. Because if more people cross the edge, then by pigeon-hole principle in one side, we will get more people than available node which is not allowed in the problem statement. So, E_i will be used a total of 2 * min(n, N-n) times.

Thus the final result is:

cost = ∑ 2*min(ni, N-ni)*wieght(Ei) | for each edge Ei

Here, n_i is the count for nodes in one side of the edge E_i and N-n_i on the other side. So, we can use simple DFS algorithm to solve the problem. During the traversal, just count number of nodes in the subtree for an edge u⇒v and calculate result for each edge in the process.

SPOJ PRIMIT

Problem link: SPOJ Problem Set (classical): 211. Primitivus recurencis

Given a list of directed edges or features, we have to find the smallest possible sequence of nodes where all the given edges are present without violating the direction.

Although at first this may seem to be a bipartite matching problem or problem related to strongly connected component. But I am not sure whether this particular problem can be solved using any of those techniques. Here we have two things to observe.

1 ⇒ Ordering for each weakly connected component is independent. So, we can add up the results for each weakly connected component as we can arrange them in any order, because they don't have any node in common.

2 ⇒ The minimum length will be the length of eulerian circuit for each component. We can break the circuit at suitable places to make it a chain. Considering [1], we can break the chain anywhere we want. Because other components have nothing to do with it.

So, for each weakly connected component, it boils down to finding minimum number of edges need to be added to make the component an euler circuit. For each component G_i, we can find the minimum number of additional edges by the following formula (Note, the formula will also handle the components which are already an euler circuit).

Number of additional edges = ∑max( cnt(Gi) / 2, 1 ) for all i

Note: if you already have an euler circuit, i.e. cnt(G_i) = 0, then you still need 1 additional term in the sequence. The simplest example is two edges, 1-2 and 2-1. You will need either 1-2-1, or 2-1-2 sequence.

And to find the value of cnt() for a component G_i, we just add the absolute difference of in and out degree count for each node in that component.

cnt(Gi) = ∑|d+(u) - d-(u)| for each u ∈ Gi
Here, d+(u) ⇒ indegree count for u, and d-(u) ⇒ outdegree count for u.

So, the overall solution outline is something like this, first use disjoint set data structure, or commonly known as union-find to mark the components. You can also use simple DFS / BFS as well. Ofcourse we are ignoring direction in this stage as we want to generate weakly connected components. Then for each node, calculate total indegree and outdegree counts. Now for each component, use the above formula to find additional edges x_add, thus the final answer is N + x_add, here x is the given number of edges.

SPOJ QUEEN

Problem Source: SPOJ Problem Set (classical): 4235. Wandering Queen

Basically you are given a grid with a start and end point along with some obstacles. You have to reach end point using smallest number of standard chess queen moves.

The first idea that pops into mind is using BFS, along with states for 8 direction. In this case, the complexity is around 8 * 256 * 1000 * 1000. Anyone who is a bit familiar with SPOJ engine, knows that, this solution will definitely get a "Time Limit Exceed" verdict.

The catch is, it doesn't matter for a standard chess queen from which direction you reach a particular cell in terms of cost. A queen moves toward 8 directions as long as nothing is blocking her paths and the cost remains the same. So, whenever you reach a cell, you will want to traverse all of the 8 possible directions from that cell. If you maintain the previous direction, the cost will not change, and if you change direction, the cost will be increased by 1. Fortunately, we can maintain the BFS property without keeping extra states for direction simply by adding a parallel flag array and modifying how we choose the next cell.

Although there are 8 possible directions, we have only 2 different scenarios, namely: whether we want to change direction or not. Instead of keeping states for direction changes, we will visit all cells in a particular direction from a specific cell before traversing from other cells and pushing them into a queue as usual. Following this, we can visit all the reachable cells from a particular cell in a single move. During this process, we will store the bit-masked flags for direction in a parallel array. Now, when we meet a new cell, there are four possible scenarios.

1 ⇒ The cell is out of the grid or contain an 'X', simply stop moving in that direction anymore.

2 ⇒ The flag value for this cell already has the bit for current direction set to 1. It means, going in this direction doesn't do anything helpful anymore.

3 ⇒ The flag value for this cell doesn't contain bit for current direction, but it has been visited form different direction earlier. We just skip this cell and continue with the direction. Note: This step is important to understand. Because at first this may seem like, we can just stop here as the cell is already in the queue and will be traversed later. But thinking carefully, you will find out that, your current move will definitely have a lower or equal cost than the current cell which resides in the queue will have (obvious BFS property). So, we may still need to update the rest of the cells following the direction. Although we skip this cell, we update its flag value to mark the direction from which it was visited. See sample case 2, that explains the necessity of this step.

4 ⇒ New cell, we visit it, do regular BFS stuffs like updating cost, pushing into queue, and additionally, we mark the direction from which it was visited in the flag array.

Oh, and ofcourse, flag for the start cell should have all the bits set. Now, we visit each cell at most 8 times for each direction, but we push each cell only once into the queue. Thus, we are able to remove the 256 different bitmasked states, and the solution is more likely to pass the time limit.

Following this procedure, I got accepted in 2.56 with STL queue, and no IO optimization. I am having a feeling that, this problem can be solved more efficiently. So, don't forget to share your idea on this problem.

Repository Transfer

Finally I have removed all of my github repositories. I have been getting request from a lot of people for removing the repositories or making them private. As github charges too much for maintaining private repositories, I have decided to switch to bitbucket, another wonderful free git server. All of my repositories are set as private. Sorry for the inconvenience. There are already plenty of sites where one can find solutions for online judge problems. My repositories were never intended to be known as a place where you get all the beautiful solutions and then just copy-paste them from your account. That is just meaning-less, stupid and of no good use of-course. Still if you want to see any of my noob-ish solutions, please send me an email.

Thanks for understanding and happy problem solving. I think I am now retired from all these beautiful little things. I will miss these programming contests forever...

SPOJ FINDPRM

SPOJ Problem Set (Classical) 5970. Finding Primes

Fun problem! First it wants you to run a sieve from 2 to N, and then do the similar operations starting from N to 2, except, this time, you have to mark the factors of N and then find the next largest N1 not yet marked, then mark factors of N1 and so on... Finally, you have to tell how many numbers will be unmarked by both algorithms up to N.

First observation is, you only need to consider those numbers which are primes, so, we can run a sieve up to 10⁷, which will allow us to test whether a number is prime or not in O(1) time.

Now, for each N, we can pre-calculate the result. Just note that, say if you know ans[n-1] and want to determine ans[n] from it, this inequality will hold |ans[n] - ans[n-1]| <= 1. Because the current N will be added as an unmarked, or there may be a number which you added in the past, will be removed by one of the factors of this N. Or, if N is not a prime, then it will be already removed by the first algorithm i.e. sieve.

If N is a prime number, then no N1 has removed this N already, so in this case the ans[n] = ans[n-1] + 1.

If N is an even number, and if N/2 was a prime, you have added that with your result, but this should be removed at this stage. So in such a case, ans[n] = ans[n-1].

Why don't you need to consider other factors like N/3, N/5 ... ? 2 is the only even prime factor and it can produce even numbers by multiplying other primes with it. For other primes, p = 3, 5 and so on, if N/p is prime, then N cannot be even. So the basic idea is as follows:

for( i = 2; i <= N; i++ ) {
    ans[i] = ans[i - 1];
    if( i is even and i/2 is prime ) ans[i] = ans[i] - 1;
    if( i is prime ) ans[i] = ans[i] + 1;
}

I had absolutely no clue at the first glance. Really nice problem.

Practice Week #1

Problems for this week:

SPOJ::VONNY
SPOJ::PRIMIT
SPOJ::FINDPRM
SPOJ::GRAPHCUT
SPOJ::TPERML
SPOJ::SCITIES
SPOJ::QUERYSTR
SPOJ::PRHYME
SPOJ::STARGATE
SPOJ::MOBIVINA
SPOJ::MDOLLS
SPOJ::MA1
A virtual contest using these problems is hosted on Hust. Follow this link