ikar's blog

Good Bye 2013
By ikar, 11 years ago, translation, In English

Good day)

Welcome to the last Codeforces round in this year Good Bye 2013. This round will be unusual because it will be common for participants of both divisions.

The problems were prepared by authors Gerald Agapov (Gerald) and Svechnikov Artur (ikar). Pavel Kholkin (HolkinPV) and Vitaly Aksenov (Aksenov239) also help us to prepare the problems. Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

UPD: Score distribution is similar to standard — 500-1000-1500-2000-2500-3000-3500

UPD2: Thanks to all participants, we hope everyone enjoyed prepared tasks. Problem analysis.

UPD3: Congratulations to the winners of the last round in this year. Rating will be changed in a few hours.
1. BaconLi
2. Egor
3. liympanda

We wish everyone good luck, high rating and excellent mood)

Announcement of Good Bye 2013
  • Vote: I like it
  • +347
  • Vote: I do not like it

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

Is there a handle changing feature?

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

    No, you can only choose the handle name when you register, then you will not be able to change it later.

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

      Maybe you misunderstand him, usually at the end of every year there's a gift from codeforces to its users, last two years it was allowing to change the handle and ahmed.korayyem asked if codeforces will allow changing handle this year too.

      BTW, why are you surfing codeforces in incognito mode?

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

        Oh, sorry for my misunderstanding.

        Actually I use normal mode when surfing on codeforces, but when I want to visit codeforces "register" page without logout I have two options, open other browser software or use incognito mode, but it's faster to use incognito mode, so I use it :)

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

      Actually it happened last year. (http://mirror.codeforces.com/blog/entry/6290)

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

    I would like to change my handle this year too as a Codeforces gift.

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

      Hello, but gifts are things other people give to you. They are not things you request, and then get.

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

        I mean, I could be happy if I see a Mike post saying: "You can change this year your handle as a Codeforce gift like last year. Enjoy it."

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

It seems this contest would be rate?

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

Although have lessons tomorrow morning, going to take the one of the most important contest:) That's why I love Codeforces!

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

    Just want to get a good ending for this year.

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

ahh... at last a post about 'Good Bye 2013'.

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

will the problems be as hard as div2 contest or div1 contests?

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

    happy new year to all ... last contest of this year ..... so get highest rating .. wish u all the best for all

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

Good luck!!!

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

Advanced Happy New Year to everyone :)

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

Can we have hints on problems' difficulty? I can't imagine how the contest is going to be rated and the same problems will be for both divisions!

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

Good Luck to everyone...!!! And Happy New Year...!!!!!

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

how many problems there will be??and i think as the contest for the end it would be better to have extra duration.

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

Well, actually it's good bye GPA! Having an exam tomorrow out of 30% and I still don't know what the course is all about and yet I'm taking part in this contest :D :D

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

GL HF everybody :D Happy New Year 2014

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

Also, good fun && have luck!

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

I never really understand why the score distribution is announced during the last minutes before the contest? Can somebody explain me this? :)

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

    One million dollar question !

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

    For this contest, obviously to hide the fact that there are 7 problems instead of 5 :3

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

"Score distribution will be announced before the contest."

contest starts in 30 seconds!

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

Happy new Year! Good luck in new year!

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

Can anyone tell how solve 379F - New Year Tree ?!

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

On problem C I made this:

while (vet[u] <= l) ++vet[u];

I realized that it would time out after locking :/, but then I remembered that GCC might optimize this stupid mistake I've made, and it did! :D Bye bye 2013!!

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

    Holy random? I successfully hacked person with while(v[i].a<=v[i-1].a) v[i].a++; and g++ too:)

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

      I failed to hack someone's code that had a similar loop and I was wondering how did his code pass! Now I've got the answer!!!

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

      can u please expain what is wrong in this loop ?

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

        Simulate the code with this test:

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

Good bye Codeforces Round for this year...

Insha'allah... we will meet again... :)

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

We get "Happy New Year!" instead of "Accepted". So nice!

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

At first, thanks for this great contest! I enjoyed it very much except for one thing.

Because of "Codeforces is temporary unavailable", I lost some hack points that I should be able to get... Although it's my fault that I came up with a powerful corner-case late, but why codeforces server have been weak for a long time in spite of much demand? I really want codeforces team to strengthen the server...

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

