Nerevar's blog

Codeforces Round #207
By Nerevar, 11 years ago, translation, In English

Hi all.

Today there is a school regional team competition in programming in Saratov. We've decided to make a round using tasks from this competition. The problems were prepared by Gerald (Gerald Agapov), Fefer_Ivan (Ivan Fefer), HolkinPV (Pavel Kholkin), Igor_Kudryashov (Igor Kudryashov), IlyaLos (Ilya Los) and Nerevar (Dmitry Matov). The problems' statements were translated into english by Mary Belova (Delinur).

The round starts today, on 15th of October, at 16:00 MSK. Parcipants from both divisions are welcome to take part in it.

The scoring is standard: 500-1000-1500-2000-2500.

Congratulations to the winners!

Division I:

  1. tourist
  2. mmaxio
  3. Dmitry_Egorov
  4. iwiwi
  5. bmerry

Division II:

  1. Apsara
  2. ZJUDBLab
  3. noxe
  4. intsashka
  5. Kanari

UPD: The tutorial is published.

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

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

today is "Eid al-Adha"

Happy feast to all muslims :D

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

    Happy feast :) عيد سعيد عليك ان شاء الله :)

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

    Хорошо-хорошо, только не взрывай.

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

    A special day for a special round. Happy feast to you too :)

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

    Kurban bayram mubarek olsun!

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

    Happy "Eid Al- Adha" to you. :)

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

    Happy Eid al-Adha!

    Just want to remember that you CAN NOT fast in the next 3 days (4 if you count the Eid al-Adha), for you who fast routinely.

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

    Happy feast to all of you :D

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

    happy feast to you too :D

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

    Really funny...
    This is now 30 minutes after contest but still : "The scoring will be published later."...

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

    4 hours for system testing...
    30 second for ratings!!
    thanks!

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

      You should respect this rule:

      You may edit your comment only for fixing grammar mistakes or small changes. Do not change the main idea of your comment.

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

        Sometimes you made a mistake and after making the mistake you understand it... What should you do that times?

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

Just curious, why the scoring is published just before starting?

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

    maybe It is different to "Scoring will be dynamic. Problems are sorted by increasing order of difficulty."

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

    4 mins to go, yet no scoring!

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

what means 'school regional team competition'?

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

    ACM regional competition ???

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

    In Russia, we have team programming contests for schoolchildren: one All-Russia contest and several regional contests. Our region includes southern part of Russia.

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

it's very early!!!

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

this is the one of the earlist contests in CF(at 8:00pm in China) the timetable shows that students have to finish this contest at school, dont they i dont know about contests in Russia, perhaps it's an important one. do they feel excited? all in all, wish them good luck

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

    If each round were arranged like the timetable of this round, it would be perfect for us Chinese participants.

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

      you know it's an international website, so jet lag is a serious problem:) that's okey, for we can cherish each chance

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

How i can know the problems for the last school regional team competition ?

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

I hope everyone fails :D

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

Finally, a contest that's not too late.

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

this round was previously arranged ahead of schedule maybe because of the TC.

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

" The scoring will be published later " . 4 minutes before the contest , yet not published . Well later does include after the contest :P

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

    Score distribution is standard. The author of the post are involved into our Olympiad. So, he wasn't in time with announcing.

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

No hacks available?

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

The queue is really long!

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

I think some time should be added because of all this "In queue"..

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

    And the site was down too for few minutes... :(

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

How solve problem D?

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

It's very very hard to understand today's problem description!!!

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

    I guess, I spent almost one hour trying to understand problems, this it's my second contest where I could say it have very poor description.

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

My Decision on opening a new problem depends on current problem result i can't start in another problem until i know the result of current problem (pretests) and Queue is toooooooooo Long :( :( and take long time to know if it pass pretests or not

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

    Definitely it effects on a coder's coding... He has to keep an eye on his recent submission to know if it is passed or not... :/

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

Forget about last round's C (div1), this round's C is much more deadly! Well, at least there are abundant hacks :D

A funny thing happened to me now: I sent a hack on a solution 1 minute before the end of the contest, and waited for the queue to settle (around 1-2 minutes after the end). But I found out it was ignored, because there was a successful hack around a minute before mine, but that hack was still in the queue when I sent mine :D

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

    Well, C div1 is not very much hard , but you just need to be very careful to handle all cases

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

      But being careful is hard! (for me, at least...)

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

      That's exactly the point. With problems that rely on you finding a general algorithm, passing pretests usually equals passing the systemtest (as with Adiv1 this time). But it's easy to miss a special case (I hacked one guy on "5 1 1 1 1 1", for example).

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

        So THAT was the case I missed! I was dying here trying to figure it out... :)

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

