Contest Link: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=103450#overview

This editorial was written by atrista. I am just posting in CF.

Problem A:

Problem summary: Given a n * m grid G, we have to go from top-left corner to bottom right corner where the cost of stepping to cell (i, j) is denoted by G[i][j] which is always positive.

Solution: We can use straight-forward Dijkstra for this problem. Simple Dijkstra with starting node (0, 0) with initial cost of G[0][0] and ended on (n - 1, m - 1) will do the job.

One of the participant, moudud99's code: http://paste.ubuntu.com/14416006/

Problem B:

Problem Summary: Given a list of walls and doors, we have to find shortest path from cell(0, 0) to a cell(x, y) where cost is corresponded to number of doors we have to pass through out the path.

Solution: The main issue in the problem is certainly graph construction. We are given a list of walls either horizontal or vertical. We can represent the graph like this

int grid[N][N][4]; where grid[i][j][l] = 0 / 1 / 2. if 0, nth side of cell (i, j) doesn’t have a wall nor its a door, if 1, then it has wall, if 2 is a wall. We can assume if l=0 then the direction is up, if l=1 then the direction is left, if l=2 then the direction is right, if l=3 then direction is down. When we get a vertical update, we update both grid[i][j][1] and grid[i][j - 1][2]. For a horizontal update, we update both grid[i][j][3] and grid[i - 1][j][0].

After that we can use a variant of bfs where we fill the wall and door separated and consider them as a single node. Or we can just use a Dijkstra and do this simple we do in simple graph.

A code that follows the bfs idea: http://paste.ubuntu.com/14417087/

One of the participant, Anindya_Buet’s code: http://paste.ubuntu.com/14417071/

Problem C:

Problem Summary: Given a weighted graph G, where weight can be negative, we have to find out if there is a negative cycle in the graph.

Solution: We can use Bellman Ford algorithm for this task. We know, for a graph of n nodes, if there is no negative cycle the length of the path can have almost n nodes which are added by n - 1 iterations. If after another extra iteration we can reduce the cost for any node then, there exists a negative cycle.

A very simple code that follows the idea from IOI_ruhanhabib39’s who solved the problem: http://paste.ubuntu.com/14417177/

Problem D:

This is one of the most elegant problems of the contest.

Problem Summary: Given a graph and a sequence of node, we have to simulate the effect of removing nodes and corresponding edges in the graph and have to output the sum of cost of all pair shortest paths.

Solution: We need a good understanding of Floyd Warshall algorithm for this problem. Floyd Warshal relaxes a path between all pair of nodes using an intermediate node. The order of relaxation is dependent on the sequence by which the nodes are removed. But as simulating the removing is tough, so we calculate the result from backward and starting with an empty graph we simulate adding nodes in reverse.

Code that follows the idea: http://paste.ubuntu.com/14417195/

Code from participant Anindya_Buet: http://paste.ubuntu.com/14417349/

Problem E:

This used to be my most favourite problem from the contest set.

Solution: Instead of just calculating the path with maximum probability of a packet successfully getting through, we can simple calculate the path with minimum probability of a packet not getting through. After that, this is simple expectation calculation.

Code that follows this idea: http://paste.ubuntu.com/14417450/

Code from participant Anindya_Buet: http://paste.ubuntu.com/14417472/

moinul.shaon's comment:

Use dijkstra to calculate minimum probability p. So expected time for unit data E is E = p * 2k + (1 - p) * (2k + E). Solve it and you will get E = 2k / p for unit data. So for S data answer is 2kS / p

Problem F:

Simple Miser Nim game.

Solution: Miser Nim is a Nim game unless all pile size is 1. If all pile sizes are 1 then this is simply a odd even game.

Code from participant IOI_tasmeemreza : http://paste.ubuntu.com/14417512/

Problem G:

Solution: This is exactly a Nim game where the pile size in just the distance between gray and white pieces.

Code: http://paste.ubuntu.com/14417564/

Problem H:

Solution: This is a problem of finding Grundy number. A great analysis of this problem can be found in topcoder: https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/ Notice the Composite games – Grundy numbers section.

We simply calculate the grundy number for n*n grid and simply xor the grundy numbers for cells where the hyper knights are.

Instead of just calculating Grundy for every case, we can precalc it.

Code from participant nmunim : http://paste.ubuntu.com/14417606/

Problem I:

Solution: This is simply game theory themed DP problem. Let dp[i] be 0/1. dp[i] = 1 if there at least 1 winning state from this for the player no matter who is playing, with i stones.

So, dp[i] = 1 if any of dp[i - a[j]] = 0 where a[j] denotes a legal move. So, if dp[n] = 1 then Stan wins else Ollie wins.

Code from participant moudud99: http://paste.ubuntu.com/14417642/

Problem J:

Solution: In this type of game problem, then we are dividing the pile into two or more piles then the grundy numbers that are affecting the grundy of initial pile is xor of the child piles.

