cyand1317's blog

Codeforces Round #418 (Div. 2)
By cyand1317, history, 8 years ago, In English

418 I'm a teapot

Hi everyone! >///<

I'd like to invite you to Codeforces Round #418 which begins at 15:05 MSK on 7 June. Please note that the timing is unusual.

This is my first round here! KAN reviewed the contest and helped me through the preparation process, while Alladdin, FalseMirror and Tommyr7 tested all the problems, and MikeMirzayanov and the awesome Codeforces and Polygon platforms made all this happen miraculously. This wouldn't have been possible without your efforts!

The round is rated for the second division, and participants from the first division can take part out of competition. As usual, there are five problems and two hours to solve them. The problems will feature... Well, let's wait and see :)

The scoring distribution will be announced later.

Hope everyone few bugs and fair ratings. Looking forward to seeing you then!

UPD 1 Scoring will be 500-1000-1750-1750-2500. It's recommended to read all problems' statements so as to find the problems that suit you — we tried quite hard to make them clear and interesting.

UPD 2 The round is delayed for 10 minutes due to technical issues. Apologies.

UPD 3 System test is done. Congratulations to the winners!

Div. 2 Top 5

  1. memanon
  2. marmoset
  3. liu_runda
  4. yieldar
  5. Krydom_Yuudachi

Overall Top 5

  1. xumingkuan
  2. HellKitsune
  3. natsugiri
  4. yancouto
  5. irkstepanov

Hope you all enjoyed the contest. You all did a great job! The editorial is on the way, please be patient :)

UPD 4 For the impatient, here are the tutorials for problems A to C. More are coming!

UPD 5 The complete editorial is out. Cheers!

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

Comments Comments (233)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +110 Vote: I do not like it

Is it rated?

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

Just in case anyone is scratching their head: https://httpstatuses.com/418

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

why always scoring distribution is announced later ?

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

    it's just because you have no girlfriend.

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

      codeforces is not a place for such shitty jokes.

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

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

          purple guys are allowed to say everything

          and blue are not

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

            I would like to prove you wrong by typing that comment, but I prefer to keep my contribution. It is not purple, but it's because the guy is Bredor. Look through his comments and you will know.

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

            And don't copy-paste buddy.!Be creative and make your own jokes..!

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

          Bredor is a famous troll and everyone knows he writes sarcastic comments all the time.

          While your comment was ill-timed and not even funny.

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

Hmmm... It seems like Alladdin and amethyst3 are brazzers

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

Hope to see a

NORMAL CF ROUND

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

    What do u mean by "Normal CF round"?

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

      3000 — A 2000-B 1000-C 500- D 50-E *Numbers of Accepted submissions

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

        500-D ?? that's normal ?

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

    You mean you're waiting for the delay ?

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

As a tester, wish everyone good luck and have fun!

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

Haven't seen a Chinese round for ages. Cool.

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

Hope it could be easier than last Chinese Round

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

418 I'm a teapot so for this round you will enter as a normal water(current rating )and exit as hot water(current rating+154).

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

    For what it's worth, I hope you're right.

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

      It's only for my current rating and to need for make me pupil . But for you it's maybe 129.:D

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

        Yeah I noticed, but getting 154 wouldn't be bad for me either :D

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

          I hope you make this done but in my case for getting 154 need more heat that's so hard .

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

            It is easier to get +154 rating with current 1046 rating, than getting +129 with 1771 rating.

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

