adamant's blog

By adamant, 11 months ago, translation, In English,

Hi everyone!

Missed me? I bet no! In either way, here goes another one round which I dared to spoil by my participation in problemsetting. Welcome to the world of extremely unoriginal problems, awkwardly long and boring statements and trifling jokes in anouncements.

This time round was prepared by Ildar Gainullin (gainullin.ildar) and me (I'm ashamed to place link of such color here, you know who). We want to thank Vladislav Isenbaev (winger), Konstantin Semenov (zemen), Alexey Shmelev (ashmelev), Ivan Smirnov (ifsmirnov) and Alex Fetisov (AlexFetisov) for testing problems and help in preparation. Also special thanks goes to Nikolay Kalinin (KAN) for his help as coordinator and, of course, MikeMirzayanov for polygon and codeforces.

We hope that you will enjoy the problems, good luck and have fun!

UPD. Also thanks to akvasha for completing our problemset by his problem.

UPD 2. The contest is over, congratulations to winners!

Div. 1:

  1. dotorya
  2. Um_nik
  3. Radewoosh
  4. ainta
  5. dreamoon

Div. 2:

  1. UoA_Nirvana
  2. noelnadal
  3. Dededededestruction
  4. Kroma
  5. Yjsu

Here are editorials.

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

»
11 months ago, # |
  Vote: I like it +54 Vote: I do not like it

Man! I need such sense of humour!

Anyways, GL and HF.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -39 Vote: I do not like it

    Guess who is more pr0?me me me. Do you even code bro?

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it -24 Vote: I do not like it

      how to get a better Contribution?

      stop commenting or you will get more down vote :)

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Seems interesting :D

»
11 months ago, # |
Rev. 5   Vote: I like it +44 Vote: I do not like it

Great Grand Duke Olexandr Kul’kov

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +89 Vote: I do not like it

    I'm sorry but you have some small mistakes.

    It's more correct to write Oleksandr (or Alex if you are lazy to write long words).

    "Great grand" is a bit tautology. But if you mean that Oleksandr is a great guy then maybe it's ok.

    Sources: link, standings of some competitions and wikipedia.

    I hope my comment will help you :)

»
11 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Logged in just to upvote you

»
11 months ago, # |
  Vote: I like it +22 Vote: I do not like it

When the announcement is so exciting, I bet the contest will be awesome!

»
11 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Welcome to the world of extremely unoriginal problems, awkwardly long and boring statements and trifling jokes in anouncements.

sees some problems from his past contests

Okay I'm bracing myself :D

»
11 months ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

How many problems in the contest?

»
11 months ago, # |
  Vote: I like it +69 Vote: I do not like it

Isn't this clashing with Topcoder SRM 726 ?

»
11 months ago, # |
  Vote: I like it +27 Vote: I do not like it

how many number of problems will be there?

»
11 months ago, # |
  Vote: I like it -55 Vote: I do not like it

FUCK TC SRM. It is clashing with cf round so no way i'm missing it!!!

»
11 months ago, # |
  Vote: I like it +40 Vote: I do not like it

hope for no long queues. c:

»
11 months ago, # |
  Vote: I like it -48 Vote: I do not like it

awkwardly long problems??? why??? ):

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    negative comment seriously? do you really like them?:D

»
11 months ago, # |
  Vote: I like it +111 Vote: I do not like it

