fcspartakm's blog

Codeforces Round #288 (Div. 2)
By fcspartakm, 10 years ago, translation, In English

Hello, Codeforces!

I'd like to invite you to Codeforces Round #288 (Div. 2). It'll be held on Tuesday, January 27 at 19:30 MSK and as usual Div. 1 participants can join out of competition.

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 my dear teammates Arthur Svechnikov (ikar) and Ilya Los (IlyaLos) for writing solutions.

The scoring distribution will be announced later. Good luck everyone!

UPD Score system is standart 500-1000-1500-2000-2500.

UPD2 Competition completed! Thank you all!

UPD3 You can find editorial here.

UPD4 Congratulations to the winners!

  1. topcoder.2015
  2. KimJongUn_JBYongDongJI
  3. atatomir
  4. pankaj_gudlani
  5. egor_bb
  • Vote: I like it
  • +223
  • Vote: I do not like it

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

Preparing for the battle...

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

Good Luck to everyone :). I request all Div-1 Participants to participate Out of Competition. Hope I become Div-1 Coder after this Round :).

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

    加油~

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

    We were roommates today :)

    Unfortunately you got your C faild :( else you would be there :( Next time :)

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

      Congratulations to you for both 1st position in the Room as well as for jumping into Div 1 :).

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

Two consecutive Div — 2 contest. It's really frustrating for Div — 1 participants.

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

I remember that I saw Round 288 div.1 && div.2 about 5 days ago. But now there exist only div.2...Could I ask the reason why the div.1 is cancelled? Is it because the problems for div.1 are not prepared?

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

Div.1 users dont create new accounts please.

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

    I think that problem is separate rooms for div 1 users.Many of them want fun,hacking,and best place in their rooms. If that changes,contests would be more regular.

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

gl & hf )) PS: Good luck and have fun) PSS: I have 4 houres before CF. It's about 5 games in Dota 2. GG :D

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

Although it's a Div.2 only contest, but still it will be a good start for me! I'm sure I'll enjoy the contest!

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

I hope this won't be dynamic scoring in this contest :|

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

cheaters don't cheat!!!!

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

    and you assume that cheaters will do what you say ? :D

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

Update about the scoring system well before contest.. That's unusual.. but nice .. Gl & Hf

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

let the game begin :)

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

5300+ participants. That's amazing)
UPD: 5400+ :D

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

700+ unrated participants. Funny, isn't it?

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

What Does standarT in last line Mean Exactly?

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

    Try to come up with it :)

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

    It's a typo. It should be standard which means 500-1000-1500-2000-2500

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

    means that problem setter is from Russia. ;)

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

    It means the score distribution is a work of art

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

not to prepare contest is much better than have a contest with many mistakes;

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

Suspicious?

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

dreamoon_love_AA just might reach his dream of first place in a codeforces round !

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

how to solve E

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

