lperovskaya's blog

Yandex.Algorithm 2015: first elimination round today!
By lperovskaya, 10 years ago, In English

Join Yandex.Algorithm, an annual international programming championship organized by Russia’s leading search provider Yandex, to flex your programming muscle and win the equivalent of up to $5,500 of cash prize. The championship is open to anyone, regardless of their education, profession or programming style.

Qualification round starts on May 17 with warmup round on May 3. Read more about Yandex.Algorithm and register for participation before May 18.

UPD Qualification round is open until 0:00 May 18, start now on Yandex.Algorithm website.

UPD Do not miss first elimination round. That will start May 24, 2015 at 21:00 (UTC+3)

  • Vote: I like it
  • +149
  • Vote: I do not like it

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

Sorry, form unavailable Need auth.

What's wrong?

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

    You need to be logged into Yandex to register. Use social auth for easy registration

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

Will you send reminders before every round?

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

Where will be the final round take place?

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

    Russian post version says that the championship will be fully online :(

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

Why am not I allowed to enter warmup round?

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

We will start the round at 22:10, thank you for your patience

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

    I hope you guys are not managing the contest from the Yandex Moscow office at Sunday, 22:00 :)

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

    It's still unavailable for me

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

    The absence of the exact date seems now suspicious to me :(

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

    Lie

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

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

My friend says he can see the problems but all I get is "The contest is over. Submissions are not allowed". Sounds quite unfair?

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

    He's lying and shouldn't be your friend anymore.

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

      Well he sent me a problem statement, so I guess he just created a problem for the lie! :D

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

        Why would he lie to you wihout a preparation? Don't be naive. :)

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

    Same here

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

The countdown timer is shown now.

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

Now it says the contest will start in 3 minutes, but my friend sent me a picture of the statement already... Gonna be a fair competition I see!

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

I saw problem A and started coding it but now it says the contest has not started yet. =.=

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

    Hey, that's unfair! We need some men in black to fix that for ya.

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

Ваше решение отправить не удалось. UPD: У вас нет прав просматривать это соревнование.

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

Just when you thought it's all going well — "You are not allowed to view this contest".

I'm getting Bayan flashbacks here :\

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

Даже условие загрузить не успел :(

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

    А я успел и решить, но отправить не успел(

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

What can I do sometimes ?!!!!!

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

Whenever I try to submit a solution, it tells me:

"Your solution was not submitted."

Help?

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

I can't submit my c++ solution for A. Any clue? :D

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

Problem B is identical to a problem from Canadian OI, with minor changes to the statement and identical input format/sample data:

http://wcipeg.com/problem/ccc03s2p3

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

    I think all problems used for this round are not new. I don't see any troubles with giving old problems to the warm-up round.

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

      In the rules it says

      For all rounds, the problems will be original.

      Official Rules

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

        Problems in the warm-up (testing) rounds were used on different contests like OpenCup or local contests. Problem about cube was used on some ancient SnarkNews Series; but in there it was taken not from Canadian OI, but from some other source (dont remember precisely, which one though).

        Original problems must be for all official rounds (Qualification, three Online rounds and Online Final). Testing round(s) use selections — main goal of it is to test if the system is working ok and to remind TCM/Time rules to players, and for this goal selection from different sources works okay.

        I met problem with same idea several times in different old contests, so it was added as "classical problem"; i am surprised that number of players solving them is not that big.

        May be, first time it appeared in Canadian OI (atleast format points at it). Btw, tests were changed abit to catch some special cases.

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

    See also the following problems:

    https://contest.yandex.ru/contest/424/problems/F/

    http://wcipeg.com/problem/ccc13s2p6

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

Huge thanks for everyone who stayed with us until the normal flow of the round. We'll make sure that Qualification round on May 17 will run smoothly.

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

Разбор будет?

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

How to solve C ?!

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

    If points are on the different sides to axis x result is euclidean distance between them. Else change y of first point to -y.

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

      It is stated, that both points are on the top side the river, so you don't have to check whether cities are on different sides of the river.

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

How to change the country flag that is shown to the right of my name in the standings?

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

I can't wait more for the editorial. Can anyone give the accepted code for problem A? Thanks.

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

    You can use Havel–Hakimi algorithm to solve the problem.

    Because there is at least one solution. You can first build a degree sequence with all degrees equal to k. The divide the rest degrees to each element of the degree sequence evenly.

    My code for reference: http://paste.ubuntu.com/10994941

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

      Is it possible to solve this problem ignoring K? I mean, create a sequence of edges based only on N, and then take the first M edges of it. (Yes, the sequence must ignore M too :)

      For a challenge I have been trying to solve A this way, but failed. I still do not know the answer.

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

        Well, I ignored K, but had not ignored M though

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

Sooo, who are the t-shirt winners ?!

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

I couldn't understand open/blind submission. What is difference ?! What are advantages of open/blind. Does blind mean : "I don't need feedback" or sth else ?!

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

    When you use blind way, you dont have feedback but you have additional bonus instead of penalty time. I.e. you choose harder way and are awarded for it with the decreasing of total penalty.

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

      hmm got it... So if my solution gets OK in open submission does it mean I have solved that problem I mean it checks all tests ?!

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

        Yes.. It means ur solution passed all the test-cases

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

      To be precise, it's not instead of a penalty, it's in addition to penalty (so you have both penalty and bonus)

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

Where can I solve previous Yandex contests?
(of last year and last to last year)

EDIT-1 : Found 2014 in GYM

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

Is there public standings page?

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

    Not until the end of the contest. It will be unfair if contestants who haven't started yet could see someone's final results.

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

    It still would be cool to see the standings for those who are not registered.

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

Huh, memory limit is 64Mb ; o? Kinda completely missed that, I haven't seen such small memory limit as a standard limit for some time and it costed me one problem ; d.

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

    Same for me.

    I'll read statements more carefully. I'll read statements more carefully. I'll read statements more carefully...

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it -8 Vote: I do not like it


    Like this ?!
    UPD I understood why minus. I think you you thought it doesn't calculate if your memory exceeds 64MB, but before this submission memory was around 135MB.

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

My first submission stayed with the "waiting" status for about half an hour and I had a stupid bug that I had to wait half an hour to correct. I hope this doesn't happen in the Elimination rounds.

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

Top 512 participants according to the cumulative result of all three elimination stage rounds will receive a contest T-shirt. what does it mean "cumulative result",there is 3 round,and in each only top 30 user can earn points,3*30=90 and how 512? pls some1 explain me

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

What is the solution for Problem B — Optimal Playlist ?

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

    Binary search, then condense strongly connected components and topologically sort them. Components will form a chain iff the required path exists.

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

      What about finding Minimum Cost Spanning Tree in DAG? Would this approach work?

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

        No: for example, in graph (1->2,1->3) there is an oriented tree, but no path visits all nodes.

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

Ah, missed qualification again.

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

Can someone give some hints for problem C? Thanks.

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

    My approach was following. Let's store in f[d][j] j-th parameter of d-th document, in s[d] relevance for d-th document and in some structure r — sorted relevances with numbers of corresponding documents (it was set<pair<long long, int> > in my code). Then for each query it's easy to update. For 2 K it was just top K elements of set. For 1 d j v:

    r.erase(r.find(make_pair(s[d],d)));
s[d]+=a[j]*(v-f[d][j]);
f[d][j]=v;
r.insert(mp(s[d],d));
    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I used order statistics tree. I guess using STL set container would have sufficed too.

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

How to solve E problem ?!

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

    We need to find the number of pairs (A, B) such that A divides N, B divides M and L <= AB <= R. First generate all divisors of N and M. Then iterate over A (divisor of N). Corresponding B must be in the interval [L/A, R/A]. The number of divisors of M from this interval can be found by binary search.

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

      You may even iterate through all divisors of N and M and just check if L<=A*B<=R.

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

        Yes, it seems that the worst case is the number 223092870=2×3×5×7×11×13×17×19×23, which has only 2^9 divisors, so it's 2^18 pairs at most.

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

          i think the worst case is 931170240. this number have 1344 divisors.

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

          I am pretty sure, that your estimation is not correct (for example, you may use 2*2*2*2*2 instead of 2*23), but you may assume that the number of divisors for such small numbers is O(N1 / 3), and the total complexity of our algorithm will be O(N2 / 3)

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

I'm still unable to understand what Problem B was. Can someone please explain the output of the sample case or any other case?

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

    You should find a path in the given graph with minimum possible max edge weight.

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

Couldn't understand the purpose of problem X — Fake testing problem.

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

    People were asking for some way to be able to test code on the server in case of compiler configuration problems. I think this solution proposed.

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

    You can build your source file on Testing server and run it. e.g. you can debug TL for your solution.

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

    it's as codeforces's custom test

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

How to solve problem B (Elimination round 1)?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it +20 Vote: I do not like it

    My solution — in cycle pick every city as a center.

    Central city can be allocated to either top or bottom cities group depending on where you need it by shifting line some infinitesimal amount up or down. We can do it because no three cities lie on the same line.

    After you picked central city you can use magic atan2 function and simulate rotating line through your central city and calculate how many people live above or below it. You can do it by sorting two lists by atan2 value (or one list) and going through it with two pointers. Pick minimum, but remember that you can always allocate central city the way it's better for you (my code was like abs(abs(x) — central)).

    I bet there are easier solutions but this one got ACed and I am happy with that.

    For me it was tough round, much tougher then Round 1 in GCJ this year. I solved just one problem and spend 1 hour solving Saw or Not To Saw — I think I was very close, but couldn't get through WA3 :(

    Moved to: Proper thread for discussion

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

      You can use orientation in integers, but use atan2 in doubles?

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

        With coordinates limited by 1,000, double precision should be more then enough for all angles. Though I already see that it was bad solution — over complicated. Costed me 15-20 minutes of my time.

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

          coordinates were limited by 2⋅104
          and with good tests no solution with bad-written doubles should pass imho

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

            If so, I defy you to show us test where atan2 is not sufficiently precise (on long doubles, why not?)

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

              of course it's difficult to construct such test. And in this problem I think atan2 is sufficiently precise
              so maybe using orientation everywhere is paranoia, but a good one ;)

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

          This is overcomplicated? I think that your solution is the simplest possible one. What can be even more simplified?

          I used more complicated approach where I maintained array of prefix sums of possible divisions when sweeping points with line of a fixed inclination and updated it appropriately when rotating this line.

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

            I liked idea of taking pairs of dots and drawing lines between them. I think if this idea struck my mind I would finish this question in 15 minutes, not 35. But I often experience that — coding more complicated solution.

            But thank you for admitting that red coders sometimes do complicated things too. :)

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

              What do you mean by that idea?

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

                Found it in this thread above. I just realized that it is O(n^3), to test all pairs of cities and calculate population on each side. So maybe not good idea. Ok, my solution is not over complicated :)

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

    It isn't real solution, but here's some magic!

    http://ideone.com/YeLtmM

    Rotate point around origin by , and try all possible y axis, as a "divide line". Do it K times.

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

