Igor_Kudryashov's blog

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

Hi to all!)

Regular round Codeforces #237 for participants from 2 division will take place tomorrow March 19, 19:30 MSK. Traditional, participants from 1 division can take part out of the competition.

The problems were prepared by Igor Kudryashov (Igor_Kudryashov) and Gerald Agapov (Gerald). Also thanks to Michael Mirzayanov (MikeMirzayanov) for very cool system Codeforces and Mary Belova (Delinur) for translating the problems into english.

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

UPD: Score distribution will be standard 500 — 1000 — 1500 — 2000 — 2500.

UPD 2: The contest is over, thanks to all participants.

Congratulations to the winners:

  1. Pkqs09
  2. juggler
  3. zstu_bobo
  4. kevinswat
  5. Salvare004

UPD3: You can find the tutorial here

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

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

Gerald's rounds are always nice. Thank you for preparing this contest!

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

    Yes, I agree with you.
    Why always there is some unrated users in top 5??

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

A day before Nowruz!
Wish this good round completes the happiness of starting of our new year!
Happy 1393 (Solar Hijri calendar) to all Persians arround the world ;-)
Wish everyone happiness and good luck!

P.S: You can follow the exact time of year delivering (March equinox) in Iran here
Edit: Year delivering is the national word (تحویل سال) but the scientific name is March equinox

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

Is it standard distribution?

EDIT: Why people are so opposed to asking a simple question? Obviously when I asked this information was not in the main post...

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

Good luck everyone~ This must be a good contest! :)

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

I hope this will be my last Div.2 Round (1699 now) :)

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

    Before last contest you've got 1666, also nice :D And I've got 1697 :)

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

404 contest not found! ++id; :D

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

Oops. I guess I didn't register. I feel like it let me register with out being logged in so I thought I had registered but I actually hadn't. Next time. Good luck. Zoz

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