The time when the contest will be started it is 'Iftar Time' (Fast Breaking Time) for Muslim in southern Asia. It will be better and helpful to us if the contest starts an hour later from that time. cyand1317

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

    Meanwhile it would be quite late for participants from eastern Asia, it's just difficult to meet everyone's needs... :( If the timing does create difficulties, you can try virtual participation later. Apologies for this.

    (It would be great if authors have a list of different regions' occupied time intervals...)

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

Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).

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

    It should be 500 — 1000 — 1750 — 1750 — 2500 right?

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

      Teapots also make mistakes like humans do... You know.

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

Have you noticed that the round number is the reversed contest number ?

Contest number is 814 and the round number is 418.

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

Problem C and D have the same score!Amazing!

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

A 1750 C always makes me upset :(

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

Data structures and Constructive algo related problems may be exist in today's round...mathematical term too :)

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

10 min extensions seems to be a template.

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

Contest extended by 10 mins ... :)

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

contest delayed?

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

10 minutes fact!!!!!!!!!!!!!!!!!

Coding ended(Ramadan and Iftar fact).

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

Everytime :(

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

Contest Delayed , Maybe a good time for more contribution .

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

It won't be a normal Codeforces round if it is not delayed :D

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

Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).

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

10 minutes delayed???

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

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

A Codeforces contest really cannot be regular without a 10 minute delay, can it :)

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

clicked 'ok' to go to contest arena and then 10 minute delay!

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

Show the time of the contest 10 minutes later so then u don't have to delay it every time !

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

why there's always 10 minutes delay?

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

10 mins again

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

10 minute delay is a tradition now in Codeforces

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

May I ask, what kind of of technical issues causes delay by 10 mins?

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

A ten minute delay for me to make a beverage, thank you!

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

6000 People registered for the contest. 10 minutes delay means 6000*10 minutes = 1000 hours = 41 days of their life. Just saying. Waiting sucks.. :(

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

normal codeforces round = The round is delayed for 10 minutes due to technical issues

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

It's about Monogatari! Now it is somewhat interesting. 8-)

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

    There's some spoilers in task statements lol(but I had already completed mongatari series).

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

      I am only mid-way through the series, and I am pretty sure I got spoiled by B,C,D — but who cares! I should be fine as long as if I don't lookup for the characters' name in English.

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

        Actually you don't) Especially B, C and D, they have nothing to do with the plot. While E is taken from the first episodes you would watch.

        I kept that in mind while writing statements so as not to contain spoilers to the anime.

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

          lol, after reading A and E I assumed that the others are about the actual plot as well.

          Good job for not spoiling the amazing series. :)

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

            I should have mentioned that in the announcement ._. Did this scare some of you away?

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

              The oddity within my buggy code did scare some of me away. :P

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

                Does that part of you want to go home for now? Is Mayoi visible?

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

                  The debugger window shows traces of Mayoi within my recusion loop right now.

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

Anyone else facing the issue of getting logged out constantly? I had to login at least on five separate occasions during the contest. Not complaining, genuinely want to know whether mine was an isolated case or not.

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

this B made me crazy
waiting for the end of contest to see test 6

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

    also test 2 : In the second sample, 5, 4, 2, 3, 1 is the only permutation to satisfy the constraints.

    dive me crazy , why 4,4,5,3,1 is not accepted !!

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

      Because {4, 4, 5, 3, 1} is not a permutation of the numbers from 1 to 5.

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

        uh, well
        i also misunderstood this point

        thanks

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

        i made the permutation but still getting WA on 9.

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

        can there be more than than 2 positions where ai != bi??

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

          no , one or two , it can't be more than 2 differrnces

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

          No

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

            now i got the mistake, i found no. not appearing in a and find the it's correct position. but position was not found correctly in my case.

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

      It's a permutation. every integer from 1 to n must appear exactly once

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    1.*No number should repeat itself in the list*(I guess testcase 6 stuff!!)
2.Final list should only differ by 1 from list 'a' and list 'b'
    → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In problem C, n*q should pass but my solution got TLEd on pretest 10. :/ why?