Nooooo... CF and SRM are clashing :/??? Seriously?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Hope either Codeforces or Topcoder will change starting time as soon as possible.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    Unfortunately, when we announced this round, there was no SRM on this date on their schedule. When they announced it, it was too late for us to move this round.

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 4   Vote: I like it +3 Vote: I do not like it

      Hi, I think there was Data Science Newsletter (of Topcoder) titled "It's Data Science Newsletter Time! SRM this Saturday & the 19th!" in December 9th (10 days ago) and it has a schedule — "SRM 726: December 19 at 11:00 UTC -5". And I remember that the date that announced this round was less than 10 days ago. So I think "When they announced it, it was too late for us to move this round." is not true, isn't it?

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +28 Vote: I do not like it

        I've put Round 453 on the schedule on the 7th. You know, it is the end of the year, we have a lot of rounds and I also have a lot of other things to finish, so wasn't able to move it, sorry about that.

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But that's a matter of 90 minutes, was it so hard to put the contest in the 'usual' time (19:30 MSK)?

          • »
            »
            »
            »
            »
            »
            11 months ago, # ^ |
              Vote: I like it +46 Vote: I do not like it

            After SRM we can start no earlier than 21:05 MSK, it is too late. Before it we can start no later than 16:35 MSK, it is too early.

            • »
              »
              »
              »
              »
              »
              »
              11 months ago, # ^ |
                Vote: I like it -22 Vote: I do not like it

              1) So if I understand correctly following events happened in this order: a) you scheduled round on today, b) topcoder announced their SRM date, c) you announced cf date. If that's correct you can't blame them for putting SRM at clashing time.

              2) 21:05 MSK is too late? Many people from Russia participate in SRM at 5:00AM MSK. Or did you mean some other issues?

              • »
                »
                »
                »
                »
                »
                »
                »
                11 months ago, # ^ |
                  Vote: I like it +32 Vote: I do not like it

                1) By scheduling I mean posting it on the public schedule at /contests which propagates to calendars and so on. So I use this word in the same meaning as announcing.

                2) Yes, it is too late. Rounds are made not only for red coders who write contests even at 5:00 AM, but for everybody.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  1) In that case I'm sorry for suggesting wrong statements.

                  2) IMHO 21 is perfect time to have a contest. 18 or something can always be troublesome because some people still have courses on university or work. 21 is safely after all such activities and 23 is not too late to end contest (for me, but it depends on a particular guy). And even if it is too late for some people then I guess that having two contests, one at 19MSK and second at 21 MSK is significantly better than one at 18:35 MSK and 19 MSK. Did you try contacting TC to reschedule their SRM since CF was announced first? I guess this is worse for TC than for CF, so if they value what they do they should at least consider this.

»
11 months ago, # |
  Vote: I like it -63 Vote: I do not like it

Will the rounds be rated?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Maybe! It will be specified Later. Anyway, That is enough to have contest to learn and enjoy. :)

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Maybe semi-rated!

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it -19 Vote: I do not like it

      Or x-rated!

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +79 Vote: I do not like it

        xxx-rated round, not safe for work.

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it -14 Vote: I do not like it

          I am your follower Adamant!!! I am waiting for your contest eagerly Hope Someday I have a chance to meet you :)

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    phew...and i was worried no one's gonna ask that...XDDDDD

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

After retired from ACM-ICPC, I still have something to do with Codeforces, something like becoming a MASTER, just for fun. # Hello the world without training!

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Intriguing announcement :D !

»
11 months ago, # |
  Vote: I like it -29 Vote: I do not like it

This shit better be unrated, ami right or am I right boizzz?

»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Every Third Contest I do on Codeforces becomes unrated due to Server Issues / Test Cases Issues etc. FINGERS CROSSED

»
11 months ago, # |
Rev. 3   Vote: I like it -42 Vote: I do not like it

Let's see what type of problems comes in today's round.

»
11 months ago, # |
  Vote: I like it -12 Vote: I do not like it

First two problems will require Geometry/Math. Calling it.

»
11 months ago, # |
Rev. 2   Vote: I like it -40 Vote: I do not like it

I request the problem setters to restore the difficulty level of problems, the last 2 contests were a bit easier.

»
11 months ago, # |
  Vote: I like it +325 Vote: I do not like it

»
11 months ago, # |
  Vote: I like it +53 Vote: I do not like it

adamant gonna be pulling our strings tonight (ahem).

»
11 months ago, # |
  Vote: I like it +27 Vote: I do not like it