How to solve Problem F — To Saw or Not to Saw?

I got 2 formulae by using similarity of triangles:

  • d * (c - a) / c, when >
  • b * (a - c) / a

Got WA on testcase 3.

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

    ans = gcd(a, c) * min(b / a, d / c)

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

      It may sound really stupid.. but how can one get to this formula?

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

        Let me rewrite it a bit:

        ans = gcd(2a, 2c) / 2 * min(b / a, d / c)

        The first part d = gcd(2a, 2c) comes from the following observation. Let's assign integer numbers to each peak of the saws and let's put two saws so that 0-th peak of the first saw will be exactly above the 0-th peak of the second saw and denote this coordinate as X = 0. If you plot the rest of the peaks then peaks of the first saw will have coordinates xi = 2a * i for each integer i, similarly peaks of the second saw will have coordinates yi = 2c * i. Then you plot all those peaks as points on X-axis and the question is what is the smallest distance of first saw peaks and second saw peaks. In other words what is the min(dist(xi, yi)) = min(abs(2a * i - 2c * j)) for any integer i and j. If you solved enough number theory problems it will be clear to you that this is equal to d = gcd(2a, 2c) = 2·gcd(a, c).

        Now you have this d number. If you plot peaks again you should see that the optimal solution would be to move one of the saws d / 2 units left or right and then move them towards each other as much as possible. How much you will be able to move it depends on the "sharpness" of the saw's teeth (i.e, b/a ratio). Then if you know d already the result is simply l = d / 2 * b / a. Then you replace b / a with min(b / a, d / c) because you need to consider the case when first saw has "sharper" teeth.

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

          Thank you :).
          It's crystal clear now..
          Thanks for your time

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

    well and if a = c ? I put min(b,d) but it's WA on 4th

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