I used sliding window, total operations 2 * 1500 * 200000 = 6 * 108

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

    Repeating answers are there. Total answers are 26*1500. Store them.

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

      Yes, there are 26 * n possible answers and you can precalculate them all in O(26 * n^2) using two pointers.

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

    I am afraid that is a bit too slow for a 2s TL, while there exist an O(n^2 * 26) solution.

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

      What exactly?

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

      why the n^2 ? I think a 2-pointers solution should run in O(n*26)

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

        I just preprocessed every single combination that could possibly appear in the query, i.e. for each character O(sigma = 26) and each segment [l, r] O(n*n).

        I don't think you could solve it in O(n*26), even for a sliding window 2-pointer solution it should take O(nq) or O(n*n*26) — but hey! It's surprising to learn that someone solved the question in O(n*26), would you share your method to me?

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

          Oh sorry I was mistaken. it's a O(n^2 *26) as well . I forgot the original loop that considers all cases of m.

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

    Usually 1 sec is equivalent to 1e8 operations.That's why your solution exceeded the time limit. Btw I implemented an O(N*N*26) solution.

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

    My (26 * N2 * log(n)) solution 27641415 got AC which is also around 6 * 108

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

    Same here bro :(

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

    Hello, using cin.tie() and cout.tie() works fine :)

    My submission

    Even I also got TLE in beginning, but then I just uncommented one line(First line in the main function)

    My first submission with TLE

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

What is intended complexity of B solution? I solved it in O(n) and now i'm scared that i've missed something.

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

    My complexity is same. P.S. 70 lines of code...

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

      Yeah, about 80 for me. Hope it's okay...

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

      Mine 61 with a 13-line fast read... Am I missing something?

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

        Mine 15 line code in python

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

    I think it's solvable in O(n) but there's a simple O(n^2) solution: find the two positions in the first array which has the same value(there will be exactly two of them). Replace one of those two positions with each of 1~n and verify if it's valid.

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

And how to solve D?

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

    Not sure if I will get AC, but I constructed a tree, where x is parent of y if circle y is inside x. Then dp: f[u][x]=maximum area of subtree u if there are x nodes in the first set.

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

what is generator command line argument ??

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

Is the following solution to D correct? It passed pretests, but I'm not entirely convinced. If circle is inside odd number of circles or 0 circles add its area, else subtract its area.

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

    i did the same

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

    I did DP on graphs

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

    I think the expected solution is a DP.

    If I understood your algorithm correctly, your algorithm should fail on this case:

    Edit: Incorrect test case

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

      Actually the answer here is the area of the large circle + the area of the second largest, which is the same as my algorithm.

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

        Ah you were right. I think that solution should AC

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

    How do u check how many circles it is inside.

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

      You just do O(n^2) to check how many circles contain a particular one.

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

        No. Like there are 2 circles. How do we check if one if inside the other?

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

          Distance of two centers is smaller than the difference of two radius

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

    Yes,its true!If we're taking the outermost circle(not covered by anyone) as a single unit it

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

Great round!

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

I must be misunderstanding problem C. Can someone explain to me why this solution is wrong?

For each subsequence of s and each character c:

  • moves = count of c in subsequence
  • best[c][moves] = max(best[c][moves], length of subsequence)

Then for each query (m,c) just output best[c][m].

I'm pretty sure my code has no bugs but I keep getting WA on pretest 7.

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

    I did the same and passed pretests, maybe you are forgetting best[c][moves]=max(best[c][moves],best[c][moves-1])

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

      Actually I took care of that too, but still WA. :(

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

    maybe forget best[c][moves] = max(best[c][moves], best[c][moves — 1]) ?

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

    best[x][y] can't be greater than n.

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

    Haha nevermind, it was a stupid bug where I mixed up the indices of i and c at one point. Good thing this round is unrated for me. :)

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

I solved B but i'm interested how did you guys solve it??

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

    You didn't XD

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

    Let res be the permutation we need to find. Now it is easy to observe that there can be only at most 2 numbers missing in res according to given a and b arrays. Now find those missing numbers and assign those numbers in missing places in res and check if the res is valid or not.

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

Yeah, it's time to compile error in 20 seconds before the contest ends(27649694).

