cgy4ever's blog

Codeforces Round #270 Editorial

By cgy4ever, 10 years ago, In English

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

472B - Design Tutorial: Learn from Life

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)

(Also, you can use your knowledge about real world computers to solve this task: http://mirror.codeforces.com/contest/472/submission/8014415)

Tutorial of Codeforces Round 270
  • Vote: I like it
  • +137
  • Vote: I do not like it

Comments Comments (103)
| Write comment?
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for fast editorial!

→ Reply
»
10 years ago, # |
  Vote: I like it +30 Vote: I do not like it

D can be solved in O(N^2). Prim can solve MST in O(N^2) if we don't use priority queue:)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Oh, yes, Gerald told me that some days before. :)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            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?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              I got the pattern from a screenshot and I operated by using ADB (Android Debug Bridge).

              → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In which way you can use Prim's algorithm without priority queue?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      find minimal element each time in O(n)

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Prob A, you say that:

if n is even 
   then print 8, n-8

n is 25
ans = 8 17
isn't 17 prime number?

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      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)

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        Can you describe your algorithm in detail? :)

        Why you can do 2x2 multiplication instead of 2xn?

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Umm... Sorry, I was obviosuly wrong and you were right ; p.

          → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

Problems were very interesting.Thank you!![user:cgy4ever] .

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody explain the solution for problem D? I am unable to understand the editorial.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please provide solution for D implemented in java? -_-

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Problems were very interesting.Thank you!!!!!!!!!!!!!!!!

→ Reply
»
10 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    read this and you don't need scanf on CF

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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_T
      Anyway thank you.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In C++11 it isn't right, especially if one use sync_with_stdio(0).

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          well, I don't see reason why c++11 would change anything

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            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.

            → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Two years ago I measured that iostreams (with sync_with_stdio(false)) was faster on reading/writing ints than scanf/printf on MinGW.

        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I spend the same :'-( , my solution of problem D obtained TLE without "ios_base::sync_with_stdio(false);" cgy4ever why? TT_TT

    Anyway cgy4ever thanks for the problems, they were very interesting.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Probably it depends on country/culture. They are numbered from 1 everywhere I know in Russia

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/472/submission/8013128

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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! :)

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

My solution for D problem:

  1. choose root.
  2. 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].
  3. construct subtree recursively.
  4. connect root and the nearest vertex to root in a subtree.

This algorithm may be O(N^2). source code

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone help me get the idea of LCA in problem D ?

→ Reply
»
10 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This approach is more intuitive and easier to implement.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks a lot for this round. Nice problems and a lot of fun :)

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D .. Why am I getting a WA on test 9 . Also how do I see the full testcase ?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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 2

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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://mirror.codeforces.com/contest/472/submission/8020297

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

“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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, you are right! Thanks for finding that. Fixed.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

cgy4ever Could you give a more detailed explanation of Problem E? I don't quite get your point in the tutorial.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sadness of long long int in Problem D :(

→ Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks @Enchom, you explained perfectly. I get it now.

      → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Why problem D is giving TLE, if I am using sets?
Solution using sets 8041413
Solution using vectors 8041479

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used the size of blocks = 15000 instead of sqrt(n).I got AC without any other optimizations. Try to use L = 15000.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 4864

Thanks.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As you are using while(curr<=n) you might access p[n]. So the array size should be n+1 instead of n.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain problem B proof in different words ? Didn't get correctness of it..

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D: My Submission

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    cgy4ever, can you help me with a sample solution or something, please?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Dfs / bfs from some vertex will find shortest distances to all other vertices.
      Run it n times.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh, I forgot it's weighted. Anyway it's tree and doesn't contain cycles, that's why dfs and bfs work

          → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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:
    1. if dis[x][y]==dis[x][0]+dis[y][0] implies they are siblings
    2. 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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it -8 Vote: I do not like it

472D — Design Tutorial: Inverse the Problem == http://www.e-olymp.com/en/problems/7413

→ Reply