Just my luck. Picked the weird looking problem earlier on only to realize there was an easier one waiting. Started solving and couldn't submit by 5 seconds. Submit in upsolving mode and get Accepted.

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

Can someone start a new thread with editorial to the problems of Elimination Round 1.
I think I can learn a lot from the editorials of this round. Problems were a lil tough for a beginner like me.

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

My code (for Elimination Round 1 problem E) gets TLE in test 9 with 2.093s. How can I improve it? What's the problem?

Thank you in advance!

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

    Here is how I did it. Hope it helps.

    I am currently too sleepy to read your code so I can't really say why yours failed. Sorry.

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

      Thanks, it helped. I forgot to compress queries in which k=1.

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

My opinion is that problemset was very nice! C, D and F were very interesting in my opinion! B and E were also OK. Unfortunately A was tedious, any deeper thought, just a lot of cases to consider.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    You can write A with almost no special cases

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

      How? My solution has about 10 ifs.

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

        I do not measure number of cases in number of ifs, rather in number of different constructions. My solution

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

      OK, that sounded like a challenge, so I went for it and managed to get this accepted by this code: http://ideone.com/kFdFxb It doesn't contain that many ifs (only 5), but it is still tedious >_>... I think that analysis of those cases is nonomittable (case when cur_wid == l[hor] is especially nasty xd) and if you have more elegant solution I would like to see it.

      During contest I didn't give that task a deeper thought, because I haven't even read it, because in half of the contest I have to made a choice which problem to do next — A, C or D. A had least amount of ACs within top people (but now I see that it had much more ACs that time :d) and had longest description, so I disregarded A and choose D since I quickly got and idea how to do this. After contest I thought that it's all about cases, so I didn't think about this much :P.

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

    Are you implying that you haven't seen about 10 problems which are basically equivalent to B? Those half-plane things appear over and over and over again.

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

      Uh, OK, indeed it is not very innovative problem, but at least there was not anything which will cause me to complain about something, for example no restoring result, no collinear points etc.

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