This was the contribution to Global Warming :) [ LOTS OF TREES ].

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why can't I see other's solution to hack? Only thing I see after clicking the solution is Update adobe flash. I use chrome browser.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Have you tried updating Adobe Flash Player?

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I too cant hack after locking the problem. I have all the tools installed

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Try Firefox

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I m using chrome and am able to view my solutions.but not others. Next contest i will try firefox.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe flash is disabled in chrome, click the circle near codeforces url and allow flash.

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve Div1 C?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    for each i , find smallest j such that [i,j] induced subgraph has a cycle , to do that , build a max spanning tree(weight = min(i , j) for an edge i <-> j) , now its just some path queries.

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How To Solve Div2 Problem A? Can anyone Explain?

  • »
    »
    11 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    It is possible to solve it by maintaining an array of booleans:
    reachable[0], reachable[1], ..., reachable[m]
    (initially all elements are false, except reachable[0] which is true).

    Then, while reading input do the following:

    • For each pair (a, b), if reachable[a] then iterate by x from a to b and assign true to reachable[x].

    The answer is reachable[m].

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to check discontinuity in this case?

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It depends on what you mean by discontinuity.

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
          Rev. 4   Vote: I like it 0 Vote: I do not like it

          No Path from source to destination.

          Link is broken?

          • »
            »
            »
            »
            »
            »
            11 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You probably meant the cases when bi - 1 < ai for some i?

            Suppose that ai - 1 is reachable (reachable[ai - 1] = true).

            After (i - 1)-th step, we will have reachable[ai - 1 + 1] = true, reachable[ai - 1 + 2] = true, ..., reachable[bi - 1] = true
            Note that reachable[ai] will remain false (because bi - 1 < ai).

            On i-th step (as well as during all other subsequent steps) we do nothing because reachable[ai] = false.

            The answer will be false, as expected.

            Full code is also available (33420669).

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe I can.

    So, you should initialise "int RightCan[submission:33422641] = 0" — the farthest point you can reach. (And you can also reach ALL the points before it — from 0 to RightCan).

    If a[i] <= RightCan — then we can reach the start point of teleport[i]. So, we can change RightCan to b[i], if (b[i] > RightCan). (This if very impotant... becouse otherwise we can decrease RightCan!).

    It's know that a[i] >= a[i — 1], so we don't miss anything.

    And now, if (RightCan < m) you should print "NO\n", otherwise — you can reach your goal and print "YES\n".

    Here is my solution: 33422641

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks For Help :)

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      If it is possible. Can you help me, please? In pretest 5 we have:

      11 39
      11 19
      11 19
      11 11
      13 18
      

      In what way can we teleport from 11 to 13? Thank you in advance. In my solution http://codeforces.com/contest/902/submission/33436932 i had wrong answer.

      • »
        »
        »
        »
        11 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Starting point should be 0 always as state in the problem statement. In Test-5: it's start from 11 so answer should be for this case is "No".

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm afraid that you got the problem condition wrong. Didn't you?

        Specifically, if a = 11 and b = 39 (as in the first line of the quoted example), then you can teleport from 11 to 12, from 11 to 13, ..., from 11 to 39.

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          If I understand correctly. We must take into account all the previous iterations, if the current position does not change.

          • »
            »
            »
            »
            »
            »
            11 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            If the x = 11 point is reachable through teleports only (after processing all the previous input),
            then 12, 13, ..., 39 are also reachable through teleports only.

            (x = 0 is always reachable because It is the starting point.)

      • »
        »
        »
        »
        11 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Well, look here:

        3 7

        0 6

        1 2

        4 7

        Your solution gives the answer "NO". But your can reach point 7: 0 -> 4 -> 7.

        port 1: [0 _ 1 _ 2 _ 3 _ 4 _ 5 _ 6]

        ___port 2: [1 _ 2] ___ [4 _ 5 _ 6 _ 7] <-port 3.

        This happens because your looks only on the 2 last teleports. _____________________________________________________________

        And yes, isn't mivael right?

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you very much. I will try to implement the correct solution.

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you for your time Can I bother you a bit more

          Why in test
          48:
          Verdict: WRONG_ANSWER
          Input
          1 4
          1 4
          Jury's answer
          NO
          

          have we answer NO ?

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh! I understend. We must begin from zero I solved! Thanks for help.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The basic idea behind the solution is you have to find is there any discontinuity between 0 to M.
    To check this Take an array A of size M or greater having initial value 0.
    now take the input [x;y] and do this.
    A[x]+=1;
    A[y]-=1;
    after doing this take prefix sum of array a using A[i]+=A[i-1] form i=1 to M.
    now if any element in array A [ 1 to M ] is equal to 0 except last value then answer will be 'NO' Otherwise 'YES'

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain how prefix sum work in this case?

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Take an example.
        N=3 M=5
        0 2 ; a[0]=a[0]+1,a[2]=a[2]-1
        2 3 ; a[2]=a[2]+1,a[3]=a[3]-1
        3 5 ; a[3]=a[3]+1,a[5]=a[5]-1
        after doing this your array will look like
        [1 0 0 0 -1]
        now after taking prefix sum your array will become.
        [1 1 1 1 0]
        no element is 0 except last one so your answer will be "YES" in this case.

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why array consist of only 0 and band 1? It should store sum of x and y?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the pretest 3 on C ?

