can you please share your code for the READCOST Problem? The editorials are not available and the solutions from the replay are also not public.

VASTLIFE was also a copy of a Google Foo Bar Challenge. So yeah. Very lazy problem setting.

https://mirror.codeforces.com/blog/entry/64035

We were also affected similarly. We made 4 submissions and wasted nearly 30 mins before seeing our first submission getting AC. I complained but to no avail.

Same thoughts

Yes, the official results which were declared are different from the current results.

Yes. He said that in Kanpur regionals as well.

I have also been to Amritapuri regionals, and the problemset there was really good (i.e., testing and required good skills). The gwalior problemset was really not good. Such a thing is not acceptable for ACM-ICPC, and CC must take care of it in future...

Then you might be knowing it already if you are from codechef, don't you?

The idea is to consider acceptable AND values of the final path, which must be  ≥ K. For a particular AND value x, you can find the shortest path in the graph with Dijkstra considering only edges that have v as "supermask" of x (v & x = x). This is a candidate answer.

But you don't need to repeat this for all x ≥ K. There will be only a few "minimal" x for which you must find the shortest path, because if a x is acceptable then all supermasks of x will also be acceptable. You can find these minimal x by flipping exactly one 0 in K to 1 and 0-ing all lower bits. x = K must also be checked. As an example, for K = 001101, you must try x = {100000, 010000, 001110, 001101}. So you would have to run Dijkstra ~30 times to find the overall answer.

And it has been a monopoly so far xD

Also Indian regionals are the easiest to get to the WF as well.! :D

yes its true ,not only for indians but for many in the community, because system for calculating contribution is weird i think so,becos how the hell? Ashishgup has contributed more than tourist,Petr,rng_58,neal,etc for the community? in my opinion ,contribution should only be calculated by any editorial or educative discussing comment ....

Some fake Indian accounts that don't admit their fault

I'm not crying about anything, and I never said anything about being eligible to qualify for World Finals. I'm just posting a discussion blog and stating what happened.

PS: I know I'm not close to qualifying for World Finals.

For those of you who think I'm making this blog for contribution, I'm not. I just made one because nobody else did in the past 10 days.

I guess we both can agree that ashish is a karmawhore.

Codechef's discuss is so awful that it's more likely that the CC admins will answer on CF

So you're not the regional director for Kharagpur after all!

What is this refraction stuff?The problem is this.

Now you have to go from the house to the river and then to the land. So basically you have to cover some distance with empty bucket(k times faster) and the remaining distance with water(k times slower). You will obviously fill the water from the river at some point between the lines dh and dl. So the path will be go from house to this point and then from this point to the land.

Since there is a factor of k binary search the most optimal point at which you should fill the bucket. Once you get the point calculate the distance appropriately.

The question asks for minimising the time and not the distance so this approach cannot be used.

My approach involved ternary searching along the river to find the optimal point from where minimum time will be taken.

I have used binary search and Snell's law to solve the problem. Basically, I take a distance from the base and find the corresponding sin(i) and sin(r). Then, I compare sin(i)/sin(r) to k and do a binary search as it is a monotonous function.

https://www.codechef.com/viewsolution/22050337

5,6,7,8 AIex_2oo8 can only h8

SORRY.

Why are this all haters are ignoring the fact that it is true CC has rrally messed up experience of the candidates. Team ToLazyToPropagate was 2nd in kolkata regional but after changing AC to WA they are 3rd and might miss the chance to WF. If the judgement was right at that time they could have performed well to maintain their rank. Instead of saying he just wants contribution say CC gave him chance to do so and no one else had balls to put this up so he did. There is nothing wrong in it.

I think codeforces should start banning accounts like quora does.

Thanks for opening my eyes Swisknife.

We are sorry for our inappropriate behaviour, Swischeese

Polygon and strings: It is given that the convex hull of the given set of points is the set of points itself. Also no 3 points are in a line and no 2 points have same X or Y coordinate. One more important constraint is that in the solution no line segment should intersect with other line segment. Imagine you sorted the points clockwise/counter clockwise ( does not really matter which ) . We know that our solution has to include all the given points since query length is N-1.

