fcspartakm's blog

Codeforces Round #322 (Div. 2)
By fcspartakm, history, 9 years ago, translation, In English

Hello, Codeforces!

I'd like to invite you to Codeforces Round #322 (Div. 2). It'll be held on Monday, September 28 at 12:00 MSK and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time!

This round is held on the tasks of the school stage All-Russian Olympiad of Informatics 2015/2016 year in city Saratov. They were prepared by me and recently returned from army Edvard Davtyan (Edvard).

Great thanks to Maxim Akhmedov (Zlobober) for helping me preparing the contest, to Maria Belova (Delinur) for translating the statements into English, to Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform and ideas of some problems and to Vladimir Petrov (vovuh) for writing solutions.

It will be a little unusual round — you will be given six problems and two hours to solve them. The scoring distribution will be announced later. Good luck everyone!

UPD The scoring distribution today will be 500-1000-1500-2000-3000-3000.

UPD2 Editorial

UPD3 Congratulations to the winners!

  1. Moe
  2. for_the_pride
  3. SakurakoujiRuna
  4. VNOI
  5. z123z123d
  • Vote: I like it
  • +163
  • Vote: I do not like it

Comments Comments (83)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it -19 Vote: I do not like it

I think it'll be exciting to have one division combined contest per month.Is it possible?

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

    Sure, you just have to provide problems for it.

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

That doesn't seem correct... what a gr8 time

Also, the actual time seems to be just 2 hours before SRM 669...

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

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

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

Can you move it to Sunday afternoon please ? It is hard not just for me,but for many users to adapt to this unusual contest time...

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

4 AM in my part of the US o.O. At least I can participate.

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

It's in my school time :( !

OK i will take it virtual!

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

Why not just move the contest to Sunday at the usual time? This suspicious time seems like a move to try to "steal" contestants from Topcoder.

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

    The competition is held parallel to the school competition, so the time is unusual.

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

      What about moving your contest 15 minutes earlier? It's not a big change, but enough for a rest between CF round and SRM :D

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

What a perfect time for coders in East Asia! ( 5PM ~ 7PM )

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

my school finish when contest is finished... :(

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

    but my school finish when contest s finished.... :(

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

six problems and two hours ? Note that round starts in the unusual time ?

OMG very unusual contest :)

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

QWQ 17:00 is good time ,but I have a class on Monday

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

Can you add one problem and make it rated for both Div 1 & 2 :)

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

So I'm gonna skip school for this contest. Yay!

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

We look forward to the classic problem of the Army. Good luck to all!

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