Any better idea on D than a hardcore DP + Euclid's Extended Algorithm (which i didn't manage to implement, by the way).

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

    My solution was something like this:

    Let X = s1, Y = s2. We count the number of appearances of X, Y, XY, YX, YY (you can prove that XX doesn't appear). In the latter three, at most one "AC" can appear, so you bruteforce all 8 possibilities. You don't need Extended Euclidean; the bounds n, m ≤ 100 are very forgiving for an immediate brute force.

    (I'm not sure what you mean by hardcore DP. In my opinion, my solution above is not DP at all, so probably different solutions.)

    (My solution turns out to fail, so it might not be the correct approach. Take the above with loads of salt.)

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

      WA 23?

      I have the same solution and got wa 23 : \

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

        You must prevent overflow while calculating count of AC's in tested variant.

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

      No, your solution seems ok, I simply missed the fact that I can brute-force through all cases in ax+by=x, your solution was the same as mine. What i called hardcore DP were some recurences I used instead of simple formulas to write the solution faster in order to calculate the number of X,Y,XY,YX,YY,XX (that's why I used DP, I didn't have to treat cases like nu XX and different formulas). Somebody else also told me about this solution and his also failed because of www.wolframalpha.com/input/?i=50th+fibonacci+number (int instead of long long)

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

    My solution has a recursion to calculate the how many AC are in kth term, inside a dp that generates a possible second starting string, inside another dp that generates a possible first string. Is that hardcore enough? :p

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

      Yes, it is. Your recursion used memoisation I supose? Can you explain a little bit more of your solution, please?

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

        Well, at first I thought knowing the number of AC in each of the first string would be enough. If no. of AC in first is 3 and in second is 4, then the third will have 3+4 = 7. Then it will continue like fibonacci sequence. But then I realized, what if the string is like this ABBBBBA and CBBBBC.

        Even though the first and second string has count zero, third string has count 1. So, in order to generate the sequence, I must know the starting and end letter of each string, along with the count of AC.

        So I used dp to generate the first string. Only three letters would be used in the string, A, C and any other letter ( I used B ). So the parameter was dp ( first letter, position in the string, last letter used until now, number of ac ). At each position I could place one of the three ABC. I proceeded accordingly.

        Once I reached the end of first string, I called for the second string right from there. I had to carry few information from first string to the second. The first and last letter and number of AC in the first string. Apart from these, everything else was same for the second string.

        So the second dp parameter was this dp2 ( first letter of first string, last letter of first string, number of ac in first string, first letter in second string, position in second string, last letter in second string until now, number of ac in second string ).

        Once I reached the second string, I called a function to calculate kth term. I passes the following info to the function recursion ( f1, l1, ac1, f2, l2, ac2 ). Using this info, I could calculate kth term in O(k).

        Here is my submission: 5581341. Seems like a lot of calculation but it's really not a lot. Each of the table is filled only once.

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

    Bruteforce. Count of "AC" in s1, count of "AC" in s2, first and last letters of both strings ('A', 'C', or any other). And then for that information we can calculate count of "AC" in k-th string.

    And total time is (n / 2) * (m / 2) * 3^4 * k ~ 10^7.

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

Can someone explain why my submission to D fails?

http://mirror.codeforces.com/contest/379/submission/5584738

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

    3 1 1 1

    Answer is:
    A
    C

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

      Thanks,yes I forgot to take into account the case (n==1) || (m==1)

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

      hey, how did u move to the next line without leaving an extra line (between A and C)? i didnt know it was possible to do that without using Block option.

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

        All we need is just some
        magic =)

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

the Accepted verdicts have been changed to Happy New Year! how cool is that? :)

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

    Now, if someone had 0 accepted submissions, they're also in for a bad year :)

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

Did you guys notices that in status page instead of accepted, it is showing happy new year ??

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

Happy New Year! instead of Accepted ....

Nice way to wish us... :)

Like this innovative idea ... :)

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

What a perfect contest! I loved it so much! I would like to thank all of the authors and the preparation team! Happy new year to everyone!

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

fail of the year? 5573462

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

    how? o.O

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

      It is not enough time to write 300000 long long numbers with cout. His solution wrote only the part.

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

    sync_with_stdio to false?

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

      he didn't use cin/cout, so sync_with_stdio wouldn't take affect must be the sort function with terible random then o.O

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

      I try it with sync_with_stdio(false) but still TimeLimit :-??

      with sync_with_stdio 5586030

      with scanf and printf 5586108

      both of them TLE :D

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

        Try it one time with int instead of long long.

        In general case using long long costs so more than int.

        Wish it works in your case.

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

    It is surprising, I used cin/cout and it passed

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

      There are two sort in this, which accounts for double the runtime. And then adding to that, there is the cout function.

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

        It's surprising. I got accepted with two sort functions and using cout : 5578740

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

      He didn't pass references in sort comparator.

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