The scoring will be published later. later = never ever ? looooooooooooooooong Queue ! :|

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

today's div-2 contest was slightly harder than usual contests, but the problems were very interesting to solve! next time, try to increase the possibility of hacks! :)

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

I think the system testing can't be completed before TC start ...

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

    Even before TC's end

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

      That's why they began the contest so early.

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

    dunno why, but i think this is the record for the slowest testing ever on Codeforces!

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

Hi I wanna ask about my A submission [LINK] Why my submission didn't passed time limit ? I saw that my idea is same with other submission that got accepted. Is that using (*it) many times make my submission slower or there's any other factor ? thanks

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

    what is the purpose of the hold; statement at the end?

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

      It just same as getchar(); twice. I'm sure it's not the problem because I got TLE on preetest 11

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

    Probably because of the lower_bound(s.begin(), s.end(), l) call. From the docs:

    On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

    If you want log complexity, you have to call s.lower_bound(l) instead.

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

    I think that this line:

    while ((*it) <= r)

    should be

    while (it!=s.end() && (*it) <= r)

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

    I think it's because you are erasing while you increment the iterator. IMO you should erase the whole range after you assigned the winner.

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

    ffao gave the correct answer.

    I got TLE for using lower_bound(s.begin(),s.end(),l) later i replaced it with s.lower_bound(l), i got accepted! so its really something to keep in mind.

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

25% system test = 30 min
100% system test = ???

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

    Supposing linear behavior you can simply calculate it by a proportion xD

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

    430 min?

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

    50% system test = 115 minutes!

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

      25% system test = 30 min 50% system test = 115 minutes what's about 100% system test ??? :P

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

        400 mins

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

          Whats that? quadratic interpolation?

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

            I hope when I wake up tomorrow to find the system test has finished

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

LOL at least 140 testcases for div1 C well, at most 140 seconds (=more than 2min) are spent on each user.

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

Why today's judgement such slowly?

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

    Because there are many test case to run (20-150 cases) for each submission, and each case is about 1-3s time limit.. and there are many submission too.

    EDIT: here is a picture

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