So, for pile size x, grundy[x] is the smallest number that isn’t in the set consisted of grundy[i] xor grundy[x - i] where i <  = x / 2 and not equals x - i.

Then we simply xor the grundy numbers corresponded to the pile size.

Code implementing the following idea from zawadabdullah : http://paste.ubuntu.com/14417707/

Thank you.

contest link : http://acm.hust.edu.cn/vjudge/contest/view.action?cid=103408#overview

I was gonna write an editorial anyway. Thought here would be easier and some CF users might benefit from these too. Here goes:

Problem A:

This is a dynamic programming problem. Suppose i am to find number of pattern of wall length N and i have already calculated pattern all values for x < N. Now if i place a vertical brick after any pattern of length N - 1, we get a pattern of length N. Again if i place two horizontal brick (one above another) after any pattern of length N - 2, we get a pattern of length N. It is apparent that there is no double counting.

Say dp[N] denotes the number of patterns of length N. So dp[n] = dp[n - 1] + dp[n - 2].

Base cases are for n = 1, dp[n] = 1 and for n = 2, dp[n] = 2 ; which can be calculated manually or from the given test cases. Make sure to use long long, as int will not hold the answer.

solution : http://paste.ubuntu.com/14401595/

Problem B:

This is a dynamic programming problem.

First observation is that you actually have unlimited number of each type coin. You need to make K and you have K coin of each type. So you will never run out of coin.

say dp[x][y] is the number of way to make y using first x coin. The recurrence relation is:

dp[x][y] = dp[x - 1][y] + dp[x][y - valueofXthcoin]

This means that, I have two option:

1. I dont take the xth coin ( dp[x - 1][y] ) to make value y.

2. I take the xth coin to make dp[x][y] from dp[x][y - valueofXthcoin].

I hope, you can figure out the base case here. value 0 can be made only one way.

solution : http://paste.ubuntu.com/14401682/

Problem C:

After some thinking and seeing some example, you can realize that, the solution is the LCS between the string and its reverse string. Its straightforward to get LCS of two string. Be careful of empty string.

solution : http://paste.ubuntu.com/14401762/

Problem D:

This is a bitmask dp problem. Make a "oo-" -> "--o" or "-oo" -> "o--" and recursively calculate. Here o/- can be represented by the 0/1 bit of a number, which gives a recursive dp.

solution : http://paste.ubuntu.com/14401916/

Problem E:

This here is a very good explanation :

https://www.quora.com/How-do-I-solve-Mixtures-MIXTURES-on-SPOJ

solution: http://paste.ubuntu.com/14402002/

Problem F:

Simulate stack,queue and priority queue. If it satisfies more than one DS-> "not sure". If satisfies none "impossible". Otherwise print the name of the DS.

Solution: http://paste.ubuntu.com/14402150/

Problem G:

This problem can be solved by DFS/BFS. But the intended solution (as part of DS contest), union_find AKA Disjoint_set_union. Initially every node has size 1. When combining two component x and y, say i am gonna point from x to y. so add size of x to size of y.

Solution: http://paste.ubuntu.com/14402226/

Problem H:

Standard range sum query problem with update. Read about segment tree/BIT.

Solution: http://paste.ubuntu.com/14402317/

Problem I:

Similar to range maximum query with update, the only difference is that you need to also maintain the 2nd largest number with the largest number.

Solution: http://paste.ubuntu.com/14402614/

Problem J:

This is the hardest problem of the set. This problem requires the mixture of both DP & DS. Different DS can be used depending on the approach. But i am gonna discuss the approach with stack. This problem is a great example that even such a simple DS as stack can solve tough problems.

calculate from right to left of the array. suppose i am at index x of the array and rightside of this index, all values are calculated. A Stack will maintain whoever is alive on the right. Now x will try to kill to whoever is alive on right of him ,suppose y. If x can kill y, then dp[x] = max(1 + dp[x], dp[y]). Because x requires one extra second to kill y who survived thus far (thats why 1 + dp[x]). But stable time of y, dp[y] was calculated before and may have killed many psychos, but y might have been killed before that time by x. So if y killed more psychos than 1 + dp[x] that means x have to kill extra dp[y] - (1 + dp[x]), which means time required is dp[y] - (1 + dp[x]) + (1 + dp[x]) = dp[y]. The value of dp[y] will not be needed later (as dp[x] will be atleast as large as dp[y]), so dont have to worry about updating it. Pop y from stack and calculate again.

Solution: http://codeforces.me/contest/319/submission/15081127

Problem K:

Count the number of 1 bit in a numbers binary representation. Print Odd/Even.

Solution: http://paste.ubuntu.com/14402661/

Thank you.

Problem Link: http://uva.onlinejudge.org/external/120/12003.html

I have solved this problem using sqrt decomposition and treap . In sqrt decomposition per query cost is O() and treap is O( log(n)*log(n) ) . Both of my method took ~3.3s and ~4.5s respectively . I want to know if there is any faster method as there seems to be ~1s solution on the statistics.

Thanx :)