»
11 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

How so solve Div2D?

Also, though I was able to solve Div2C , someone please share the logic of it. I saw some people did C quite quickly. That was like fucking awesome.

Was it so easy or some general problem that I don't know?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What I did was for one tree, I kept adding all the children to a single node. And for the other tree, i just remove one child and put under some other parent. Hope this is the right logic though

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmm seems nice and same as mine. :)

      Although I was able to come with one more logic though a bit late but I believe this will work.

      No two consecutive terms should be not equal to 1.

      I mean to say that no two non unity terms should have distance less than or equal to 1.

      This will suffice as a condition. For designing a tree, your and my logic should work I suppose.

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        There can be consecutive 1's. The condition is there should be atleast 2 consecutive 2's(or numbers >1)

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes..That is the thing what I wanted to write. :)

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This is what I implemented. Let's see if it is right, lol.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2 D/Div1 B?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    B. I went for a DFS solution. set the root color and then dfs iteratively coloring the nodes

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +64 Vote: I do not like it

    lets work on
    f0 = 1
    f1 = x
    fi = fi - 1 * x + fi - 2
    answer is fn, fn - 1

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I did exactly the same.

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Overlook the condition that that co-efficient should be -1,0,1 and got the wrong answer :(. Else did exactly the same.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Usually I self-proclaim myself as someone who knows many things about math, but here you proved the opposite.

        Thanks for the enlightenment you brought ;) I got stuck for an entire hour with D and not even knowing about this ;)

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        How do you use Google in such problems? I guess that searching "polynomials euclid algorithm small coefficients" would yield no useful result and even on that page you provided I see no useful info (without that mod 2 trick that I still don't understand these Fibonacci polynomials are useless).

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You can do it by arbitrary mod. Mod 2 is to keep coefficients below 2. The thing is that if you calculate gcd using some mod and has k steps you will have at least k steps calculating it in rationals.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Using this formula,

      f2 = x*x + 1 = x^2 + 1 and f3 = x*(x^2+1) + x = x^3 + 2x

      Since, the coefficients should be from -1 to 1. So how did you handle this part?

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        mod2

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Instead of mod 2, can we multiply it with (-x) ?

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes but some higher degree polynomials may contain coefficients outside the range. So you need to multiply with x or -x depending on the current situation.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But the coefficients won't be -1 0 or 1 right?

      (I don't know.. I am probably wrong but please tell me where I am wrong)

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Working in means the coefficients are taken mod 2

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      f3 = x^3 + 2x, however all the coefficents must be in [-1;1]. How did you solve this issue?

      UPD: solved

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +45 Vote: I do not like it

      What? I have no idea why this works :f. This seems like key idea here, but I see no meaning behind it.

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it -30 Vote: I do not like it

        It's well known that GCD takes the longest time on fibonacci numbers. This is just an extension of the idea from numbers to polynomials

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it +35 Vote: I do not like it

          If we abandon condition about coefficients being from set {-1, 0, 1} then this problem is trivial, I was well aware that without it we can do fi = xfi - 1 + fi - 2... What is tricky here is that reducing mod 2.

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        if we work on instead of , then this obviously works since fi mod fi - 1 = fi - 2 since x * fi - 1 + fi - 2 mod fi - 1 is obviously fi - 2
        in , this fact still remains true , since degree of fi = degree of fi - 1 + 1 and powers of x are independent over .

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it +32 Vote: I do not like it

          I still have no clue about your solution. It is of course true that over , but I see no connection of that fact to Euclid algorithm in and have no idea what this independence has to do with anything.

          • »
            »
            »
            »
            »
            »
            11 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            well fi mod fi - 1 = fi - 2 even in , are you sure you didn't misread the question and thought that coefficients should be {-1,0,1} even for immediate steps?

            • »
              »
              »
              »
              »
              »
              »
              11 months ago, # ^ |
              Rev. 2   Vote: I like it +11 Vote: I do not like it

              Let's make it clear what is obvious ans what is not:

              Obvious fact 1: If we define fi = xfi - 1 + fi - 2 over then we have over

              Obvious fact 2: If we define fi = xfi - 1 + fi - 2 over then we have over

              Obviously false statement: If we define fi = xfi - 1 + fi - 2 over then we have over

              Since that last fact is not true, I see no connection of your solution to Euclid algorithm.

              And regarding "are you sure you didn't misread the question and thought that coefficients should be {-1,0,1} even for immediate steps?" — during contest I was solving that wrong question you mentioned (however I am pretty sure you meant "intermediate" not "immediate" :)), but I realized it was not necessary some time ago and still have no clue about it.

              EDIT: Sorry, I made a typo in first version of that post in "obviously false statement"

              • »
                »
                »
                »
                »
                »
                »
                »
                11 months ago, # ^ |
                  Vote: I like it +8 Vote: I do not like it

                ah , i finally get your point , i completely forgot this during contest and just implemented it straight away thinking "its just a div1B , it can't be that hard".
                Let me think about it for a while

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  The proof isn't that hard. Start from the two polynomials fn, fn - 1. Now do Euclidean algorithm over on these.

                  You can show the following claims by induction. First, all fractions during the process will have odd denominator. Also, the numerators of a polynomial pi(x) you get during the Euclidean algo over will have even numerator if and only if the corresponding coefficients in fi(x) is 0. In particular, all leading coefficients will be fractions with odd numerator and denominator.

              • »
                »
                »
                »
                »
                »
                »
                »
                11 months ago, # ^ |
                  Vote: I like it +6 Vote: I do not like it

                okay here is a much simpler reasoning of why this takes n steps
                Suppose on the contrary , it takes  <  n steps , then for some i ,  fi mod fi - 1 has degree  <  i - 2.
                fi = fi - 1 * (ax + b) + r(x)
                degree of r(x) is less than i - 2
                let fi(x) = ... + pxi - 2 + ...
                and fi - 1(x) = ... + cxi - 2 + ... dxi - 3 + ...
                then we have p = bc + ad in , since each of them are rationals and 2 is obviously a prime , each of these terms exist in as well hence this holds in as well and we have degree of r(x) is less than i - 2 in as well which is a contradiction.

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    Just try random polynomials: one of degree n and another of degree n - 1 till it works.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Alternatively, you can set P0(x) = 1, P1(x) = x and for i ≥ 2, set

    Pi(x) = x·Pi - 1(x) ± Pi - 2(x)

    for some choice of sign. Exactly one choice of sign works once you fix $P_2(x).$ A computer can verify that this works, but I have no proof.

»
11 months ago, # |
  Vote: I like it +6 Vote: I do not like it

how to solve c and D?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    ...... ( f(x) , x+1) -> (x+1 , x ) -> (x,1) -> (1,0)

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      каждый раз надо находить такой f(x) что f(x) mod (x+1) = x (в нашем случаи ) но я так и не смог написать )

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I think Div2C Greedy problem

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please help me with my code : https://ideone.com/talzy9

      • »
        »
        »
        »
        11 months ago, # ^ |
        Rev. 11   Vote: I like it +5 Vote: I do not like it

        test
        5

        1 2 1 2 1 2

        You program is wrong Answer is "perfect"

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
          Rev. 3   Vote: I like it +3 Vote: I do not like it

          can you please explain why the answer is perfect in this case?

          EDIT : my bad now i understood thanks a lot for the help ! :)

          btw if i am correct the cases of perfect are those which don't have two consecutive ai > 1 ? if i am incorrect please correct me!

