Igor_Kudryashov's blog

Codeforces Round #126 (Div. 2)
By Igor_Kudryashov, 12 years ago, translation, In English

Good afternoon, friends)

We introduce you Codeforces Round #126 (Div. 2). Please note, Codeforces Round #126 (Div. 2) will be only today and only today you will have unique opportunity to raise your rating in this competition (certainly, you will be able to solve problems virtually after round, but this doesn't change your rating). Also round will be unrated for participants from first division.

This round was prepared by students of Saratov State University: Nicolay Kuznetsov (NALP), Pavel Kholkin (HolkinPV), Igor Kudryashov (Igor_Kudryashov) and Gerald Agapov (Gerald). Also we thank creator of Codeforces Michael Mirzayanov (MikeMirzayanov) for amazing system, member of staff of Codeforces Mary Belova (Delinur) for great translation and Alexander Kuprin (Alex_KPR) for help in preparation of this round.

Note, today it is decided to use dynamic scoring system (Learn more about dynamic problem scoring).

Also problems will be placed in random order, it means they aren't sorted in increasing order of difficulty.

More right ideas and fine solutions to you.

UPD. Competition is over. Thanks for all who participated. We hope you enjoyed the participation, and round not passed in vain. Editorial will be posted soon. Congratulations to the winners:

  1. Andreos

  2. jma127

  3. iensen

  4. Spider-man

  5. MrPapaya

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

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

I didn't find how many problems we'll have in contest . |-(((

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

wow.. this is the 200th contest on codeforces(taking Div-1 Div-2 separtely) .. Kudos to the Codeforces family :) : )

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

I dont know why I am getting the runtime error on pretest 1 for Problem D. I was getting correct answers in my system which works with EgorK's plugin. .Somebody please see my code and tell me where I was wrong

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

Hm, no AC for A problem in Java? What was the idea?

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

    I didn't solve it at the end, but my idea was to register the number of filled seats for every diagonal in a Fenwick Tree. This would give me the number of filled seats at a distance d from the preferred position in logarithmic time for every d.

    With that value I can check if there is a free spot at minimum distance, and then just look for it with brute force.

    This would give a O(log(n) n k) algorithm, I guess it should fit in time.

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

What about constraints for problem C? I really think problems should be written more carefully.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    The names of teams team1 and team2 are non-empty strings, consisting of uppercase English letters, with length of no more than 20 characters; goals1, goals2 are integers from 0 to 9.

    What else do you need?

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

      Man, I don't even see that in the statement!

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

        There are less than 10 lines on the part "Input", are you kidding me?

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

          Hehe, my bad. Somehow I missed that part. Should not compete after a bad last night, I guess.

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

Can someone tell if the testcase 9 for problem A was 2000 2000 100000 and then 100000x 552 1028

or were there also some different chosen seats?

thanks

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

    No. The 66668th is 551 1028. You can see my submission: 1830110

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

      :) nice idea, thank you very much

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

Did O(nklog n) worked for problem A. I wrote O(n*n*n) and got TLE. I figgured out O(nklog n) but did not have time to finish during contest. Is there a better way?

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

    K*(N+M) may work in time.

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

      мы старались завалить любое такое решение :) авторское имеет время

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

        Плохо старались значит:) Думаю, что такое легче было валить ограничениями, а не тестами. Как не крути — 2*10^8 на КФ за 3 секунды работает. Мое решение зашло за полторы.

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

          ну миллион неправильных решений не угадаешь... а ТЛ как всегда ставится с запасом, ведь уж лучше пройдет так, чем не пройдет правильное, но не очень аккуратно написанное решение.

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

            come on! You're writing in russian and the people still giving u points?? Wow... red is a powerful color!!!

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

someone could tell me how giving this input for the problem C and why?

EIYLBZCLPBGXJRT BERLAND 7:9 MWVSPZD BERLAND 4:7 MWVSPZD EIYLBZCLPBGXJRT 4:8 VRGN EIYLBZCLPBGXJRT 3:6 VRGN MWVSPZD 6:0

sorry by my english

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    X > Y, that is, Berland is going to win this game;

    X must be greater than y

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

I think Problem C Div 2 is incomplete .. The problem only asks to find the min (X-Y) but does not specifies that X should be as less as possible.. For eg: In test case 1-> ans is 6:0 but what if I give 50:44 . I got a WA because of that

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

    No, You are wrong: "if it is still impossible to come up with one score, you should choose the score where value Y (the number of goals Berland misses) is minimum."

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

When will the editorial be uploaded

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

When will the editorials be posted?

→ Reply