For problem C,I find the fomula: dp[n][k]=dp[n-1][k-1]*(n-k+1)+dp[n-1][k]*k (1<k<n) using bruteforce.But what's the logistic in it?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    (I guess that you meant problem C). Don't tell me that it's true :o!? That looks very mysterious for me. I got AC (after contest) using much more complicated DP with n^3 states, some binomials and stupid trick allowing me to fit in O(n^2) space ;__;.

    UPD: Yeah, it looks that it's true, however I don't have time now to wonder why is that. Here's my code: http://ideone.com/GdOSTe but compared to your solution I guess it can be mainly used to make fun of me :P.

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

      Can you explain more about your idea?I really can't understand it.

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

        I consider similar type of game. When we delete only the smallest card, not smallest or largest. Observe that game when there are n cards and we want to end up with k-th card is a sum of two independent games of that type (one with cards 1..k, one with cards k..n) when we delete last card in turns of the same number — this is key observation to whole solution (one of them (k..n) is reversed, that means that we delete the largest card instead of the smallest one).

        Given that I compute dp[a][b][c] which tells how many of such games are that we are given a cards, largest card is on b-th position and we delete it c-th moment we see it. pref[a][b][c] = sum dp[a][1..b][c]

        Fitting in O(n^2) space is little tricky. Given formulas for dp I can compute dp for dp[a][..][..] given only dp[a-1][..][..], I do not need previous values of a, but when counting answer I have to combine games of sizes k and n-k+1, so I either need to separately count this for dp[k] and run everything once again for dp[n-k+1] or observe that analogous property holds for number of checks and when combining games I always combine two games with the same number of checks (I used second approach).

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

          I think the c-th moment factor is also the hard and key point to solve the problem.And it really needs observation.

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

    This formula is also number of permutations with k-1 rises (position such that a_i < a_i+1). It's easy to see why it's correct but I still haven't found connection between that and C problem. Maybe there is a bijection?

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

this was hard

→ Reply