»
11 months ago, # |
  Vote: I like it +38 Vote: I do not like it

"awkwardly long and boring statements"

Lol so true

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i dont understand problem C, output sum(a[i]) E i = 0->h

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    That refers to the number of integers you are to print. The summation is nothing but the number of nodes in the tree

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div1B?

»
11 months ago, # |
  Vote: I like it +46 Vote: I do not like it

What was the purpose of putting "tree" in title of D? To give a hint for contestants :f?

»
11 months ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

For those who ask about seeing others' submissions/hacks/adobe flash player:

set these settings:

Allow website to use Flash

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i am able to see others submission history but unable to see solution even after locking!

»
11 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Lol, I hacked a few people on Div1A because they did something like cout << ans[i] where ans was of size ~10^5.

»
11 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Nice contest. Couldn't understand C for an hour and after i understand it i solved it in 20 mins. But in general nice.

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

What Div2 (A) pretest 6 ?!

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    May be something like.. 3 10 0 9 1 5 7 10

  • »
    »
    11 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Ooooh, I did break while getting input. My output in pretest 6 was: -- NO NO --

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

This is the way a codeforces contest should be prepared.Kudos to problem setters.

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Overall, the problems are good. I think ive seen Div2B & A with some changes, the C and D are so challenging. Even though, i almost made it, apparently i didnt. (._.)/, I'm actually really tired but i rushed to join this contest because i wanted to get my expert rating (AHAHAHAH), I ended up doing really sucks, and sloppy (Because of my skill in graph). Lesson I learned in this contest, sometimes you need a rest between contests. :). Merry Christmas !