6 problems in 2hrs. Imagining how easy/hard the problems will be. I have a hunch most Div2 will solve the C problem. The decider for remarkable rating changes might just be the D.

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

    You can't predict it at all.. everything is possible in such competitive activities my dear :)

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

    You can downvote all you want. You're basically wasting your time. :D

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

    Nothing has since changed in my life since the downvotes...well aside that am a few dollars richer. So keep up the downvotes and waste your precious time. :D :D :D

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

      I don't understand how that could waste our time!? it literally takes one second to downvote a comment. :/

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

        I actually don't expect you to understand how it would waste your time.

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

          Just like you vote for political parties to form your government(if there's democracy in your country) to show whether you like them or not, you upvote/downvote without caring about the time you waste.

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

I wish the scoring will be IOI styled.

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

    I wish that too.

    I also wonder how's it 6 tasks for 2 hours, and Div. 2 contest. I thought the school stage of the Russian Olympiad would contain less but very hard problems. Let's hope for the problems to be useful for practicing by Olympiad participants! :D

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

Please test the system before starting time because SRM will begin after this contest directly

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

Is hacking allowed in this round? Since it is an unusual and parallel round, the confusion arises!

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

very unusual contest ,i hope it has usual but interesting problems

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

Nooooooooo!! It had to happen just when my rating starts to rise a bit , Guess I've gotta wait for the next contest . Anyway I wish "ALL THE BEST" for those of you who participate .

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

    Each contest you miss is your loss. Forget ratings. Ratings will rise when you become good and you can't become good by avoiding intimidating situations. I know this because I used to avoid contests too :)

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

      Dude I cant miss my lab's either now , can I.....!! And what made you think that I was Avoiding It , when I was feeling bad that I wouldn't be participating in it....??I_love_Captain_America.

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

why this time??

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

Please CF be careful, any delays on this round will case it's intersection with TC round

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

12.00 Slightly unconvenient time for Ukraine.

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

Should we wait a long time for system testing and rating changes? I mean, maybe real competition won't finish at time we finish?

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

I really don't like the idea, that codeforces round finishes in the same moment when topcoder srm starts!

Does anyone know the way to influence topcoder administration?

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

Why set a round in the unusual time? or Which case will lead a round in unusual time?

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

    because it's something like mirror of school Olympiad, as far as I unserstood

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

100 bonus points to whoever wrote the ugliest solution to problem D?

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

Problem D was just horrible! (and to be serious it was a very good one :-) What is an elegant solution to this?

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

    +1

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

    It has too many conditions to handle. Curious to see if there's a recursive solution to it. I wrote a big messy solution , will submit it after system tests.

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

    I doubt if there exists any elegant solution rather than dealing with each case possibly . However, it will be very nice if some red guy explains how they generally deal with these kinds of problems (don't they get irritated).

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

      of course there is only two cases ! and these two cases are the ones in samples also it's easy to proof that only these cases might be correct ! check my solution : https://ideone.com/HomOtB

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

    I used the following observation that there will always be atleast one rectange out of a, b & c whose one side will be equal to the side of the new square. It helped me a lot in concise my code.

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

      Did this observation reduce your code length, or simply increase the number of conditions? The brute force way is a huge code, but at least its a complete copy paste work.

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

    I wrote solution, using straight forward idea:

    1) try all 6 possible permutaions (3! = 6, 6 times call first function)

    2) try all 8 possible swap's x and y (2 ** 3 = 8, 8 times call second function

    Now you need to check only 2 possible answers.

    Solution: 13270215

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

      Can you explain why we need to take every permutation of the initial order? A counter-example would be perfect.

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

        Try switching around the letters in the second example test and you will get different cases but if you take all permutations (or sort them like I did) it's only one case.

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

Can anyone tell me why my code gives me (and everywhere I checked ) right answer but gives wrong on system test? my solution: 13269100

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

    I'm not sure is it the case, but

    (int)floor((double)skill[i].rat/10.0)

    extremely inaccurate and is equal to

    skill[i].rat / 10

    (if skill[i].rat is an integer variable) which is 100% accurate.

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

Unable to submit in practice mode. Please check.

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

    The problems will be available after our onsite event completely ends. It seems it will be in 1 hour.

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

Good round: good problems, fast system test, fast editorial. Problem F was very nice. Did anyone solved it in a different way to the editorial ?

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

I am not able to understand the solution presented in the editorial for the problem F. Can anybody explain me solution for problem F in a bit detail ?

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

new record :D
11 on div2 and new max

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

i wonder when i can re-submit some problem in this contest?

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

Problems were very interesting. so good... thanks for making this contest!!!

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

During contest I submitted a code , it passed pretest but got wa in system test .... now same code I submitted later and got accepted ..... what seems to be the problem here ...... :/ ....

code which got wa:

http://mirror.codeforces.com/contest/581/submission/13270251

same code which got ac later:

http://mirror.codeforces.com/contest/581/submission/13276903

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

    Well. The problem is in this for:

    for(int i = 0; (i < n) || (k > 0); i++)

    When k is big, i becomes much more then n, so your progmam crashes and don't write anything (and get wa because of unexpected end of file). For example in test like: n = 10^5, k = 10^7, a[i] = 100.

    I have no idea why it's passing tests now, but this is it.

    P.S. Sorry for english.

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

      Maybe it's features of codeforces, so after contest there is no problem with array index out of bounds.

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

        If you increase the size of the array, the program works correctly.

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

          hey thanks for taking your time and giving me replies :) ..... yes, it was a mistake.... and it's weird that it got accepted afterwards .....

          → Reply