Now imagine you have taken the 1st point in the answer to be the jth point in the sorted order. what can be the possibilities for the 2nd point? If you take the Kth point in sorted order and there are >0 number of points between jth to kth point AND >0 points in between kth to jth point ( points array is circular so there are two intervals between jth and kth points ), then at some point in the future you will have to intersect the segment j to k because you must cover all points.

What this tells us is that after taking jth point the only possibilities for the next point are j+1 or j-1. Which tells us that at any instant, the set of "taken" points forms a contiguous segment in the sorted order. If the segment L to R is taken then the next point can be either R+1 or L-1 and nothing else. However,information which one of L and R was placed in previous step is also needed. this leads us to a simple DP solution bool dp[which][L][R] where "which" tells us if L was placed in previous step or R. dp array tells us whether it is possible to proceed with these parameters or not. To print the actual solution just store the optimal next moves for each state. Total time complexity is n*n*m, given constraint on n*m makes this solution optimal.

Flipping polygons: I do not know why the setter has given Fibonacci numbers in the problem. Interpret updates in this manner: instead of rotation points, let us rotate the y axis. So the y axis will have a direction, and a counter indication which point (or side in case when N is even) it is passing through. So rotate polygons in L to R by X rotations means basically adding X to all elements in L to R. However if some polygon is flipped X rotations mean subtracting X from it counter instead of adding.Fortunately, this can be done using a single segment tree with some smart lazy propagation. I recommend you to look at the AC codes on codechef in the replay contest ( look for the ones which have a single seg-tree). The code is quite simple to understand.

A tile with number S can be formed: This means that atleast one of X or Y is of the form S / (2^k).

X and Y are not divisible by each other: This (along with the previous statement) means that exactly one of X or Y can lead to S.

Assume X can lead to S in 2^k moves. Expected number of turns before you get an X is 1 / p. So expected number of turns to get 2^k X's is 2^k / p.

Do a similar analysis for Y (replace p by 1 — p).

Use 0-1 BFS while maintaining the set of colors of previous edges(corresponding to only shortest path) for each node. Code

Another approach is as follows: Modify the given graph as follows. For each node present in the graph, make some copies of the node equal to the number of distinct colors attached to it. Let the copies of the node (say u) be numbered v1, v2, ... , vk. Connect these nodes to u with weight 1. These edges represent changing of color. Now, for an edge some color, connect their corresponding copies with weight 0. Now, run any shortest path algorithm from S to T and let it be L. So, ans = (L — 2) / 2. Complexity: O(n + m) if you use 0-1 BFS, or O((n + m) * log(n + m)) if you use dijkstra. See my code: https://www.codechef.com/viewsolution/22043601.

First observation which is really important here is that for a number Ai in the array, say it's prime factorization is Ai = p1 * p2 * .. * pk. Then, you can treat each prime as a different pile and solve. You can consider the moves as choosing a prime factor of Ai and replacing it with some number x which can in turn be decomposed into more piles. Now, basically you have to calculate the grundy of a prime number. Another observation is that the grundy of the kth prime number is k. Why? This is because from a prime p, you can go to any prime less than p and 1 itself. So when you do the mex operation, grundy comes out to be k. See the code: https://www.codechef.com/viewsolution/22010093.

We just need the areas of the closed regions formed by the fences. (The answer then is just the sum of squares of areas over the total area.) Imagine that all of the rectangles' edges are extended both ways — the field now looks like a grid of kit-kat pieces. Any regions formed by the fences must be a disjoint union of these small pieces of land, which are only at most O(k^2). So we can use a DSU / perform a DFS to join adjacent pieces of land that don't have a fence between them.

Consider any valid walk. The i^th edge on the walk and the i^th edge from the end have the same character on them. So try building the walk from both directions. Define dist[a][b] as sum of lengths of the shortest walks from s to a and from t to b such that the concatenation of the (ordered) edge set of these walks is a palindrome. Then min(dist[x][x]) gives us the shortest even length walk. Odd length walks can be considered by enumerating every edge in the graph.

Indian Regionals are a joke.

As much as I agree with you, unfortunately ICPC rules state that "In consultation with the judges, the Regional Contest Director determines the winners of the regional contest. The regional contest director and judges are empowered to adjust for or adjudicate unforeseen events and conditions. Their decisions are final."

It's really sad we can't do anything.

Just pure mathematics. Find the intersection of lines in all 4 directions and check the coordinates of that point to the boundary condition of the square.

Anyone please?