gridnevvvit's blog

Codeforces Round #209 (Div. 2)
By gridnevvvit, 11 years ago, translation, In English

Hello!

Soon (on November 2 at 12:00 MSK) you are lucky to participate in Codeforces Round #209 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition. Pay attention to the round begining time!

Problems have been prepared by me. I want to thank Gerald Agapov (Gerald) and Ilya Los (IlyaLos) for help in preparation of this round, Mary Belova (Delinur) for translation of statements, Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

UPD1: Scoring will be next: 500, 1000, 1500, 2500, 2500.

UPD2: Congratulations to winners!

  1. cptbtptp
  2. FancyCoder
  3. Oyk
  4. E.B.
  5. orzkbc

UPD: Editorial

Good Luck!

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

Comments Comments (59)
| Write comment?
»
11 years ago, # |
  Vote: I like it +15 Vote: I do not like it

wish all participants a very happy Diwali! :)

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

I don't know in other countries how is this time for participants, but in our country in this time all of students went to school , and they can't participate in this contest .

Is there a specific reason to take this round in this time ?

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

    I dont know about your time zone but it is saturday here :D

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

      In Muslim Countries like Iran holidays is friday. and saturday is begining of a week.

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

        Ok i learned something new.

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

        is only one day holiday in a week . thats very bad :(

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

        ours is a muslim country,but we also have vacation on saturday along with friday. :)

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

    Organising in two or three different days of week and two different times will help everybody to participate.

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

Fastest system testing ever!!!

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

That was the fastest system testing I've ever seen! Great Job! :D

Waiting for updated ratings. :)

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

woah! this is certainly the fastest system testing ever on Codeforces!!!

EDIT-1: why are the testcases still not available for viewing though?

EDIT-2: now able to view the testcases. thanks!

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

Great problem set.. Thanks to the author and testers!!!

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

My skipped solution[submission:4965469] turn out to be accepted when I submit it after the contestsubmission:4967854, testdata for problem D may be too weak.

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

Thanks for the fast systest! :)

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

any solution for C ?

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

can anybody tell me what's wrong with my submission 4967509 for problem C? thanks!

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

    same with you...test case 18

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

    Nevermind :)

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

      i don't think long long is needed, because the integer is always reducing from 10^9. in terms of the code, its magnitude is always reducing.

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

    i found my mistake....if anybody would like, compare WA (4967509) and AC (4968673) yourself!

    HINT: there is just one extra character in the AC code than the WA one. :P

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

      you weren't adding the powers before. typo or logical error?

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

        umm, i knew i had to add them, but initially assumed that = would do that! so i guess this would fall under logical error.

        and since i passed the pretests, i didn't recheck it thoroughly, but after i failed the system tests, i did. that's how i found the mistake!

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

    8 2 5 5 5 5 4 4 2 0 this test case fails your solution.

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

