izban's blog

Codeforces Round #239
By izban, 10 years ago, translation, In English

Hello everyone!

This Sunday, on March 30 at 11:00 MSK (March 30 at 07:00 UTC), Codeforces Round #239 for both divisions participants will take place. Note the unusual time of the round.

The problems have been prepared by me. I want to thank Codeforces team: tasks coordinator Gerald Agapov (Gerald) for invaluable contribution to the preparation of tasks and Maria Belova (Delinur), who has translated the problems. Also thank to Niyaz Nigmatullin (niyaznigmatul) for testing.

I wish you all good luck and have a good weekend!

UPD: You can see score distribution at the problems page.

UPD2: You can find editorial here.

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

Comments Comments (84)
| Write comment?
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Why is the time at 11:00 AM MSK rather than the usual 7:30 PM? Now the Americans won't be able to compete in the contest unless we stay up until 2AM or later in some parts

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

    I think it's because TopCoder SRM 614

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

      TopCoder SRM 614 will be held tonight, not Sunday.

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

    For some people the time is inconvenient, for others it is convenient.

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

    We have the same problem here, in Mongolia 19:30MSK is 23:30

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

    I would say I'm in America, but I'm not American. Almost Americans won't care about this kind of competition, as well as Obama. In anyway, I will stay waiting and participate for this codeforces round.

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

    In Vladivostok,usual time is inconvenient like far-east countries,I think.

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

    I woke up at 2:30 am and did pretty well; it's not impossible :)

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

Если комментарий наберёт ровно 42 к концу контеста, опубликую крутую статью :)

====================================

If this comment will get exactly 42 to the end of the contest, I'll publish awesome blog entry :)

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

    Is it ok to get 42 by absolute value? ;-)

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

      Yes, sure ;)

      If conscience allows it :)

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

    -42 устроит? :)

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

      Ты не понимаешь комментарий на английском выше? Какая жалость.

      ====================================

      You don't understand English comment right above? Such a pity.

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

    So close...

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

    Just as promised.

    Link

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

I think it coincides with March Lunchtime of Codechef :)

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

This time 's good for Asian. In Viet Nam it 's 2:00 PM, so I can go some where at Sunday night :)

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

I prefer weekend rounds. But it is probably due to NEERC this time.

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

3:00 pm. It'll be so perfect time for Chinese participants.

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

Please clarify the start time of the round. The link to the start time indicates the round will start at 10 am Bulgarian time while the counter says it will start at 9. Please note tonight whole europe will switch to summer time while AFAIK Russia no longer switches the clock. Could you please clarify the time in GMT to avoid confusion?

EDIT: please note that after my comment the authors did at the start time in UTC.

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

    Actually both times point to 10am Bulgarian time after the switch which makes sense. Still please post the time in GMT for people who do not know that in Moscow no switch to summer time will happen.

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

Good Luck for Everyone

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

since only 2 minutes left for round to start, can u please post the score distribution?

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

Hello. Please understand me, I am new to the site and I don't know where to post and I'm not a genius when it comes to English. What is the leg of length?

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

    It means side of the triangle with given length (note that we generally exclude the hypotenuse). Only consider base and height.

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

    Leg = one of the 2 shorter sides.

    Leg of length a = the length of that leg is a.

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

Sad day for hackers.

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

I figured the tricky case for A but somehow couldn't hack for the entire contest :(

I have tried using Chrome and IE in Windows, Chrome and Firefox in Linux. All I saw is a spinning black circle and unresponsive "Hack" button.

What is the flash player version I should have? Or is anyone having the same problem?

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

Wow fast system test.

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

    wonder if this will happen again!

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

      Well, ratings don't need to be updated really fast, unlike the systest. It's the place in the ranklist that's keeping us on edge; when we know it, we can estimate the rating change, but the exact value doesn't matter so much.

      I guess people are used to superfast rating changes from TC. That's one of TC's biggest pluses (although it still doesn't balance out the Bad Idea Arena).

      Of course, taking a week just to update ratings is not OK, like some sites do.

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

        yes i guess ur right. sorry if i offended anyone.
        anyway, today ratings were updated much faster. :)

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

So close! 46th...

I know I can't be moved up the ranklist for no reason. But can I be moved down? Just 1 place, plz :D

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

