Блог пользователя cgy4ever

Автор cgy4ever, 10 лет назад, По-английски

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

Разбор задач Codeforces Round 270
  • Проголосовать: нравится
  • +137
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Thanks for fast editorial!

»
10 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +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

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 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?

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +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.

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится +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?

            • »
              »
              »
              »
              »
              »
              »
              9 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      find minimal element each time in O(n)

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +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.)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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".

»
10 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

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?

»
10 лет назад, # |
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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -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)

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится

        Can you describe your algorithm in detail? :)

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

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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??

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 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.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 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...

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +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?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    read this and you don't need scanf on CF

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 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_T
      Anyway thank you.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 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?)

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится +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.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 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)

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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.

»
9 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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).

»
9 лет назад, # |
  Проголосовать: нравится 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

»
9 лет назад, # |
  Проголосовать: нравится 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! :)

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 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 ??

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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)

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +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.

»
9 лет назад, # |
  Проголосовать: нравится 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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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.

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 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 ):

»
9 лет назад, # |
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 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

»
9 лет назад, # |
  Проголосовать: нравится 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..

»
9 лет назад, # |
  Проголосовать: нравится 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 !!

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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

»
9 лет назад, # |
  Проголосовать: нравится 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?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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.

»
9 лет назад, # |
  Проголосовать: нравится 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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Sadness of long long int in Problem D :(

»
9 лет назад, # |
  Проголосовать: нравится +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 :)

»
9 лет назад, # |
  Проголосовать: нравится +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.

»
9 лет назад, # |
  Проголосовать: нравится +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).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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.

»
9 лет назад, # |
  Проголосовать: нравится +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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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 :)

»
9 лет назад, # |
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.

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

вопрос по D. Я из входной матрицы строю граф(полный), ищу в нем минимальный остов и dfs'ом из каждой вершины нахожу расстояния от неё до остальных и сравниваю с записанными в исходной матрице. итоговая асимптотика получается n^2 * log(n*n) — сортировки. но из-за всяких проверок, построения остова и т.д. у меня TL на 11 тесте(10 еле-еле влазит). скажите, такое решение не предусматривается или нужно оптимизировать? 8063019

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    Получает AC (8063333) после замены

    bool f(edge a, edge b)
    {
        return a.z < b.z;
    }
    

    на

    inline bool operator < (const edge &a, const edge &b)
    {
        return a.z < b.z;
    }
    

    Связано это с тем, что перегруженный оператор "меньше" оптимизируется лучше. А также (самое главное) происходит передача аргументов по ссылке вместо копирования.

»
9 лет назад, # |
  Проголосовать: нравится 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 4864

Thanks.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
        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.

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
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?

»
9 лет назад, # |
  Проголосовать: нравится 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:
    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

»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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