systest is amazingly fast, but the rating update is slow :(

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

    systest is O(0.000001), but the rating update is O(n!!!!!!!) :(

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

look at this submissions:

4966994 4966935 4966174

i think they are same people!

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

I am looking forward to updating of my ranking...

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

I see 2 submissions accept in problems C are same : 4966118 and 4969298 http://codeforces.me/contest/359/submission/4966118 http://codeforces.me/contest/359/submission/4969298

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

    Chill, one of them is in virtual participation.

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

About problem C, we know that if x1 is large enough and a, m is smaller than N(=1e9+7), and x1 ≡ a (mod N) is satisfied, then gcd(x1,m) mod N = gcd(x1 mod N, m) = gcd(a,m) is good.

But if x1, x2 is large enough and a, b is smaller than N, and x1 ≡ a (mod N), x2 ≡ b (mod N) is satisfied, how to solve gcd(x1,x2) mod N ?

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

Where is the tutorial?

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

For Problem B, Did anyone else thought of this solution?

I got this solution after scribbling four pages of my book. But don't know why it is right!

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

    My solution is the same as that. But my coding is ugly...

    BTW, what book is it? It seems quite helpful.

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

    Let me explain my way of looking at it. I will take an example. n = 2, k = 1. Firstly, my permutation should have 2*n = 4 elements. For now, I do not know anything about it so let's say it is:

    a1, a2, a3, a4.

    According to the given formula,

    (|a1-a2| + |a3-a4|)-(|a1-a2 + a3-a4|) = 2*k

    In LHS of the above equation, Let's denote expression inside first parantheses as A1 and second as A2.

    Now, 2*k is always even. It means that there are 'k' terms which are being added to A1, and 'k' terms which are being subtracted in A2. One way of looking at it can be:

    A1 = C+k

    A2 = C-k

    where C is some constant.

    How can I form an expression such that k gets added in A1 and gets subtracted in A2? By reversing exactly k pairs whose absolute difference is 1!

    So, if my sequence was 4 3 2 1.

    A1 = (|4-3| + |2-1|) = 2.

    A2 = (|4-3 + 2-1|) = 2.

    Say I reverse exactly 1 pair, (2, 1) becomes (1, 2).

    New sequence = 4 3 1 2.

    A1 = (|4-3| + |1-2|) = 2.

    A2 = (|4-3 + 1-2|) = 0.

    A1-A2 = 2 = 2*(1) = 2*k!

    One more example, n = 4, k = 2. I will just give the answer. It is based on the explanation above.

    Answer : 8 7 6 5 3 4 1 2.

    Notice that two pairs (2, 1) and (4, 3) have been flipped.

    General solution: Just form a permutation sorted in descending order and flip 'k' pairs as illustrated above.

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

      Sorry for such a long post. Just wanted to be clear in what I wanted to convey)

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

      Hi, Can you please elabroate on

      Now, 2*k is always even. It means that there are 'k' terms which are being added to A1, and 'k' terms which are being subtracted in A2

      Regards, Nitin

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

        One way of achieving a 2*k difference in (A1-A2) is to have 'k' terms of value '1' in A1 which are being added, and the same 'k' terms subtracted in A2.

        Flipping the pairs of numbers helps in doing this.

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

I dont know why my problem C isnt working. Hope the editorial comes in fast. Is there a way to see the entire testcase, I mean when I see the test case on which my soln failed it shows — finite numbers and then "..."

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

what would be the ans for prob C for this test case

2 6 3 3

and why???? please explain me .............

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

    6 is not a prime :) so invalid

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

    even i wasted a lot of time thinking that a factor of x could reduce the denominator and hence would have to be accounted for. then i reread the problem and saw that x must be prime. started coding the solution immediately after that! :)

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

Is tutorial coming?

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

Is O( 2*N (lg N)^2 ) solution passes for problem D??? N=3*10^5 .

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

    Depending on how well written it is, it would be possible for it to pass, but my O(40N) takes 0.35s, so it might just TLE.

    EDIT: Mine is . I forgot about GCD working in . So yeah, it should pass.

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

    i think my solution is O(N * lg n ^ 2) in best form and O(N * lg N ^ 3) in worst form. (but im not sure!) it get accepted in 1300ms. i Think Your Solution will be accept too! here is my solution : 4967080

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

http://codeforces.me/contest/359/submission/4979724

This is my submission for D. I picked a number and guessed it as my current gcd. then I did a binary search on my pre-computed segment tree. By this i tried to find a L and R for each position i so that gcd(L to R) = arr[i]. I think it takes O((lgN)^2) and the outer loop of N makes the overall complexity O( 2*N (lg N)^2 ). But it is getting TLE on case 10 where N=3*10^5. Is it a problem with my implementation.

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

    That's just what I was talking about above, that a well-written solution would pass. In this case, there's an additional factor of to the complexity, so a segment tree, which has a large constant compared to some other approaches (sparse table for example), can get TLE.

    Seeing as it takes 1.5s on case 9 with N = 2·105, it probably just needs some small optimization to pass.

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

      Thanx a lot Xellos & MiRZA(I don't know how to tag a nick:( )for your gr8 help. Finally Got AC! Same code just replaced the Segment tree portion with sparse Table. Totally new experience for DS beginner like me. Time Limit was 1341 ms, and i am happy with it. Thanx again.

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

        "Tagging a nick": When you write a comment, there's an icon on the top panel (yellow, blue and red stripes). Click on "User" there.

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

        Your Welcome ;)

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

Wow! All problems by one person!

→ Reply