Problem A is exactly same as uva 10346 — Peter's Smokes.

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

    lol, there is at least 6-7 similar problem like this at UVa. That's why it is the giveaway problem of the contest :)

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

    LOL, the fan in your profile image moves while looking on the screen and not directly looking to it, and it stops when just directly look at it :)

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

Happy new year~ However, who can tell me why I WA at test #22? 5584508 I can run a correct answer on my computer. TAT

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

I have submitted the problem C in java7 5577222 it got runtime error during the contest and I realized that why it got RE? so I submitted the same code in java6 in practice,it got accepted.5585065 Did it consider as accepted or not?

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

    Your Comparator do not adhere to comparator contract — it should return 0 on equal elements. Java 6 sorting algorithm is implemented in the way that for all compariosions any outcome is possible, but int Java 7 sorting algotrithm (which is TimSort) sometimes only 2 outcomes are possible and when 3rd one is returned it is assertion error

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

      Thanks thats why you are such a good programmer we learn the use only and you know the implementation of the method too.From next year I will use the library method when I know about it completely. As for my solution whether it will be considered as failed or passed because it got accepted in Java6(in practice though).

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

My this code for problem C has given me TLE in 11th case ... As the input is very big, I'm unable to know the reason... would anybody help please ???

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

    There's a while loop inside a rep(i, 0, n). The while loop may be executed as many times as the size of the bi's, which is O(n). Hence the overall complexity of this solution looks like O(n^2) which is not good enough since n could be 300000.

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

      In while loop value of 'i' is being increased... it should be just like 'i++' portion .... total complexity should be O(n). Shouldn't it ??? Or am I missing something which isn't known by me ???

      And the 10th case is big too... n=299999 ... I haven't got TLE in this case... :O

      Actually I want to know the reason ... while submitting, I never thought about this verdict ... But I've got !!! Please clear me... :(

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   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

        The variable comes from ai and is as big as 10^9, so even a single while loop may not end in time. The ai's in the 10th case is small but is large in the 11th case.

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

          But I'm astonished that, I submitted without using that while loop... and got TLE too, at the same case ... :O

          My submitted code without inner while loop is 5589598

          what is the reason behind this ??? :O

          I even didn't use STL map too ... :O

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

            your solution with int instead of long long: 5589677

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

              Thanks a lot... riadwaw

              Now my code submitted in the contest time is AC too... while loop was not the problem... The reason is only __int64 ...

              Too frustrated... didn't want such finish in this year ... ;(

              Just for not knowing that __int64 takes more time than int...

              Anyway, good thing is it's not in any onsite contest... (trying to take it positively, though failed) ...

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

            Also you could pass the arguments of cmp by reference, like 5589749.

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

