cyand1317's blog

By cyand1317, history, 6 months 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, neckbosov 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

Overall Top 5

  1. xumingkuan
  2. HellKitsune
  3. natsugiri
  4. MakeYanGreatAgain
  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  

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

Is it rated?

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

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

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

why always scoring distribution is announced later ?

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

    it's just because you have no girlfriend.

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

      codeforces is not a place for such shitty jokes.

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

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

          purple guys are allowed to say everything

          and blue are not

          • »
            »
            »
            »
            »
            »
            6 months 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.

          • »
            »
            »
            »
            »
            »
            6 months 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..!

        • »
          »
          »
          »
          »
          6 months 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.

»
6 months ago, # |
  Vote: I like it -43 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Hope to see a

NORMAL CF ROUND

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

    What do u mean by "Normal CF round"?

    • »
      »
      »
      6 months 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

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

        500-D ?? that's normal ?

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

    You mean you're waiting for the delay ?

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

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

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

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

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

Hope it could be easier than last Chinese Round

»
6 months 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).

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

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

    • »
      »
      »
      6 months 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

      • »
        »
        »
        »
        6 months 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

        • »
          »
          »
          »
          »
          6 months 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 .

          • »
            »
            »
            »
            »
            »
            6 months 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.

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

              If God bless me and understand the problem statement !

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
              Rev. 3   Vote: I like it -10 Vote: I do not like it
              int now = Expert(Diversity); // normal water
              int tmp= 154 + 129 + 35(from : rafsan35 );
              int add= tmp/ 6 ;
              now+=add;// Hottttttttt !
              if(now== candidate master(Diversity)){
                  puts("Hellow  candidate master Diversity");
              }
              else{
                puts("Worng ans Bro ! ");
              }
              
»
6 months 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

  • »
    »
    6 months 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...)

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

    Suitable for me in Bahrain because it ends an hour before iftar haha

»
6 months 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).

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

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

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

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

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

the time is too unusual

»
6 months ago, # |
  Vote: I like it -108 Vote: I do not like it

I am new to this fantastic BLOG where i see many people helping each other out with out any self interest, i am a newbie here and i apologies in advance for any mistakes i might make here ..... http://www.europadtours.com

»
6 months 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.

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

Problem C and D have the same score!Amazing!

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

    They also recommended to read all problems' statements so as to find the problems that suit you

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

A 1750 C always makes me upset :(

»
6 months 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 :)

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

10 min extensions seems to be a template.

»
6 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Contest extended by 10 mins ... :)

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

contest delayed?

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

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

Coding ended(Ramadan and Iftar fact).

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

Everytime :(

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

Contest Delayed , Maybe a good time for more contribution .

»
6 months 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

»
6 months 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).

»
6 months ago, # |
  Vote: I like it -9 Vote: I do not like it

10 minutes delayed???

»
6 months ago, # |
  Vote: I like it -16 Vote: I do not like it

»
6 months 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 :)

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

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

»
6 months 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 !

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

why there's always 10 minutes delay?

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

10 mins again

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

10 minute delay is a tradition now in Codeforces

»
6 months 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?

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

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

»
6 months 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.. :(

»
6 months 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

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

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

  • »
    »
    6 months 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).

    • »
      »
      »
      6 months 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.

      • »
        »
        »
        »
        6 months 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.

        • »
          »
          »
          »
          »
          6 months 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. :)

          • »
            »
            »
            »
            »
            »
            6 months 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?

            • »
              »
              »
              »
              »
              »
              »
              6 months 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

              • »
                »
                »
                »
                »
                »
                »
                »
                6 months 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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 months 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.

»
6 months 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.

»
6 months 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

  • »
    »
    6 months 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 !!

    • »
      »
      »
      6 months 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.

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

        uh, well
        i also misunderstood this point

        thanks

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

        i made the permutation but still getting WA on 9.

      • »
        »
        »
        »
        6 months 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??

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

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

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

          No

          • »
            »
            »
            »
            »
            »
            6 months 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.

    • »
      »
      »
      6 months 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

  • »
    »
    6 months 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'
    