hussh.. Problem B div1 was easier than problem A.. :(

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

Very nice problems ! Congrats to the author ! I loved problems C and D ( and finally got solved D ).

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

Today was a good day for hacks (Div 1).

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

I mistakenly read the answer instead of output, Sorry for inconvenience.

I can not understand why is my answer wrong for this test case #33. I think that my answer is right, Any helps ??
408 765

My output is:
YES
0 0
360 192
-360 675

System test checker says "wrong answer side of a triangle is parallel to OX or OY".

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

    Because it's the correct answer, not yours.

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

      Never mind. PraveenDhinwa mistook the answer for output.

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

        Yep, exactly. PraveenDhinwa posted the jury's answer for that test which is, of course, correct.

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

          Yes, I mistakenly took the jury output :(

          Actually I have considered this kind of test case while coding. I made a stupid comparison bug in Java, as this was 2nd time I was using Java.

          I made wrong comparison like the below given example:(

          Integer a = 3, b = 5; if (a == b) out.println ("matched");

          I missed the point that their references are being compared rather than values :(, Nice point to take care in future

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

After system test fewer accepted problem A than B .. Seems that many don't figure out the third edge can't be parallel to x axis..

Most programs failed on test: 20 15

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

Too many hacks on A : /. kmjp reached 63rd place without solving any problem, because he got 15 hacks on A :P. It's a bad thing where there aren't any hacks but in my opinion so big number of people with >10 hacks is also undesirable. I suppose it's a hard task to make such pretests that some solutions can be hacked but not that big number of them :P.

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

    Only problem A is tricky here, if pretests are a little bit stronger then it will be a no hack contest..

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

      not just A, even problem B had a few (~30) hacks!

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

Div2 C: Can someone tell me why 

YES
0 0
12 9
-12 16

is not a valid triangle?

Edit: got it

6184905

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

It seems the time limit of D was too tight. Many O(N^3) solutions timed out.

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

    Hi, I think it's not. All our good solutions work <= 900, even Java solutions, even with n^3 memory. I think 3 times margin is enough. Of course there are some solutions with huge constant factor that shouldn't pass.

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

      I guess the reason you making the TL so tight is to kill O(N^3 logN) solutions, but it doesn't work well: here

      Maybe it'd be better to let O(N^3 logN) pass (and if you think it is too easy, we can use it as 1500p).

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

      In POI there's a rule that constraints should be as small as they can not to let worse solution pass and there also one that making a distinction between solutions differing by a log factor is probably pointless. I guess noboby will be hurt if TL would be increased/constraints would be decreased, so their solutions can pass, because since they are in O(n^3), they deserve to. I'm a follower of an idea that every two solutions in the same complexity are equivalent :P.

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

Look at this page

The last rated participation in this contest siIlycross

sillycross and tourist both won IOI gold medals...

I wondered what siIlycross was doing...

Failed on all the problems, even tried to hack tourist for many times on problem A...

。

。

。

But finally, I found that siIlycross and sillycross were different people > _ <

It's hard to distinguish “I”(upper i) and "l"(lower L) sometimes on Codeforces...

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

    wonder how siIlycross managed to stay Master despite finishing last! :D

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

      It seems that there is some cap (different for different users), and your raiting can't decrease by more than ~100 points — does not matter how bad your performance is.

      For example, look at TMandzu or Zlobober.

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

        hmm, makes sense.
        i guess the maximum increase/decrease of rating depends on number of contests user has participated before current round. the higher this number, the smaller the "cap" by which rating can change.

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

Please help with my Div1 A submission 6179184.On test 34,on my computer,my solution can give the correct output:

YES
0 0
75 180
432 -180

but on CF it gives NO.

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

    I added 0. + to all sqrt's.

    6188507

    UPD Try to run your original code in "launch" using visual c++ 2010.

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

      Thanks.I used TDM-GCC 4.7.1 on my computer,without -O2,I think that's the reason.

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

    Precision error.

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

    You should never work with floating point numbers when you can work with integers.

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

how to solve problem C in div1

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

    I decompose a binomial coefficient for i > l into

    Take an array A[] whose j-th element is the k - j-th term of this sum (if i = l, then A[k] = 1 and A[j < k] = 0). When you increment i, A transforms into the array of its own suffix sums, because

    where the first term is A[j] of the original A and the second is A[j + 1] after the transformation, which is the recurrence describing suffix sums.

    This transformation is also additive — performing it on the sum of queries gives the same result as performing it on each of those queries separately and then summing up the results. That means you can use a sweepline with adding new queries (A[k] +  + ) and removing them (you need to subtract bin. coefficients from the corresponding terms of A).

    UPD: The exact formulas were wrong, also it wasn't prefix, but suffix sums. The confusion came about because I changed the indexing from the one used in my solution (6186385). Nevertheless, the original decomposition is unchanged.

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

      This is a beautiful solution!

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

      Good solution. But i still dont get how to save queries in each element and find the current element?

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

        Find the current element: sum up the terms of array A — it's the same as computing the sum above.

        Adding queries is trivial — just increment A[k] for the k of that query. When deleting queries, you'd need to subtract from A the values that would be there if you applied the same algorithm on only that one query — those are the bin. coefficients in the sum.

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

Round Stats & Rating change

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

it's very Thriller contest 4 me.............

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

It was a nice contest. :) BTW can someone describe how to solve div-1 C? Edit : Sorry, I missed the Xellos comment.

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

I got the email announcing this contest during (or after) the contest!

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

    i still havent got any email. hopefully i'll get it before the start of next contest (which is now less than 48 hours)! :D

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

Problem Div1 — A, Triangle.

For input 5 5

My program gives the following output.

YES
2496 2497
2500 2500
2497 2496

I got Wrong answer. But two lengths of these three points are 5 and 5. Could anyone help me to find the place where I am doing mistake?

→ Reply