### cgy4ever's blog

By cgy4ever, 4 years ago, ,

472A - Design Tutorial: Learn from Math

One way to solve this is by bruteforce: there are O(n) different ways to decomose n as sum of two number. If we can check if a number is a prime in O(1) then the whole algorithm can run in O(n). You can use Sieve of Eratosthenes to do the pre-calculation.

And another way is try to prove this theorem. The prove is simple: if n is odd number, then 9 and (n-9) is an answer (n-9 is an even number at least 4, so a composite number), and if n is even number, then 8 and (n-8) is an answer (n-8 is an even number at least 4, also must be a composite number).

This task can be solve by greedy: the k people with highest floor goes together, and next k people with highest floor goes together and so on. So the answer is 2 * ((f[n]-1) + (f[n-k]-1) + (f[n-2k]-1) + ...) .

It is a bit tricky to prove the correctness of greedy, since people can get off the elevator and take it again. We can give a lower bound of the answer by flow analysis: between floor i and floor i+1, there must be no more than (# of f[i] >= i+1) / k times the elevator goes up between these 2 floors, and then there be same number of times goes down. We can find this lower bound matches the answer by above greedy algorithm, so it means the greedy algorithm gives an optimal answer.

472C - Design Tutorial: Make It Nondeterministic

This one laso can be solved by greedy, let's think in this way: let pick one with smallest handle, then we let him/her use min(firstName, secondName) as handle. And go for the next one (2nd mallest handle), now he/she must choose a handle greater than handle of previous person, and if both meet this requirement, he/she can pick a small one.

This time the correctness of this greedy solution can be proved by exchange argument.

Note that if we change the goal of this problem: ask number of different permutations they can get, then it will be very hard. (I tried it for hours but can't solve.)

472D - Design Tutorial: Inverse the Problem

Let's think it in the following way: for the minimal length edge, it must belong the the tree, ..., for the k-th minimal length edge(a, b), if there is already an path between a-b, then it can not be an edge of tree anymore, otherwise it must be edge of tree, why? Because otherwise there must be a path from a to b in the tree, that means a and b can be connected by edges with less length, but a and b is not connected.

So this Kruskal style analysis gives us this theorem: if there is an answer, then the answer must be the MST of that graph. (You can also guess this theorem and try to prove it.)

You can solve MST in O(n^2 log n), and then there are many way to check distance between notes on tree: you can just simply do dfs or bfs from each node, it can run in O(n^2). Or if you have pre-coded LCA algorithm, it can run in O(n^2 log n).

472E - Design Tutorial: Learn from a Game

First let's solve some special cases:

If the initial board and the target board contains different orbs, then there can't be a solution.

If n = 1 (or m = 1), then we can try all O(m^2) (or O(n^2)) possible moves.

And for the other cases, there always have solution. We first hold the orb with number target[1][1] in initial board. Then we want to move other orbs to their position.

So let's come up with a process to move orb from (a, b) to (c, d): it must be some continue path from (a, b) to (c, d), so we want to build a single move: it will move an orb from (a, b) to an adjacent cell (c, d). How to do that? We can move our touching orb to (c, d) first, and then move to (a, b). But there are some concerns: in this move, the touching orb shouldn't pass any already-done cells, and it shouldn't pass (a, b) when we get to (c, d).

That means we need a good order to move orbs. We can do it in this way: first, as long as there are more than 2 rows, we move the orbs to last row (from left to right or right to left). And then it must be 2xm boards: we do it column by column from right to left. We can find that in this order, there always exist paths for our touching orb to get (c, d).

472F - Design Tutorial: Change the Goal

You need to know some knowledge about linear algebra and notice the operation of xor on 32 bit integers equals to + operation in a 32 dimension linear space. If you don't know, you should learn it from the editorial of similar tasks, for example, Topcoder SRM 557 Div1-Hard.

We need to know some basic properties of our operation:

1. we can swap two number a and b by: a^=b, b^=a, a^=b.

2. This operation is inversible, the inverse is itself.

By property 1 we can do the Gaussian elimination of each set of vectors.

By property 2 we can use this way to build an answer: use some operation to make A[] into a base (linear independent vectors that the span will be A[]), then transfer it into a base of B[], then use the inverse of Gaussian elimination to recover B[].

So now we have two bases: {a1, a2, ..., ax} and {b1, b2, ..., by}. If there exists some bi such that it can't be expressed as a linear combination of {a1, a2, ..., ax}, the solution can't exists.

Otherwise there always exists a solution: first we build b1 and put it in the first position. Suppose b1 = a2 ^ a3 ^ a8, then we swap any of them, say, a2 into position one, and then xor it with a3 and a8, then we get b1. Note that after this operation {a1, a2, ..., ax} will remain a base. And we need to ensure we don't erase already-done numbers in a.

472G - Design Tutorial: Increase the Constraints

Let's start with a simpler task: we have string A and B (|A|, |B| <= n), we have q queries and each query we ask the Hamming distance between A and a substring of B with length equals to |A|.

How to solve this? We need to notice compute A with different offset of B is similar to the computation of convolution, so it can be done by FFT.

We use +1 to replace '1' and we use -1 to replace '0', and then we do the convolution of A and reverse B. We can extract the answer of all possible query of "the Hamming distance between A and a substring of B with length equals to |A|."!

Then let's come back to our problem, how to use this way to make a faster solution? We can use a way like sqrt decompose: we divide A into L blocks, for each block, we compute the convolution of this part with B, it will takes O(n*L*logn). And for each query, we can use the pre-calculated results to speedup (if a whole block contains in the query, we can compute it in O(1)). So each query needs no more than O(L) operation.

If n = q then this solution can run in O((n*logn) ^ 1.5). But in practice it has some issues: for example, we can use bit operation to speedup like __builtin_popcount(). I tried to set constraints to fail solution with only bit optimization, but seems I failed: I apologies to allow this kind of solutions passed. (I used __builtin_popcount() to test such solution, but in fact cnt[x<<16] + cnt[x>>16] is much faster than the builtin fucnion)

•
• +137
•

 » 4 years ago, # |   +8 Thanks for fast editorial!
 » 4 years ago, # |   +30 D can be solved in O(N^2). Prim can solve MST in O(N^2) if we don't use priority queue:)
•  » » 4 years ago, # ^ |   +11 Oh, yes, Gerald told me that some days before. :)
•  » » » 4 years ago, # ^ |   +6 Thank you for the interesting problems! I like D problem the best. (I solved it by a different way from editorial.) I have created Puzzle and Dragon solver few years ago but I took so many time to solve E problem.=( I like your problems, so I'm looking forward to a new problem!:D
•  » » » » 4 years ago, # ^ |   0 I'm glad to hear you love my tasks!What is the algorithm of your Puzzle and Dragon solver? Can it solves task E or it only works for the 5x6 grids?
•  » » » » » 4 years ago, # ^ |   +15 It may be able to solve task E by some modification (I write a solution for E problem from empty source code).Because there is time limit in the game, I tried to minimize the number of swaps. (I just write a trivial search.) I uploaded a movie of the solver.
•  » » » » » » 4 years ago, # ^ |   +5 Oh, that video looks so crazy! :)I used to want to write it but it seems not that easy.How did you get the pattern on your phone? (use Computer Vision or you can access the game data from memory?) And how do you do the clicks on your phone?
•  » » » » » » » 4 years ago, # ^ |   +5 I got the pattern from a screenshot and I operated by using ADB (Android Debug Bridge).
•  » » 4 years ago, # ^ |   0 In which way you can use Prim's algorithm without priority queue?
•  » » » 4 years ago, # ^ |   0 find minimal element each time in O(n)
•  » » » 4 years ago, # ^ |   +8 Priority queue is used to find the next vertex in Prim. But you can find the next vertex in O(N) straightforwardly. (Note that you'll find "the next vertex" N times.)
•  » » 4 years ago, # ^ |   0 It can be solved in O(n^2) even without using Prim.Firstly, lets make the 0 vertex as a root and add it to the tree. After that, sort the first row of input (weights of edges connected with the 0 vertex) and lets add vertices to our tree in this order. For each vertex we will save a vector of it's children. Suppose we are trying now to add vertex "v_to_add". We will have a function add_to_tree(root, v_to_add) (root is an initial state). When we trying to add new vertex we need to check for all our chlidren if w[cur_v][v_to_add] = w[cur_v][its_child] - w[cur_v][its_child]. If it happens to any child of current vertex, then we need to add_to_tree(its_child, v_to_add). (Of course v_to_add must be a descendant of its_child because of its distance to cur_v is a distance to its_child + edge from its_child to cur_v). If no such its_child found we have to connect cur_v and v_to_add (so v_to_add becomes a child of cur_v).After that we are checking distances between all vertices. If they are same as given, then "YES". Otherwise "NO".
 » 4 years ago, # |   -21 Prob A, you say that: if n is even then print 8, n-8n is 25 ans = 8 17 isn't 17 prime number?
•  » » 4 years ago, # ^ |   +5 But 25 is not an even number. You should output 9, n-9 which is 9, 16.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +17 got it. I confused sorry..
•  » » » » 4 years ago, # ^ |   0 you should be careful
 » 4 years ago, # | ← Rev. 2 →   0 Why we used sqrt decomposition in G? Isn't it possible to decompose out interval on base intervals, like it is done in every segment tree? UPD: That thing here proved to be wrong.
•  » » 4 years ago, # ^ |   0 If you want to build a segment tree it will have O(n) nodes, and that means O(n) times FFT, that will be slow.
•  » » » 4 years ago, # ^ |   -11 But I will have n nodes where I want to do 1x1 multiplication, n/2 nodes where I want to do 2x2 multiplication etc. which will result in O(nlog2n)
•  » » » » 4 years ago, # ^ |   +12 Can you describe your algorithm in detail? :)Why you can do 2x2 multiplication instead of 2xn?
•  » » » » » 4 years ago, # ^ |   +1 Umm... Sorry, I was obviosuly wrong and you were right ; p.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I think two dimension segment tree can be solved, we need to record and sort the value of difference of postion where 0 is and position where 1 is respectively in each segment and query and count the difference value of p1-p2 using binary search at each segment, O(n*log(n)*log(n))
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 update: if each time we choose the segment with the minimum length of sequence a and b(absolute difference of two segment will be small) and divide it, and need to record the abs(len[a]-len[b]) value of each segment of segment tree,this number will not be too big I think it is O(n*log(n))
•  » » » » » » » 4 years ago, # ^ |   0 Sorry since my reply can't be update twice,so I have to create a new reply, sorry for trouble caused:update: we can use brute force to compute every segments with length sqrt(n),and use something like two dimension segment tree to divide the segment until the length is sqrt(n) seems can be solve by n*log(n)*sqrt(n)?
 » 4 years ago, # | ← Rev. 2 →   +7 Problems were very interesting.Thank you!![user:cgy4ever] .
 » 4 years ago, # |   0 Can anybody explain the solution for problem D? I am unable to understand the editorial.
 » 4 years ago, # |   0 Another one solution for problem D. One can make vertex №0 root of the tree. Then you can restore for each vertex path to the root (u is ancestor of v if dist[v][0] = dist[u][v] + dist[u][0]) and restore the tree from this information. Then one should use n dfs to check if the matrix is correct.Solution: 8007468
•  » » 4 years ago, # ^ |   0 I will be thank full to you if could help me understand why one needs to do n DFS to check if the matrix is correct? or Why is 1 DFS not enough for checking the correctness of the matrix??
•  » » » 4 years ago, # ^ |   0 Well, one DFS is actually enough if you will check all distances between vertices using LCA or something like that. But I think, it is harder than make n DFS.
 » 4 years ago, # |   0 Can you please provide solution for D implemented in java? -_-
•  » » 4 years ago, # ^ |   0 Your mistake is probably implementing Prim's algorithm in O(N^2 * log(N)) or using Kruskal's algorithm, they might be too hard for Java.
•  » » » 4 years ago, # ^ |   +8 no, my mistake was in choosing java 7. Resent with java 8 and received AC. Just shocked.
•  » » » » 4 years ago, # ^ |   0 Here on Codeforces different Java versions are faster in different problems
•  » » 4 years ago, # ^ |   +3 You may use filter by language here
 » 4 years ago, # |   0 Actually it's not necessary to use assembly hacks to solve G.. bit hacks are enough.. Brute force bit hack is nm/32, which is not enough.. But in fact we can use offline algorithm to optimize it to n^2/32.. which is enough to pass with O2...
•  » » 4 years ago, # ^ |   +5 Well, online works too
•  » » » 4 years ago, # ^ |   +54
•  » » » » 4 years ago, # ^ |   +14 Well, it's a pity that there's such solution for a cool problem, but anyway I'm glad to have personal record:)
•  » » » 4 years ago, # ^ |   0 D:<
 » 4 years ago, # |   +3 Problems were very interesting.Thank you!!!!!!!!!!!!!!!!
 » 4 years ago, # |   +14 Just changed cin/cout to scanf/printf: AC (after contest) 8015832 and TLE 8010736 (during contest). cgy4ever why you didn't warn about large input? T_T why?
•  » » 4 years ago, # ^ |   +3 read this and you don't need scanf on CF
•  » » » 4 years ago, # ^ |   0 I have that ios_base::sync_with_stdio(false); in my template, but it is commented and at the bottom. Actually whenever I see N < 106 I use scanf/printf. But this time I didn't notice it T_TAnyway thank you.
•  » » » 4 years ago, # ^ |   0 I think that scanfs and printf are a bit faster than cins and couts even with iosync thing. Isn't that right? (Am I not starting a flame war?)
•  » » » » 4 years ago, # ^ |   0 In C++11 it isn't right, especially if one use sync_with_stdio(0).
•  » » » » » 4 years ago, # ^ |   +3 well, I don't see reason why c++11 would change anything
•  » » » » » » 4 years ago, # ^ |   +8 Just an observation. Maybe it is compiler-depend. But at least on acm.timus.ru it was almost always faster.Also one can look at this benchmarks, but they don't really have a lot of common with C++11.
•  » » » » 4 years ago, # ^ |   0 If we don't consider doubles (reading them is very slow using con on CF) they may be different, but not really significantly. I believe today I saw a comment where one said that after changing scanf->cin he got TL->AC (but that was really near TL)
•  » » » » 4 years ago, # ^ |   +5 Two years ago I measured that iostreams (with sync_with_stdio(false)) was faster on reading/writing ints than scanf/printf on MinGW.
•  » » 4 years ago, # ^ |   0 I spend the same :'-( , my solution of problem D obtained TLE without "ios_base::sync_with_stdio(false);" cgy4ever why? TT_TTAnyway cgy4ever thanks for the problems, they were very interesting.
•  » » 4 years ago, # ^ |   0 I also did the same mistake. I know its my fault. But the thing i love about codeforces is that its not as I/O extensive like other online judges. I hate this kind of i/o extensive problem. And I think it should be advised in the problem to use faster i/o in this kind of problems so that nobody gets it unsolved for only I/O latency.
 » 4 years ago, # |   +21 Excuse me, but where the heck are floors indexed from 1 :P? I definitely prefer indexing from 1 in general, but floors are always indexed from 0! That made me solving B 2 times longer than it should :P.
•  » » 4 years ago, # ^ |   +11 Probably it depends on country/culture. They are numbered from 1 everywhere I know in Russia
•  » » 4 years ago, # ^ |   +5 They are numbered from 1 in China. In US (at least here in Los Angeles) they are showed as G (for ground floor), but it equals to 1 (because the next floor will be 2).
 » 4 years ago, # |   0 For prob D, I just rearranged the matrix, and rebuild the tree in O(N^2) without using MST or any other algorithm. Here is my solution http://codeforces.com/contest/472/submission/8013128
 » 4 years ago, # |   0 Sad story with problem D: These 2 solutions are equal except the array w[][]. Having an int array gives AC, but long gives TLE.But anyway, thank you for the contest so much! I really enjoyed solving the problems! :)
 » 4 years ago, # | ← Rev. 2 →   +13 My solution for D problem: choose root. for other vertices, calculate which subtree it belongs in O(the number of subtrees). v and u belongs the same subtree if and only if dist[root][v]+dist[root][u] != dist[v][u]. construct subtree recursively. connect root and the nearest vertex to root in a subtree. This algorithm may be O(N^2). source code
 » 4 years ago, # |   0 in problem D tutorial, in the last line you said: ** if you have pre-coded LCA algorithm, it can run in O(n^2 log n).**shouldn't that be O(n*log n) when using LCA ??
•  » » 4 years ago, # ^ |   0 It depends on the way one codes LCA. If you are using the Euler Tour + RMQ method then it's O(n^2) (because RMQ is O(nlogn) and each query is O(1)). On the other hand if you prefer any other O(logn) per query method, then it will be O(n^2logn)
 » 4 years ago, # | ← Rev. 2 →   0 Can anyone help me get the idea of LCA in problem D ?
 » 4 years ago, # |   +17 Another one for D: Let's pick some vertex V. Then let's find such vertex U, that dist(V, U) is max for all U. Found U is the leaf of the tree. Now let's find suck vertex T, that dist(U, T) is min for all T <> U. It means that in our tree there is an edge TU. Now let's delete U from the tree and continue algorithm from vertex T. We need O(n2) time to do such manipulations. And now in the same O(n2) time we're checking if given distances equals to distances in built tree.
•  » » 4 years ago, # ^ |   0 This approach is more intuitive and easier to implement.
 » 4 years ago, # |   0 **Please Explain problem C ** i can't understand yetand also this testcase10 rean schwarzer fei claussell alisa reinford eliot craig laura arseid jusis albarea machias regnitz sara valestin emma millstein gaius worzel 2 4 9 6 5 7 1 3 8 10
 » 4 years ago, # |   0 Time limit is too tight for N^2logN solution of problem D . My TLE code in the contest got accepted just after changing long long int to int. I think the time limit should have been increased to 3 or 4 seconds. I don't think there is a fear of getting a N^3 solution accepted at that time limit as N=2000.
•  » » 4 years ago, # ^ |   +18 In fact Gerald has a N^3 solution that can pass most cases even if N=2000, so I'm afraid reduce N into 1000 may not be a good decision.
 » 4 years ago, # |   +8 Thanks a lot for this round. Nice problems and a lot of fun :)
 » 4 years ago, # |   0 Problem D .. Why am I getting a WA on test 9 . Also how do I see the full testcase ?
•  » » 4 years ago, # ^ |   0 You cannot see the full test case as far as i know
•  » » 2 years ago, # ^ |   0 Same here... I wonder what it is.
 » 4 years ago, # |   0 I am not able to understand F. What does it mean "the operation of xor on 32 bit integers equals to + operation in a 32 dimension linear space"? And what is FFT? Great competition, the first four tasks were pretty nice, the last two tasks seems impossible for me ):
 » 4 years ago, # | ← Rev. 2 →   +3 Here's another idea for Problem C.We can make name-"person id" pairs,and sort those pairs regarding the name as keyword.Now the "peoson id" form a number sequence,all we need to do next is check whether the given n-length number sequence is a subsequence which we made or not.Take the sample 1 as example: 3 gennady korotkevich petr mitrichev gaoyuan chen After sorting,we can get a sequence:3 3 1 1 2 2so ,we can't find a subsequence 1 2 3 in it(answer is NO),but we can find a subsequence 3 1 2 in it(answer is YES). Another example: 2 galileo galilei nicolaus copernicus and we can get sequence: 2 1 1 2 so,both 1 2 and 2 1 are acceptable Here's my solution:8001545
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Did the same..!! Interesting enough this was the first idea that came to my mind . :) My Solution. 8011611
 » 4 years ago, # |   0 Good problems, enjoy the problem F and G. It seems that you like the problem of linear space and make some problems of it. I think I can solve it next time you make such problem. By the way, my solution about D is O(n^2logn) but got tle, feel a little sad..
 » 4 years ago, # |   0 "By property 2 we can use this way to build an answer: use some operation to make A[] into a base (linear independent vectors that the span will be A[]), then transfer it into a base of B[], then use the inverse of Gaussian elimination to recover B[]."I did not get two parts here. How to go from one base to another (i.e. from A to B) and how to do inverse of Gaussian Elimination ? Please help !!
•  » » 4 years ago, # ^ |   +5 To go from one base to another : Note that one can always form a base vector such that MSB of each element of base vector is 1 only in that element. Now suppose you want to go to b_i in basis(y), then it can be reached iff xor of all elements e in basis(x) is equal to b_i, where e is such that MSB of e is 1 in b_i.Inverse gaussian elimination : If a sequence of xor operations is performed on array x to reach basis(x), then performing these operations in reverse order on basis(x) will give back array x. So, in the original problem, once we reach basis(y) from array x, we could perform in reverse order, the operations done on y to reach basis(y).Hence, giving array y from array x.Nice implementation by GateOne http://codeforces.com/contest/472/submission/8020297
 » 4 years ago, # |   0 @cgy4ever: "(I used __builtin_popcount() to test such solution, but in fact cnt[x<<16] + cnt[x>>16] is much faster than the builtin fucnion)" what is cnt here?
•  » » 4 years ago, # ^ |   0 cnt[x] = number of '1's in binary representation of x. So cnt[x<<16] + cnt[x>>16] is the number of '1's in x if x is an int.
 » 4 years ago, # |   0 “So the answer is 2 * (f[n] + f[n-k] + f[n-2k] + ...) — n.” It seems that the last "n" means n%k? 2*(n/k+1): 2*(n/k);? cgy4ever
•  » » 4 years ago, # ^ |   0 Oh, you are right! Thanks for finding that. Fixed.
 » 4 years ago, # |   0 cgy4ever Could you give a more detailed explanation of Problem E? I don't quite get your point in the tutorial.
•  » » 4 years ago, # ^ |   0 Which part you can't understand? The part of FFT or the part of sqrt decomposition?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 darrensun talked about problem E, not G :P
 » 4 years ago, # |   0 Sadness of long long int in Problem D :(
 » 4 years ago, # |   +13 Loved the round, contrary to many people saying D had a bad time limit I think it was fine. My solution passed with O(N^2 log N) in 1500ms in final tests and it passed pretests with 1200ms. So I see there were some large testcases in the pretests which is good enough in my opinion (if you pass pretests in like 1800ms-1900ms, obviously you should worry). D was given in a Bulgarian competition a few years ago so I quickly coded the solution, really loved E though, took me about 2 hours to get it working and I was 5-10 minutes late to submit it.One of the best competitions I've participated in :)
 » 4 years ago, # |   +1 "This task can be solve by greedy: the k people with highest floor goes together, and next k people with highest floor goes together and so on. So the answer is 2 * (f[n] + f[n-k] + f[n-2k] + ...) — n." if n = 3 , k = 2 and f[3] = 4 , f[2] = 3 , f[1] = 2 , the answer will be 2 * (4 + 2) — 3 = 9 , is not 2 * (4 — 1 + 2 — 1) = 8.
 » 4 years ago, # |   +8 Problem G was used for online contest just 2 weeks ago: Hamming Distance from Hackerrank, it contains problem G as a subtask (H-type queries).
•  » » 4 years ago, # ^ |   +28 True, but the intended solution in Hackerrank was indeed bit tricks optimizing the naive solution, while in this problem the author had a much cooler one and expected bit tricks to fail.
 » 4 years ago, # |   0 For the problem B, Is that should be at least (# of f[j] >= i+1) / k times from i to i + 1 floor? Then It is a lower bound, otherwise it's upper bound.
 » 4 years ago, # |   +5 can anybody please help me understand the B part solution more clearly. More specifically, what is f[i] here? Is it number of people "i", who are destined for f[i]? or something else?. And please can anyone elaborate more on proof of correctness of algo? Thanks
•  » » 4 years ago, # ^ |   +9 F[i] is simply the floor of the i-th person assuming you've sorted them, so F[n] is floor of the person that wants to get to the highest floor and F[1] the floor of the person that wants to get to the lowest floor. So F is simply the inital array but sorted.Now what is the solution? Well you know that at some point the elevator will go to F[n], soon or later he has to deliver that person to the F[n]-th floor. Well, while doing that the best thing he can do is fill the rest of the elevator with the other people that go as high as possible. The intuitive proof is that you are going to the F[n]-th floor and it is sensible to get rid of passengers that want to get to high floors as you are anyway going there, and in this way later you might not need to get that high up.So well, while delivering passenger to F[n]-th floor it is optimal to take F[n-1],F[n-2]...F[n-k+1] with him. Obviously since we sorted the array that's the people wanting to go as high as possible. Well repeating that kind of thinking over and over again it is easy to see that you actually go to floor F[n] and back, then to floor F[n-k] and back, then F[n-2*k], F[n-3*k] and so on. And since climbing up and down again to floor F[i] takes 2*(F[i]-1) time, the total time is simply 2*( (F[n]-1) + (F[n-k]-1) + ... )Sorry if you don't understand my explanation, I tried my best. You can always try to prove it strictly mathematically yourself but in my opinion it is intuitively obvious that it's the correct way to go :)
•  » » » 4 years ago, # ^ |   +8 Thanks @Enchom, you explained perfectly. I get it now.
 » 4 years ago, # | ← Rev. 2 →   0 I can't understand the last 2 column by column part of E, like that,suppose We have a target of filling the cell (2,n) and the cell (1,n) is already in position. Now how can we move the cell to (2,n) . If the desired cell is at (1,n-1) or (2,n-1) , then how , can someone explain please?upd-> sorry , I forgot the part we can move cells diagonally too.
 » 4 years ago, # | ← Rev. 3 →   0 Why problem D is giving TLE, if I am using sets? Solution using sets 8041413 Solution using vectors 8041479
 » 4 years ago, # | ← Rev. 2 →   0 cgy4ever, can you please show your sample solution for G? I managed to get it accepted with runtime under 5 seconds using FFT + decomposition of input vectors, but it required a highly optimized FFT implementation, fine-tuning of the L parameter and non-trivial implementation of the partial block case. There's no chance I could have gotten it accepted if I followed this approach during the contest, so I'm curious if I'm missing some implementation trick.
 » 4 years ago, # |   0 Can anyone please help me out with this? For Problem A, I found composite numbers using sieve and solved the problem by checking every possible composite number. Submission id is 8060116 I am getting run time error on test case 14, but on my local machine it is giving the answer as 4 4860 when Input is 4864Thanks.
•  » » 4 years ago, # ^ |   0 As you are using while(curr<=n) you might access p[n]. So the array size should be n+1 instead of n.
•  » » » 4 years ago, # ^ |   0 Thanks a lot, my bad !! Its accepted after the modification.
•  » » » » 4 years ago, # ^ |   0 you should be careful
 » 4 years ago, # |   0 Problem D: In the fourth example, the answer is "NO". Why?
•  » » 4 years ago, # ^ |   0 For the given distance matrix to be satisfied, there will be a cycle in the graph. But we should check if it forms the dist matrix of a weighted tree. I think this is the reason for the answer being "NO"
•  » » » 4 years ago, # ^ |   0 OK. But what is the difference between a weighted tree and a weighted graph? I know that every tree is a graph, but the opposite is wrong.
•  » » » » 4 years ago, # ^ |   0 A tree is a connected acyclic graph. So, a tree does not have cycles.
 » 4 years ago, # |   0 Could someone explain problem B proof in different words ? Didn't get correctness of it..
 » 4 years ago, # |   0 Problem D: My SubmissionI used the same approach as mentioned in the editorial, but I have a problem of verifying the distances between all pairs of nodes, and that results in TLE.Is there a faster way to find the distances between all pairs of nodes? Any help?
•  » » 4 years ago, # ^ |   0 cgy4ever, can you help me with a sample solution or something, please?
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 Dfs / bfs from some vertex will find shortest distances to all other vertices.Run it n times.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   0 Actually after I posted this comment I came up with an idea using Dijkstra n — 1 times to find the shortest paths to all other vertices, because this is a weighted graph. After that I got an AC.But I don't understand how can I use DFS/BFS to find shortest path on weighted graph.
•  » » » » » 4 years ago, # ^ |   0 Oh, I forgot it's weighted. Anyway it's tree and doesn't contain cycles, that's why dfs and bfs work
 » 4 years ago, # |   0 problem A 's simple test have some worng
 » 4 years ago, # | ← Rev. 3 →   0 I tried to find a tree in problem D using Dijkstra from vertex 0, but that solution failed.When I changed it to Prim, the solution passed.Can you tell me why using Dijkstra's algorithm to find the tree didn't work in this case?
 » 4 years ago, # |   0 Can the problem D be solved in the following way? check if the matrix is symmetric and all i==j entries=0 assume node 0 as the root of the tree. establish a relationship between every pair of node: if dis[x][y]==dis[x][0]+dis[y][0] implies they are siblings if dis[x][0]==dis[x][y]+dis[y][0] implies they are parent-child and vice-versa if any discrepancy found with the data, print "NO" This approach give WA#9. The test is huge so I can't tell whats wrong. Any help? Code
•  » » 4 years ago, # ^ |   0 This approach fails if the two nodes have a LCA other than the root or either of them. See this bad diagram:However, this very similar idea passes: 8011400. I'm still trying to figure out why. If anyone can explain it (or give a test case where it fails) I would be very grateful :)
•  » » » 4 years ago, # ^ |   0 Thanks man, dunno how I missed such a big flaw :P
•  » » » 3 years ago, # ^ |   0 8011400 tries to see whether the dist[x][0] + dist[y][0] — dist[x][y] is twice of any of dist[i][0].
•  » » » 2 years ago, # ^ |   0 http://codeforces.com/contest/472/submission/20199101Dunno why did this failed, I tried to consider to distance between two nodes and check them with the sum of the distance two the LCA yet it still failed.
 » 3 years ago, # |   -8 472D — Design Tutorial: Inverse the Problem == http://www.e-olymp.com/en/problems/7413
 » 2 years ago, # |   0 I have a solution to Problem 472A, but it is giving wrong answer in test case 3. Reason: Output 5 18wrong answer printed numbers are not composite