I would have passed F, if I would have used scanf instead of cin.
I did not expected that time limit would be kept so strict.
May be I should start using scanf and printf for each and every problem :(
Feeling very very bad :(
It is not a good gift at all :(

http://mirror.codeforces.com/contest/379/submission/5585325

http://mirror.codeforces.com/contest/379/submission/5581511

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

    You may find this interesting: http://mirror.codeforces.com/blog/entry/5217

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

      I know this, But most of the time, I use cin here in codeforces because they give a lot of margin in time in solutions, but this time I was wrong :(

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

        I am wondering why they give 5*10^5 queries, they can simply give 10^5 queries as it is normally done, it would be possible to solve the problem without IO or constant optimization.

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

    I have the same problem, but the problem is not in input, but also non-asymptotic optimize allowed to pass tests =(

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

Does anybody have any idea how will they give the ratings? Because this contest was very different from other ones. Div1 contestants were in the same place as Div2 contestants and the contest was rated for both of them. Will there be considered a Additional points for Div2 Participants? (Hope so!)

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

    Since normal rating formula calculates the expected position based on your and everyone else's rating , there is no reason it wouldn't work fine in this match.

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

why it is wrong answer http://mirror.codeforces.com/contest/379/submission/5584330

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

Surprised to see Petr and tourist not try to solve number F!!!!Instead they were busy in hacking!!Whats the secret behind this???

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

    maybe they didn't realize there are F and G?

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

    They can't resist that when there are lots of gray and greens and blues in their room :)

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

    I've spent more than an hour trying to solve F, but couldn't.

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

      may be you were distracted by seeing lots of grays and greens and blues.. just kidding :)

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

      This problem is almoust same with RRTREE.

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

Oh the last luckiness for 2013, I submitted my F in the last second :)) I had done F before, but at the last moment I realised that I got wrong range :< I resubmitted and lost about 600 point :'( However alright <3 Happy new year everybody <3

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

So sad:(

5583857 on contest

5585359 upsolving

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

    A diff of the files would be more useful :).

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it 
      162,171c162,167
<           if col = 1 then begin
<             if dp[col][v][cn + 1] < val1 then
<               dp[col][v][cn + 1] := val1;
<           end else if col = 0 then begin
<             if dp[col][v][cn] < val1 then
<               dp[col][v][cn] := val1
<           end else begin
<             if dp[col][v][cn] < val1 + 1 then
<               dp[col][v][cn] := val1 + 1;
<           end;
---
>           if col = 1 then
>             dp[col][v][cn + 1] := val1
>           else if col = 0 then
>             dp[col][v][cn] := val1
>           else
>             dp[col][v][cn] := val1 + 1;
      → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

    actually you are peter50216 or rng_58 or not :)

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

Egor was real quick in problem D :D

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

Can anyone explain 379C - New Year Ratings Change New Year Ratings Change why 5579353 gives runtime error ] while submission id 5585888 gives accepted answer... Thanks in advance...

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

    I think that your bool cmp is wrong. The bool cmp must return the value that a < b You can have more detail in here Sort

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

      Still not getting why this is resulting in runtime error

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

        A usual line in the quicksort function is like:

        while (a[i] < a[x]) i++;

        Now, consider an array of equal elements. For the above line to work, the a[i] < a[x] part must of course return false for equal values. Otherwise, the index i just walks outside the array (which may or may not result in Runtime Error). Your previous version of the cmp function however violated this, resulting in incorrect behavior for equal values:

        bool cmp (  rating a  ,rating b )
{
	if( a.rate > b.rate )
			return 0 ;
	return 1 ;
}

        It returns true when a is equal to b, which is an error.

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

          Addition: this error is similar to writing a comparison function which always returns true or always returns false. You can try for yourself to design an efficient sorting function which accepts such a comparison function and does not generate nonsense in this case.

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

            Thanks for your response and information.

            But wont our lives be easier to implement operator for structures and easily use sorting ? 5576735

            If one day i decided to use two function to sort an array i would rather to var static variable in my class and a switch case in my operator<.

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

              C++ allows to do it either way. It's up to the programmer to decide what's more convenient.

              Such a bug can occur in a custom comparison operator operator as well as in a standalone comparison function, and will have the same consequences.

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

    I don't know exactly how sort() works but the comparison function you give must be a strict weak ordering function, so in particular cmp(x, x) should return 0.

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

    I hope that has nothing to do with same variable names for array a[333333] and rating a.

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

I had submitted this code in the contest

http://mirror.codeforces.com/contest/379/submission/5581511
and after the contest, I submittted this.

http://mirror.codeforces.com/contest/379/submission/5586307

And when I submit it after the contest, it gets accepted
May be time limit decisions are affected from the load on the server at that time.

Please tell me what reason could be for this undesired behaviour.

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

    too bad, looks like load is the cause of that 50ms difference that took that away from you :(

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

      I think this has made me learn few things
      1. use scanf/printf everywhere.
      2. try to do low level optimization when time limit of your solution is tight.

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

        or better in case of cin and cout, use ios::sync_with_stdio(false). as scanf can be slower in case of "%c" and in that case we have to use getchar() for speed.

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

          but that again has some issues, you can not interleave scanf/printf statements, As I have habit of using scanf/printf cin, cout alternatively, I will not prefer to use ios::sync_with_stdio(false);

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

pls update the ratings:)

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

F can be solved by either Heavy Light Decomposition or maintaining Diameter Pair with LCA. (HL: 1100ms, LCA: 550ms in C++) I had hard time implementing HL decomposition, I couldn't make it in time.

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