The reason was that locally I have kotlin 1.1, but cf has only 1.0. Comp error appeared twice in this contest. So sad =(

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

What is solution of Task C? I think there is pre-calc and DP, but what is rule for dp of this problem?

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

Thank you Chinese for this round :D

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

Very fast System testing!!!

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

I was logged out several times (using google account) which is not nice. Please fix it!

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

What's the intended solution for E? I drafted a O(n^4) (roughly) DP solution for it yet somehow it fails me even on the sample test cases. :/

http://ideone.com/kOBovo

Edit: nvm, I am completely off the track.

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

RIP B

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

What is f**cking going with cf? Why I'm loosing task because of compilation error with "M_PI" in GNU C++14, although it's work on my compiler, which is GNU C++14 too?

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

    Show us the code

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

    Just googled online and it appears that it has been removed from the C++ standards, RIP.

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

      Okey, thanx. Now, there is question, why it's still working in compiler in linux?

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

        Maybe your compiler is different than cf's.

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

        I am not sure about this — but this stack overflow post might be helpful: https://stackoverflow.com/questions/29264462/m-pi-not-available-with-gcc-std-c11-but-with-std-gnu11

        The first answer also mentioned a post: "GCC 4.9 when used with -std=c99 doesn't define M_PI, but does when used with -std=gnu99", maybe it's about the -std=gnu flag, as it is also used by CF.

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

          But I'm using -std=c++14.

          Okay, maybe it's because of different in Linux and Windows compiler.

          Thank you, for helping solve my problem, it's just blow my mind, because it was possible to enter to div.1.

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

      Yeah, but GNU C++ should include it. Maybe its because CF runs on windows?

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

    it's not cf fault :|

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

    I experienced exactly the same thing when preparing the round. Perhaps you could just add an extra #define... Well, as long as something's learnt you're improving yourself =)

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

I can't understand why Reyna solution 27632209 for problem A got WA?!!!

Checker comment Can't find file C:\Contesters\Work\invoker-prod\work\codeforces2\e034999a3f1f1dd18b018c40c84c8c46\check-f7e8e87d48909eaa32eeaee49e520cf4\run\output.fd0138e687.txt.

What is the meaning of that?!!

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

    Looks like cf error(look at the checker comment).

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

    500 Internal Server Error :-)

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

    Something's broken, we will fix that.

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

Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).

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

why i got a wrong answer like this？

Can't find file C:\Contesters\Work\invoker-prod\work\codeforces2\838e4a3610786f013367ecfa30b8ac63\check-b58f02c6459228487139e47a79e2e72e\run\output.fd0138e687.txt.

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

What was the approach to solve problem B?

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

    Just split in two cases, one with only one number who differs, and another with two, use a set in the first case (you need to know the number who is missing) . And in the second case, generate the two possible vectors and use two sets, insert each vector in a different set, and print the one with setsize == n.

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

      Thanks for your reply, I also read the editorial and your approach is different and also interesting. I think your approach is more efficient, is it O(n)? The editorial approach is O(n^2) I think

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

    ok, at first, there is a simple observation. a and b can only have at most 2 different positions where the numbers aren't same. So you should think of these 2 cases.

    Case 1 : Only 1 different position(Sample testcase : 3) Here, u should check which is the missing number from 1 to n, and put that into that position

    Case 2 : 2 different position (Sample testcase : 1, 2) Here, there should be 2 missing numbers from 1 to n. try putting them into those positions and see if the permutation is valid. One of them will be valid and that's your answer

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it 
      there should be 2 missing numbers from 1 to n

      How so? I think even in case 2 there can will be only one number that differs ?

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

        I think u don't understand what did I mean with missing numbers. ok, look at these. 

        4 4 2 3 1
5 4 5 3 1
? 4 ? 3 1

        so we know for sure, 1 3 4 is in the permutation and 2, 5 hasn't been used yet. So these are 2 missing numbers which should be used in these two (?) positions

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

After seeing the system test, I wish I worked on hacking B. I saw no one was hacking B and thought maybe those pretests were quite good. Alas!

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