omg im turnin greeeeeeen!!!!! ;(

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

How to solve D?

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

    I have an idea that "ABC" is actually an edge between "AB" and "BC". What we need to do is to find an Eulerian trail of the induced directed graph.

    (Yeah, I failed in the second part)

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

    Let's look on the graph in which each vertex is a pair of symbols. Then for example abc = ab -> bc. The answer is the euler path in such graph.

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

    Imagine a graph with 52 * 52 nodes.

    Each node represents a string like this "ab".

    Then each sub string means edge in this graph. Find Euler path.

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

      even more digits are also allowed .. I have not noticed this thing and start coding and later realised that this solution is of no use now ..

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

        I did not noticed digits. It would be nice if they were bold :(.

        Thank you, for pointing out my bug during contest.

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

      62 * 62 nodes...

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

Can someone tell me what's wrong with my solution here? for problem E? I used an O(n^2) method, but I still get TLE .-.

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

B is gonna have so many System Testing wrong answers :3

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

It was very fun contest :D

I wonder how can solve C...

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

    Hello mhkim4886

    C can be solved using this idea that the candles required at the ith second can be burnt at i-1 , i-2 ,,, and so on second .. but after burning these candles check once whether you have achieved required number of candles or not .

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

I don't understand why this code couldn't pass the first pretest case about problem D, I did Eulerian Cycle and I got the same output in every pretest case, but I got WA in pretest one :Ssss >< http://ideone.com/1RfNzu

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

    Use custom invocation in situations where your code does not pass test 1. Your code prints "NO" on CF servers.

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

I solved A but couldn't submit...

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

My first hack in codeforces is unsuccessful :P

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

Gray has been my favorite color.....since I started here ^_Q

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

D was a very interesting problem; can someone give the algorithm?

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

    Interpret as a graph from the first two characters to the last two characters of each substring, and find an Eulerian path.

    Find Eulerian path with something like Hierholzer's algorithm.

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

Just for fun !

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

    What's wrong with that? Take care of your own submissions, boy.

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

Thanks for realy funny contest, with string problems! :) . And thanks for weak pretests! In problem B I've found some too slow submissions in my room, so need to generate maxtest for these submissions.

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

pending system testing 10 minutes @@

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

I submitted C in the last minute and didn't even get time for checking my A. After reading the editorial I found out what a foolish thing I did with A just because I thought I had to solve 3 this time.

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

didn't ever seen a problem 0.5 second!!! time limit during any contest!!! why so strict time limit is it a problem with only one solution, and any other solution would fail?!

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

    i believe this was done to avoid bruteforce solutions that try to compare every possible swap and output the best one. When it also can be done greedily.

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

    didn't use anything but swap and time limit!!!!!!!????

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

      Your solution is O(N2) because of string comparison. Calm down.

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

      I tried the very same thing as you but I got TLE in pretest 10, so i resubmitted with a greedy approach. Trying to generate the solutions with swap on a string seems to be too slow.

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

        i think it's luck that my solution passed pretest 10 and didn't think about the greedy one xd

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

          It's not :) If it got wrong answer, you could think of another solution and accept the code for real this time. Of course, it's good for the hackers, though :)

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

            of course it isn't i meant bad luck xD

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

    The only one solution is very very fast than other ways.

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

Is it unrated contest??!!! I am in place 700 and still gray... hooooow!

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

    No, it's only unrated for Div1 participants. You will be rated.

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

http://cfa.yuldashev.net/contest/508

Humble reminder in case if you missed the post

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

Very strange: during the round I was hacked by kgbugy659. She solved all the problems and was on the 2nd place before the end. But now she's out of scoreboard, her submissions are not listed in the room o_O Furthermore, her last rated round (before today) is not included in the graph. Weird %)

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

It may sound stupid, or rude, but I would please all the Div.2 / Div. 1+2 setters to announce the winners. I mean, especially for Div.2 contestants, who, some of them will never reach top 5 in a Div.1, it really makes them happy to see their names on the round post, and I consider it to be a nice thing. However, one will do as he wants, it was just an advice. :)

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

    I guess that the fact that Div 2 winners have been "newcomers" most of the time likely discourages writers from putting such thing in their posts.

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

      Hmm yes, this is a bit sad... But still, there is always at least one person in the top 5 wo isn't a newcommer.

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

    done

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

Why doesn't stoi() work on CodeForces? (C++11)

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

Can someone explain to me what could be so special about test case #40 for problem A. I tried to hack this solution during the contest: http://mirror.codeforces.com/contest/508/submission/9582562. I expected that if I had some moves 1000 1000, it would lead to RTE (as it must throw a segmentation fault) . But, my hack was unsuccessful.

I tried this test case: 1000 1000 4 1000 1000 1000 999 999 1000 999 999

Why did it fail to produce a RTE veredict?

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

    Array out of bound errors on C++ is undefined behaviour. It's usually impossible to know what the program will do in these cases.

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

      Thanks, I will keep this in mind before trying to hack again :)

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

    This hack would work: 

    1000 1000 1000
1000 1
1000 2
1000 3
...
1000 1000
    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Dang! I didn't check the time limit on problem B. My bruteforce solution got TLE :( I'd better check the time limit on each problem next time.

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

I am sad that my C(with set-stl),got TLE,but I am happy I became blue :D. That was my first goal,now it is division 1. I say that just because,I want grey and green users to know,that with 'correct' practise we can do everything :D

→ Reply