cognition solved problem A,C,B in 4:02 , 4:18 , 5:00 min !!!!!

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

    LOL. seems he was not alone XD.

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

    Yeah, seems strange. In problem B and C indentations are different. In B 2 spaces are used and in C tabs. Or he just wrote the contest on two different computers coding two problems simultaneously with each hand on each keyboard :D

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

      The indentation is also different in problem A, so I think there actually were 3 computers and he coded with his feet or any other part of his body (I don't want more details :-) )

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

        Does sharing an account break any rules? Though it's probably hard to prove.

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

    Though he was not alone, he is not in the top 10...

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

    I've conducted an investigation and banned him. There are multiple evidences that he took part unfairly :(

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


Round statistics

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

pls change the ratings

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

I wonder, will cognition get banned?

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

    Check the final standings again. cognition is no longer there. Probably removed. Also, setters congratulated Logic_IU for winning the round.

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

      He was there, just before I posted the message.

      Yes, removed. That's good.

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

Are they planning to update the rating next year or what?

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

Happy New Year to everyone!

I think if we have more problems in contest the results will be more reliable...
Wish we have more of these contest (Both Div , 7 Problems) in future...

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

i just noticed that Accepted has been changed to Happy New Year! even in contests other than today's round. i wonder if this is intentional, or some kind of bug with the site?

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

    They probably replaced the string globally (the value of Accepted string) and hence the effect. :)

    I doubt they intended it for all but maybe there's no easy way to do it for just one round.

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

    Yes, the same message is in Russian interface. And how it could be a bug? :)

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

cant wait for the year end rating anymore :(

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

well by the server time it's the new year right now(happy new year) but the rates aren't updated yet.

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

please update the rating, I want to see the rating before sleep,TAT

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

    UPD3: Congratulations to the winners of the last round in this year. Rating will be changed in a few hours.

    You just shouldn't go sleep for a few ours.

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

hope ratings will be updated this year :D

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

please update the ratings quickly, wishing only a "Happy New Year" will not work

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

where are the ratings?! :(((((

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

it was really nice contest!

but is it possible that rating gonna be updated this year? or we'll have to wait for the next year? xD

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

being specialist, how did aangairbender manage to solve all the problems especially Problem G of Good Bye 2013 (which remained unsolved in the contest) in virtual participation? who is he?? who helped him (if someone helped him)

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

Just finished coding problem G — it got accepted right after it passed the examples, but one hour spent coding it was so non-exciting to say the least.

How about a non-proliferation treaty on cactus problems? :) They rarely are conceptually different than corresponding problems on trees, but they are so much more painful to implement.

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

    Actually, I had twice as much code as if it were problem on tree. And the extra code is almost the same, just new parameter when handling the cycle.

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

      Well, you also have to find the cycles in the first place, correctly handle cases when several cycles share a vertex, etc. That's exactly my point — nothing conceptually different, but harder to implement.

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

    Best formula to create trash something "non-exciting to say the least" from the great problem.

    1. If you have a nice problem on line, but it isn't hard enough, replace this problem on the tree.
    2. If it is still not hard enough, replace this problem on vertex cactus (i. e. no one vertex lies on more than one cycle).
    3. If you are still not satisfied with the result, replace this problem on edge cactus (i. e. cactus in common sense).
    4. ....
    5. PROFIT!
    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +42 Vote: I do not like it

      Really good formula, explains everything!

      In this case the problem on the line would probably be worse than on the tree, though :)

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

      I would say, that you can add one more step: instead of "problem on tree" use "problem on tree that contains the only cycle".

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

    If possible:

    Could you share your approach to problem G? At least an overview to be able to read your solution. Thanks.

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

OMG!!! i finished watching two movies after the contest, and rating is not yet updated. i dont have patience anymore. going to bed hopping that i will see updated rating in the morning.

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

Ratings are updated. Check it out :)

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

Finally after ~5hours waiting, Rating has been updated! Now I can sleep :) Happy New Year!

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

Great match! And I have got the highest rating in this round. It will be better if Welcome 2014 Round which has the same rule as Good Bye 2013 were added.

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

thanks for this awesome round! :D happy new year everyone...:D

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


Thanks for the round and interesting problems!
Congratulations for everyone, who's color was upgraded :)

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

    actually, red to yellow is a downgrade of rating, not upgrade.
    but yeah, good idea about the photo! :D

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

      I think that's purple to yellow. To be more accurate, pink to golden perhaps? But we get the idea. It's cute.

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

+203 points, it was impossible :D Thank you Codeforces for the good year!

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

Happy New Year's Eve!

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

Screencast

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

    Which soft do you use to grab screen? Does it work without fails and crashes?

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

      CamStudio. Never crashed so far

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

Good bye 2013, good bye Div1!

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

    Same with me ;) . But anyways Happy New Year in advance !

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

Next contest will be Welcome 2014?

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

for problem A, tests 16-21 are all same. why?

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

This was such a nice contest! I crashed D because I used some variables as int instead of long long.Still,I managed to get ABC pretty fast and as a surprise, the rating increased over my epectations.So, thank you for the contest, and also thank you for the site, it really made my day.Happy new year to everyone!

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

Hello, 2014!! (in Japan)

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

So easy!

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

Great round to say good bye to 2013, I am equally hopeful for great contests this year!

→ Reply