»
6 months 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

  • »
    »
    6 months 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.

    • »
      »
      »
      6 months 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.

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

    Pretest passed for me using the same,maybe it'll fail systest

  • »
    »
    6 months 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.

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

      What exactly?

    • »
      »
      »
      6 months 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)

      • »
        »
        »
        »
        6 months 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?

        • »
          »
          »
          »
          »
          6 months 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.

  • »
    »
    6 months 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.

  • »
    »
    6 months 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

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

    Same here bro :(

  • »
    »
    6 months 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

»
6 months 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.

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

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

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

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

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

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

  • »
    »
    6 months 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.

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

And how to solve D?

  • »
    »
    6 months 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.

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

what is generator command line argument ??

»
6 months 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.

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

    i did the same

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

    I did DP on graphs

  • »
    »
    6 months 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

    • »
      »
      »
      6 months 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.

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

        Ah you were right. I think that solution should AC

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

    How do u check how many circles it is inside.

    • »
      »
      »
      6 months 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.

      • »
        »
        »
        »
        6 months 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?

        • »
          »
          »
          »
          »
          6 months 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

        • »
          »
          »
          »
          »
          6 months 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
  • »
    »
    6 months 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

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

Great round!

»
6 months 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.

  • »
    »
    6 months 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])

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

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

  • »
    »
    6 months 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]) ?

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

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

  • »
    »
    6 months 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. :)

»
6 months 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??

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

    You didn't XD

  • »
    »
    6 months 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.

»
6 months 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 =(

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

Why remove my point in example test??

»
6 months 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?

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

Thank you Chinese for this round :D

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

Very fast System testing!!!

»
6 months 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!

»
6 months 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.

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

RIP B

»
6 months 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?

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

    Show us the code

  • »
    »
    6 months 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.

    • »
      »
      »
      6 months 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?

    • »
      »
      »
      6 months 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?

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

    it's not cf fault :|

  • »
    »
    6 months 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 =)

»
6 months 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?!!

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

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

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

    500 Internal Server Error :-)

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

    Something's broken, we will fix that.

»
6 months 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).

»
6 months 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.

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

What was the approach to solve problem B?

  • »
    »
    6 months 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.

    • »
      »
      »
      6 months 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

  • »
    »
    6 months 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

    • »
      »
      »
      6 months 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 ?

      • »
        »
        »
        »
        6 months 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

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

          I think I get the idea. I will read your code submission to understand it :)

»
6 months 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!

»
6 months 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.com/contest/814/submission/27649536

  • »
    »
    6 months 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.

»
6 months 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.com/contest/814/submission/27638764

  • »
    »
    6 months 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)

    • »
      »
      »
      6 months 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!

      • »
        »
        »
        »
        6 months 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

      • »
        »
        »
        »
        6 months 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.

      • »
        »
        »
        »
        6 months 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
»
6 months 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? )

»
6 months 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.com/contest/814/submission/27647932

  • »
    »
    6 months 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)

»
6 months 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!

»
6 months 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).

»
6 months 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

»
6 months 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
»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

Why I got skipped??? I'm sure I didn't copy other people's code.

»
6 months 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.

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

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

  • »
    »
    6 months 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

»
6 months 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)

  • »
    »
    6 months 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 ???

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

What is this? I got the same code accepted when I submitted it with GNU 14. But got screwed during the contest as I got TLE with the old GNU 5 version. This is clearly unacceptable.

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

Please Help! Why does testcase 6 fail? Submission

  • »
    »
    6 months 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.

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

I solved the D without DP and it worked. code

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

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

»
6 months 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.com/contest/814/submission/27655109.

  • »
    »
    6 months 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

»
6 months ago, # |
  Vote: I like it -13 Vote: I do not like it

The problems sucked !

»
6 months 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 ~ :).

»
6 months 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).