is anybody else facing a problem opening the TopCoder arena? the SRM registration closes in 2 minutes, but i am unable to launch the arena! :(

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

    Yes, me too

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

      just when registration closed, the arena opened! how unlucky we are! :(

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

    Did you update your Java version? I faced that problem some days ago.

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

      i redownloaded the .jnlp file from the website just before trying to launch the arena, but still it wasn't opening!

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

        I did the same but it was a problem with a jar file (logging.jar) So, I updated from Java 6 to Java 7 and it worked.

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

        always delete your cache by typing javaws -viewer in terminal and then restart the arena .. Even then if it doesn't work , restart your OS and then open the arena .. It has happened a lot of times with me .

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

Ahh... Why the system testing is so slow? I really don't like when I have to wait few minutes for my solution being checked on pretests, especially when I have a stupid bug and have to resubmit it many times. Today I got RE because I've written ios_base::sync_with_stdio(0); and later used scanf. I submitted it 6 times and had to wait few minutes for each of them. Is it really necessary to put so many big pretests?

And now 40 minutes already passed and system testing is in 20% of its progress...

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

Hi, i wanna ask about my submission 4791878 , why i got WA on pretest 1 ? Thank you very much

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

May somebody explain C, D, E (div. 2), please? C requires a segment tree, yep?

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

    There's no need to implement a segment tree for C in Div 2, a disjoint set or simply a linked list would suffice.

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

      Or a regular STL set. 4789501

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

        Oh God, really. Thanks. And may you give some little tips for D & E, please? Don't know how to solve them :\

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

          D: let gcd(length(x), length(y)) = d; i-th character in x will be paired -times with every character in string y on position . Count how many chars equal to c in x and in y are , and then the answer is N·length(x) minus the number of all pairs of chars equal to c at every remainder modulo d (those are zeroes in the Hamming sum).

          E is ugly, I don't want to write anything about it...

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

            There is non-ugly solution for d2 E — d1 C

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

              Could you explain your Div1 C solution? I think it's better than handling different cases.

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

                Basically there is not that many ways to ditribute that many people between n compatments of 4, 3 and 0 in each. For each such variant we can use simple greedy

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

          For E(Cdiv1), let iterate number of final happy compartments from 1 to n and check if it's possible to be our answer (and how many swap). Final number of compartments x is possible if and only if

          1. 3* x <= number of students <= 4* x
          2. x <= number of compartments that already has some student sit on it (imagine that answer has more number of happy compartments, this mean we do some waste)

          Now, we will find minimum number of swap if we want to got x happy compartments in totals, we do as follows

          • Let cnt[i] be number of compartments with i students on it
          • Let S be number of students
          • Let C be number of compartments with students on it
          • Let final[i] be number of compartments with i students on it at the end
          • final[4] = S- 3* x
          • final[3] = x- final[4]
          • Let ans = 0
          • Let D = C- x be number of compartments we want to get rid of
          1. if there are extra compartments with 4 students we let that student out of seat; ans+=max(0, cnt[4]- final[4])
          2. then we choose D compartments with least total student and let all student out of seat; ans+=min( cnt[1], D)+ 2*min(0, D- cnt[1])

          our answer will be minimum ans over all suitable x

          You can look at my submission 4801911

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

            Could you explain why final[4] = S-3*x for a valid x?

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

              We have x compartments, in these x there are final[4] compartments with 4 students. 3*x + final[4] = S (total number of students should be same), so final[4] = S — 3*x.

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

          For E, first you should combine 1s and 2s to 3s, then some 1s OR 2s left. If 1s left , brute force how many 1s will not move while other 1s must move. That's easy to think. If 2s left , just do the same thing as 1s.

          Hope my code easy to read and understand.4801885

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

        A nice intuition the STL set indeed. How can we deduce if the set is enough in this problem or even in general, what is the border between set or list being enough compared to segment tree. I know the question is not so specific but I think also some advises (not necessarily related to this specific problem) from more experienced coders will be well appreciated from biggest part of the audience.

        Thank you. PS: Congratulations for becoming a red coder for first time! :)

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

          It's hard to say when sets could be "enough", all these data structures have their own usage. STL sets can do element existance queries in time, and supports insertion and deletion with the same complexity, also it can find the element before or after another element. Linked lists can do insertion, deletion, and moving to next element in O(1) time, but takes O(n) to find an element. And as for segment trees, it has a totally different usage. For more information maybe you can check out wikipedia.

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

Does anybody have some idea of div1 B and C?

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

Slowest system testing I've ever seen.......

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

    Most probably, fastest update of rating ... :D

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

what a system test!!! why Codeforces don't make system test faster permanently?

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

Eid mubarak to all muslims ..

system testing too slow !!!

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

I think system testing went to participate in TC srm and will come back.

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

Topcoder's contest and system testing will complete before CF's today :P

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

    I think TC and this system testing finished together :D :D

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

    the TopCoder SRM started at 2300 IST and has finished system testing and rating updates, but the Codeforces round that finished at 2000 IST has only finished 90% system testing, and has probably broken the record for slowest system testing ever! i know this doesn't always happen, but Codeforces should really improve the speed of judging on both pretests and system tests!

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

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

It would be so better if codeforces people could use extra servers for load distribution .. Cummon professionals , help mike with the funds .. after all we all benefit from the platform ..

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

TC srm finished and codeforces still has not finished system testing

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

I haven't seen system testing like that...! thanks!

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

First, happy feast to all muslims !

Second, I'd like all this problems. But can you tell me the reason why the result come late ??

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

Time limit exceeded on test 61 [final tests] → 4793492.

whats problem with BFS?

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

    I have seen some other bfs solutions to be failed. I don't know the exact reason. My dfs solution passed but I have seen some other bfs solutions to be failed.The reason could be (not sure) same nodes are being queued multiple times.if a node is pushed into the que and marked as visited then it could be a little bit faster. You can try that.But TLE on CF server with bfs where other solution passes with dfs!!! well i am surprised ! Thank God I dont know bfs :p

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

    It could be because you use memset everytime you expand a node.

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

I just leave it here : Yeputons comment about codeforces down

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

Actually, right now I don't know why judging is so slow. The possible reasons are:

  • we are hosting school regional and ACM-ICPC subregional contests, that's why we use our most of our machines for teams but not for Codeforces testing (right now we use 8 instead of 20 of them),
  • the problems are really slow to testing,
  • something goes wrong and I'll investigate it.

Sorry for really slow testing.

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

    Current submits are all 'in queue', any mistake?

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

    hey, if its not too much to ask, can u implement a way (if it doesn't already exist) by which we can sort the users in the standings by score in a particular problem, or by score on hacks? thanks in advance!

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

Happy feast! Could someone explain me solution of problem C in Div2 or A in Div1?

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

    You can do operations using Map, Linked list, disjoint set or Segment tree .. All will suffice ..

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

      Could you explain one of them?

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

        At first put all knights to the TreeSet, then sequentially for each fight take corresponding subset (for TreeSet it takes R*logN, where R is number of items in subset) and remove all elements of subset except winner. The total complexity will be N*logN

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

        See maintain a map/set of all those who aren't defeated .. initially it will consist of all the knights as none is killed . now as you get the queries .. find the lower bound for l and delete elements from map/set except the one index which won .. and go on updating the loose array for those who have lost .. searching requires logn for set/map since map/set are a balanced rb tree and you will go to n-1 elements exactly once .. hence your complexity O(nlogn)== 5*10^5 which is within limits for 1 sec .. Apart from that you could have used Disjoint set DS as it is also ammotized O(Nlogn) or in the same way a segment tree ..

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

System testing was too slow...but ratings has been updated very fast instead!

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

Hi everyone. I don't understand why my code for Div2-C gets TLE. Here is my solution --> 4796407 I kept all the elements in a vector and when time came, erased it. I think it has complexity MlogN + M + N . Please tell me where am I going wrong so that I can be careful not to make such mistakes in the future.

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

    Erasing an element from a vector takes O(vectorsize) time, imagine that it's because you need to re-number all elements after it. So you complexity is O(N2).

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

    Hi! Your solution would have worked perfect with another container like set. Unfortunately the erase function from vector is ( almost ) linear in the size of the vector. So your complexity is not MlogN so that's why you are getting TLE. Try with set and you will get AC!

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

      I don't usually use set. But I realize it's a pretty handy structure to use at times. I'll try what you said and get back to you. Thanks mate.

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

      Yay! Coded with set and got AC. Runtime less than 1 sec. :)

      Thanks a lot!

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

    I have a confusion with you bsearch function. specially with this line hi = v.size()-1; Your M times bsearch will cost MlogN if and only if hi = v.size()-1 is an O(1) operation. But I am not sure that it is O(1). Also in the case of erasing vector elements. Erase operation is O(n) and M times O(n) is bad.

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

    Thanks. I must have counted the complexity wrong. I'll try fixing the solution.

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

del

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

I love this problemset, especially for problem 1D ;)

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

    Could you explain how to solve D? Thanks

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

      I got TLE #82, but assuming my solution was correct, the problem asks you to make a nesting with the given bags, such that the sum of the values of all top-level bags is s. The key observation is to note that any selection of top-level bags is actually possible, as long as the biggest bag is top-level. The trick is to nest each non-selected bag within the next-highest bag, which is always possible. In other words, you can reduce the problem to a subset sum problem.

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

        Why "any selection of top-level bags is actually possible, as long as the biggest bag is top-level"? Under the condition that the total number of coins is fixed, I cannot understand this property. Could you elaborate on it? Thanks.

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

          Let's sort the bags by decreasing ai. The necessary condition is: there's a set S of bags such that , and (1st bag is the largest one). We can construct the solution now. Let's just take the bags in S and put ai coins into bag . Then, we have some bags left over, and we want to put those bags so that the constraints would be satisfied.

          Let's process the remaining bags by decreasing ai. When adding ith bag into the configuration, we know that there's a bag j which contains aj ≥ ai coins and no bags (for the largest one of the remaining bags, it's the largest bag in total; for any later one, it's the bag that was added to the configuration just before it), so we remove ai coins from bag j, put them into bag i and put bag i into bag j. Notice that this doesn't change the total number of coins, and that there were enough coins in bag j for it to happen (there will be aj - ai left over directly in j after this). In this way, we can construct a solution.

          The condition is also necessary, because the largest bag (if there are more of them, choose an arbitrary one) can't be nested in any other, and the number of coins (directly or indirectly) in bags of S (those that aren't nested in any other) must be equal to s.

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

      DP and use bit set to make it faster.

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