Update : I think B is easier than A. A is kinda "tricky"

»
11 months ago, # |
  Vote: I like it +14 Vote: I do not like it

I've just ruined another div1 contest and now i'm thinking whether it's even possible to come up with an idea for div1B if you've never seen anything similar before -_-

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well everyone had their own bad day :(. I can relate to what you feel.

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Anybody anything to E? I can only generate 10^8 pairs as candidates for (sum of ai, sum of ai2) :/

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There will be editorial very soon, please be patient :)

»
11 months ago, # |
  Vote: I like it -25 Vote: I do not like it

Hey, is he a cheater or acts like tourist in the last cs round ? :‑Þ

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Could you explain exactly what makes you think he could possibly be a cheater?

»
11 months ago, # |
  Vote: I like it -10 Vote: I do not like it

I finished coding C/div1 5 minutes after the contest with O(n log n) solution :(

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please share your approach for this!

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      For each vertex i find the minimum vertex X such that the graph consisting of vertices [Xi i] is bipartite, this can be done using two pointers.

      Now iterate over vertices from 1 to n, for vertex i add 1 to the segment [Xi i] then answer all queries that end in this vertex by finding the sum of elements of the segment that describe the query.

      UPD: I got WA, seems like the tow pointers approach is wrong

»
11 months ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

Good contest, problem D div2 could have been better. but in total, it was way better than what you described.

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can't believe I messed up Div2 A :/ Bad day, I guess

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone hack this , or explain why fit time limit?

»
11 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Such a Great contest! thanks guys XD

»
11 months ago, # |
  Vote: I like it +38 Vote: I do not like it

 How did this guy submitted after contest ended?

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

even you can get query for big n in problem D(dive2) and make it more interest!

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Most of it was graph theory.\ I LOVE GRAPHS <3 really enjoyed it , keep up the good work.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve DIV-2 D?

»
11 months ago, # |
  Vote: I like it +12 Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In div2B why dfs gives the minimum answer.when to apply dfs or bfs i am weak at it plzz help

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess depends on the logic. I thought BFS way. You need to color root of tree at least once. Just color it in first go and this will make all childs of same color. Put neighbours in queue for bfs and go on like this. Link: http://codeforces.com/contest/902/submission/33421572

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use both bfs or dfs to solve this problem.
    Keypoint is to note that bfs or dfs produce same result in case of tree.
    Mostly people use dfs in such questions because it is shorter. :)

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div 2 problem C 902C - Hashing Trees, Testcase 2 working fine in my computer. But TLE in CF judge 33450049.I'm unable to find any TLE reason.

  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    Undefined behaviour or bug in compiler. The first is more probable. Look at the output of your program.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You mentioned "unoriginal problems", evidently I found almost similar problem of div2 A — A. New Year Transportation :D

@adamant: One doubt was this the source of motivation for this problem? :D

»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

How To Solve This Problem. Help me plz

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div 2E? I need some implementation details.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Help Post, Why my solution was getting WA? Problem My Solution. Why WA Plz Help me. To Find Out Plz.