Why does greedy approach work in D? In each step of dfs(start from outer circle) try to put new circle to part where it gives positive area. http://codeforces.net/contest/814/submission/27649536

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

    Well, if we put a new circle (call it "Ci") to part where it gives negative area instead of part where it gives positive area, we lose 2 times of circle Ci's area. No matter how we divide the circles in circle Ci into 2 parts, each part will contribute less than circle Ci's area, so the sum is less than 2 times of circle Ci's area. So it's better to put new circle to part where it gives positive area.

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

What was wrong with test case 22 in B? My output seems to be correct? :/

http://codeforces.net/contest/814/submission/27638764

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

    your output differs from sequence b in more than 1 position (first and last positions)

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

      Then Test Case 21 would have given WA as well! Same goes for 18!

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

        in tc18: your output mismatches sequence a in only one position (third position) and mismatches sequence b in only one position (first position) so it is correct

        in tc21: your output mismatches sequence a in only one position (fourth position) and mismatches sequence b in only one position (first position) so it is correct

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

        nope. look closely. your output should differ exactly in 1 position. Test case 21, 18 is alright.

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        please help me to understand the below solution has loop as (in main()) for(w=1;w<=9000000000000;w++)  {  r=r+2;  } even then why its not giving TLE?
        link here
        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How my code for Problem C got accepted? I made ans[2000][26] in my code and i was using ans[x][26] in my code. (Due to linear storage of data in cpp? )

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

Can anyone tell why my C fails? Thanks a lot.

Basically for each alphabet I created a vector of <Cost, Profit> where Cost number of color is to be recolored and that would result in a subsegment of that color of at least length Profit. And for each query I just find the upper bound base on m and calculate the answer.

http://codeforces.net/contest/814/submission/27647932

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

    28 aaaabbbaaabbbbbbbbbbaaaaaaaa 1 3 a

    You'll choose to fill change it into aaaaaaaaaabbbbbbbbbbaaaaaaaa (gives 10) wheareas aaaabbbaaabbbbbbbaaaaaaaaaaa is better (gives 11)

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

Rating update please. I will be expert for the first time :)

It is really very good feeling!

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

Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).

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

didn't know CF compiler was so fast that it would support complexity of O(2e5 * 1e3) or O(n * q) for C

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it 
please help me to understand the below solution has loop as (in main()) for(w=1;w<=9000000000000;w++)  {  r=r+2;  } even then why its not giving TLE?
link here
→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Pretest so weak, FST so much . TnT...

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

Please note that the ratings are not final now and are going to change a bit because of the issue with a couple of submissions. We will rejudge them and update the ratings, don't worry.

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

Did anyone else assume the garland to be circular. :(

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

    Yes, it's my carelessness not to mention that it's linear... Though the word "garland" in CF has been used to refer to linear lists quite a few times. Apologies for this. T^T

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

This is the biggest increase of rating ever in codeforces Right ???

This is the biggest increase even after he was hacked on A and B.

(If you can't see the photo click here)

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

    Well this is weird ... on Mhammad1's profile it shows that his rating change is 803 but on the friend's rating change list it shows that his rating change is 681 ... is this a bug ???

    On the friends rating change list it shows that his rating before the contest was 100 but it actually was -22 ???

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

Please Help! Why does testcase 6 fail? Submission

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

    You are expected to output a permutation of first n number with given condition. Your output have 4 repeated.

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

I solved the D without DP and it worked. code

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

    Yes, greedy seems to give AC for this. :D Congrats :p

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

For question B, I ran my code in c++14, it gives the wrong answer on test 39 but the same code i tested on c++11 (also on my machine), it gives the correct answer. If is a cf bug? here is my code http://codeforces.net/contest/814/submission/27655109.

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

    In the function findNum, you check temp[i] != 1 without previously initializing the temp array. So it's up to the compiler to initialize that array with anything (even 1s). The same solution with explicit initialization passes in C++14: 27657207

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

The first letter of the second word of the problems' name are "aeiou", and prepositions are also different. Interesting name ~ :).

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

Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).

→ Reply