why my C problem is MLE in test 19 ?(div 2) can some one help me?

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

    Probably, stack overflow because of the infinite recursion.

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

problem: Round #207 B. Flag Day

example : 7 3 1 2 3 4 5 6 5 2 7 Who can tell me the answer ? Why many people who is accepted can't pass it ?

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

    This is an illegal case — in the third dance, you have two dancers who already participated in dances before; 5 and 7. Problem statement indicates that in each dance, at most one dancer who have already danced can participate. This makes the problem way easier actually!

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

      Without this constraint it would be a 3-Colorability problem which in fact is NP-Complete :)

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

      Thank you very much, I see.

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

pls explain the scoring system ,i solved a question(A) in prev round at the same time as this time(in this contest) but last time i had an increase of +28 points but received a -48 this time

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

    In previous contest, you were 1284th from 2158 participants. This contest, you took the same place, but number of participants were less than previous, so you lost rating.

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

Well, nice problem, especially C

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

I made WA on problem C, on the test 141...

I coded for(int i=0;i<num;i++) but I should code for(int i=0;i<=num;i++)...

I lost my rating by 67 points by the mistake and I failed to yellow. But for this mistake, I would be still red now and had gained rating...

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

    All of us have made a silly mistake in some contest caused losing the ratings

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

Versatile problem set !! #loved it again <<>> #CF, the best.

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

0xCF round : ))

→ Reply