Next time you'd better get a DECENT translator to translate the problems! OR release the problems in RUSSIAN ONLY!

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

    This time I firmly disagree with you, translation quality was decent enough, Can you specifically point out which problem had poor translation or possible issues so that translation might be improved in future.

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

      I don't get it neither... Even if some problems were tricky, I haven't found statements being hard to read.

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

        The statements were extremely vague and poorly written! I would read each line over and over again to understand what the writer is trying to get at!! Also many points were unclear, some samples clarifications should've been added!

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

          They were not much clearer in Russian.

          However it is a free contest and you pay nothing to practice here, so probably it is not just to complain. "Take it or leave it", you know. :)

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

            Well this depends on how you define "free". I don't like to sound rude but this whole thing is not made up for charity you know! Codeforces is getting well known a day after the other and it can attract many sponsors and companies that would host their competitions on it, so it's not free, what you are saying might apply to something like UVA but not Codeforces! When you make a platform, users are your capital. You wanna make something, make it the best possible or don't.

            And by the way, I don't mind paying if this would result in a better platform! Actually I'd be very glad to do so. That's not the point I'm trying to make, I appreciate their work and efforts and everything but they need to consider this feedback if they really want to achieve something!

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

              first to note, other people reads the same description

              second, what it's like good a problem has good description ?

              every people has different kind of understanding, you should not blame the problem if many other peoples understand it, try reread it, if you still dont understand, ask here or send clarification (while contest)

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

              What exactly you suggest? Magically improve the skills of existing translator or hiring a new one?

              But you know the amount of work is not sufficient to hire full-time employee. At the same time it is not possible to hire the same free-lancer for short job each time. So it will be necessary to rely upon several at least.

              And it is not easy since CF team is deeply concerned of keeping the problem statements in secret.

              You wanna make something, make it the best possible or don't.

              I think it is too bold and too careless statement. If understood literally that means you and me should not participate in this round, since we did not get in top-5 :D

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

                I think I missed (or at least die trying) in my statement :D. This problem (poorly translated or vague statements) has been around for a big while now (along with other problems, like the increase in number of cheaters, servers' outages, etc) and I believe that the time is overdue to consider a solution for this! I really believe that this should be taken into consideration. I know it's a bit unfair, but I always compare Codeforces to TopCoder. TopCoder is a very big company with big resources comparing to Codeforces, but I do really believe in Codeforces and their potential to become as good as them someday, all it takes is just paying attention to their users' feedback to improve the platform.

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

Nice problems and nice contest...!!! Thanks to authors...

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

Hi Igor_Kudryashov, I can not understand the reason behind giving constraints of length of string being upto 1e6 in problem D. I think you could have checked peoples logic even with the length being 1e5 and it would have let dp solution with slightly more space pass in the contest (eg mine) !!

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

One round with problems descriptions containing so many unspecified points.

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

was it just me, or is the statement of problem B a bit too complicated to understand?
IMO, either the statement should have been worded a bit easier to understand, or the second example case should have been explained (preferably with diagram).

unless, ofcourse, this problem was intentionally designed so that everybody spends more time understanding the statement than coming up with the solution! :P

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

    It was not only you, I had a very hard time too.

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

    the statement was very clear imo...

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

Really nice problemset!
But some statements in English were a bit hard to understand for me.
Unfortunately I spent 35 minutes debugging my code for problem B and replacing cout with printf made my code pass the pretests!
I can't believe why printf is faster than cout this way! Although I used ios_base::sync_with_stdio(false); and I thought it makes cout work as fast as printf. Also printf and cout both used the same time to print in my system.
Can anyone explain this diffrence to me?

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

    i'm not an expert on which prints faster and how to optimize I/O, but u can have a look at these if it helps.

    my AC solution 6071440 using printf (in contest).
    my AC solution 6081037 using cout (just now, in practice).

    EDIT: as expected, the second solution has a much higher runtime than the first! even using ios_base::sync_with_stdio(0) (6081967) does not improve time as much as i expected.

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

    there were some relevant discussions that you may refer to,hope you'll find it useful

    http://codeforces.net/blog/entry/5217 some tests on various input ways;

    http://codeforces.net/blog/entry/6251 A discussion link

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

Why didn't they update the problem statement of 404C - Restore Graph when there was an announcement?

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

so sad failed at final system test, at problem c, just because didnt check the number of edges at vertex 1 :(

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

    And I failed because I didnt use long to check for (k-1)freq[i] <= freq[i — 1]. :(

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

      warm_hug sigh, currently i rarely got 1 shot ac :(

      hope do well next contest :D

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

It's time to change my nickname to FakeRalor

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

    I know that feeling bro :D :D, I couldn't solve A, B and my solution for C failed because of a stupid bug!

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

      I'm ready to try it once more. Just to test rating system)

      UPD this is the post for those who like computing probabilities

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

I don't really understand the complaints; I thought problems were pretty clear and well-written, though I do agree problem statement of C should have been changed following the announcement. Seems to me that people are quick to blame the language when problems are hard(er than usual).

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

Igor_Kudryashov,Gerald

Congratulations, very nice problems. :)

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

Did anyone else get WA for test 29 in Problem C? The test case is too long (and hence truncated) which is why I can't test it locally.

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

    UPD: Try this test case: "000??1?1"

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

      Isn't that a test case for Problem D? Could you provide one for Problem C too?

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

    The WA was because of integer overflow when multiplying (k-1) and the number of vertices in the previous layer (i.e. when checking the condition (n(l)<=n(l-1)*(k-1)), where n(l) represents the number of vertices in the layer l). Casting into long long before performing the multiplication resolved the error.

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

Hi,Igor_Kudryashov!First,thank you for preparing this contest! But I have a question with the judgement of 404B - Marathon I don't think that there is any trueness error in my solution ,and I think the answer has.(I used __int64 to avoid it.because the date of a and d are given with precision till 4 decimal digits after the decimal point ,we can use a * 100000000 to transform double to __int64 to avoid the precision problem).But I just cannot make it. Could you please take a look at my code? Thank you very much!!!

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

i have noticed this for the last 5-6 contests. system testing finishes very fast, but rating takes a lot of time to be updated. why is this so?

EDIT: ratings updated! :)

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

Thank You Igor_Kudryashov and Gerald for this round..

Off-topic: Sometimes after ending the contest i feel like i am an big donkey. The masters solves all problem in 1.5 hours.. And I can not solve more than one in two hours. It feels likes i am low brain animal.. This one is one of them..

Will have to learn many things still. Hope to learn somethings from the tutorial.

:)

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

    There is no good trainer or participant with rating 1600-1700+ in your university, there is an answer. Sometimes it's a question of 5-10 seconds to learn something important from those who knows more.

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

      Yeap.. Brother. I know. But unfortunately not every one have the chance....

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

Could somebody please explain on why this answer is accepted but this one is not for problem B.

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

    Because int(975910353.9999999) is not equal to 975910354. Do not forget to round before converting to int: replace int(float(...)) by int(round(float(...))

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

      Thanks! But the problem says a and d (1 ≤ a, d ≤ 100000), given with precision till 4 decimal digits after the decimal point. So it should only contains 975910353.9999 but no 975910353.9999999?

      UPD You're right. I finally understand after reading this. Thanks a lot!

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

Congrats ! It was a nice set of problems and the tutorial came very fast. I particularly liked problem C due to the fact you had to think how to implement it in a simple way. I also liked E because it was quite original from my point of view.

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

i think that this is the first time in history of CF, where user who is placed in first position has failed A and B! :D
even so, congrats to Pkqs09! :)

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

For my submission 6082618, the checker comment (for test 5) seems wrong.

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

    your 4th vertex has more than 3 edges. It should be 3 or less

    UPD : okay maybe comment need some correction

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

    i think checker comment is 0-indexed. i agree that it seems confusing, because problem asks us to output vertices in 1-indexed fashion.

    but the verdict of WA is correct, because ur vertex 4 has degree > 3, which is not allowed.

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

Wow! Some cells in Standings still show '?' and even if they are actually AC, no points are given!

Edit: Standings was fixed, and ratings were re-updated. I am relieved.

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

where is my D ？

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

fixed

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

This is so strange, I found out why my B submission wasn't working My idea was to convert all doubles to ints by multiplying by 10^4 (because the statement said that was the most precise they would be given in) just to be safe in case of errors.

I have #define SC 10000 as my scale factor This is my testing code to find the bug:

cout<<"*"<<dd<<endl;
cout<<"**"<<dd*SC<<endl;
cout<<"***"<<(int)(dd*SC)<<endl;
cout<<"****"<<d<<endl;

Where dd is the distance read in as a double And d is the distance converted into an int after being scaled up

On my computer, I get this:

*2.8819
**28819
***28819
****28819

On codeforces, I get this:

*2.8819
**28819
***28818
****28818

For some reason only on the codeforces server, it's converting 28819.0 to 28818?

My erroring submission is here: http://codeforces.net/contest/404/submission/6079213

Does anyone know why this is or how it can be fixed?

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

    This is because of round off error

    the float output of 2.8819*10000.0 is like that 28818.99999

    try adding small value like 0.00001 to dd*SC

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

      Ah ok. So it was the rounding.

      How come when I run this on the server printf("%.6lf\n",2.8819*10000); my output is 28819.000000 ?

      Thanks for your help.

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

Round stats

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

There is -1 change in the ratings of the contestants since last night rating update. Last night when i logged out mine was 1588 after the update but its 1587 now. Some of my friends also have -1 rating down. Was the rating re-evaluated due to some error in rating update ? or something else ?

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

    apparently there was some issue with system testing due to which some solutions were not tested (relevant comment).
    so i guess some of these solutions got AC and resulted in a big increase in a few users' position (and, consequently, small decrease in some others'). due to this the ratings had to be re-updated.

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

someone explain me why this code (problem C) gets runtime eror ... 6088745

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

Perfect round! I love codeforces. It gives me a lot of new skills. And you?

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

Hey i have one question,

In Question Restore Graph Tutorials say that there would be a tree then why they have mentioned edge 3 2 in first test case? I think we do not need that edge,

Thanks :)

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

    the only simplest answer is a tree. any code which doesnt print that edge 3 2 (like mine 6077747) will get AC.
    about why it was given in the first place, i guess it was to make the contestants think a bit more, rather than just look at sample input/output and get the approach straightaway!

    → Reply