Gerald's blog

By Gerald, 10 years ago, translation, In English

Good Day!

Coder-Strike 2014: Round 1 will start very soon. If you want to participate, please register for the contest on page. The round was prepared by me, HolkinPV and Igor_Kudryashov. And we tried our best to make it really awesome.

The round will be usual rated round for the second division participants. The first division participants can take part too, but for them the round will be unrated.

If you have any additional questions, please, ask at comments.

Hope you enjoy the problems! Good luck!

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

UPD 2. The competition was delayed by 10 minutes. :]

UPD 3. Because of unusual room assignment Div.1 and Div.2 participants will be in the same rooms this round.

UPD 4. The contest has ended, hope you like the problems. Rating for Div.2 participants will be updated a bit later.

Announcement of Coder-Strike 2014 - Round 1
  • Vote: I like it
  • +61
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is contest like another contests at Codeforces? 5 problems, hacking and ... ?

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

    "The round will be usual rated round for the second division participants." ..so i think yes :D

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

      Yep, you're right! :]

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

        Really easy contest... That was just about speed... And it didnt need neither programming skills nor theory knowledge (Except problem D)...

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

Why it's not rated for Div1 contestants?

Edit: Just noticed that it's a tournament for high school students.

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

    I think it is because this round is too easy for div1 coder... just like the div2 only contest

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

And what about round 2 ?! rated for Div1 users or not ?!

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

    I cannot tell you such an information right now for sure. Now I think that it will be rated for div1 participants with very low probability.

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

As you know, one thing included in rating calculation is rank. In this round div1 and div2 compete together. The whole rank will be included for rating, or div2's separate rank will be included? If we register in this round and we don't submit any code, will our rate decrease? I hope you understood my questions! :D

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

    Div.1 users can take part unofficially and they will not be rated. For official participiants and unofficial Div2 users rating calculation will be separated.

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

      I see. Div1 users will have no part in others rating. They just compete unofficially. Thanks

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

        Also, if you submit nothing, you will not be in the standings and your rating will not change (also, your position will not affect anyone else's rating).

        And div1-participants are in different rooms than the div2 ones, so that they can hack only other div1-participants.

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

          very nice :D

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

          users who submit nothing don't even affect rating of participants with negative score in final standings?

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

            Yes. They are not in the standings.

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

          hahaa see UPD 3 :P

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

I have a more general question. What happens if we register for a contest and because of a bad happening (such as losing internet connection or ...) we won't submit any code? Will our rate decrease or it will be same as before?

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

It only rate the schoolchildren in Moscow region, right? I was register and I saw "out of competition"

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

    The round will be usual rated round for the second division participants.

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

how long will it last?

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

Again delay..

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

    Nice Start!

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

    First Time to see delay without any problems appears to us

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

      Once the reason was, that official participants were having dinner that time :)

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

        At the end of the day, what's more important than dinner?

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

Oh~delay ten minutes. Is it because of the server?

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

    No Error appear it seems like system used to make a 10 min delay even if no problem appear

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

      This 10 minute delay is happening for every round! They should set a default 10 min delay :D

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

        if that happens, then rounds will get delayed by 20 minutes! :D
        actually they should set a default advancement of 10 minutes, so that the round will start at regular time! :)

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

    No, it is just to give some additional time for official participants.

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

    I think it is because of a technical reason: Some people are having dinner :))

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

      so please I need also 10 min extra to have a dinner :)

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

      No, i was late :)

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

First time div1 and div2 participants will be in same rooms! Looks very interesting! :)

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

Total: 2279 Contestants: 103 Out of competition: 2176

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

Can non russian participants win a t-shirt?

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

How will div2 users be rated? The ranking is not separated. Will the mixed rank be putted in the rate calculation formula or first you will separate the ranks of two divisions and then you will calculate according to the new separated ranks?

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

D = E

E = D

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

What was the indended solution for D? I thought about some bipartite matching, but the number of edges was too high. I suppose that either this or a constructive solution should apply. Is anybody available to give a little hint? (Don't spoil it yet).

  • »
    »
    10 years ago, # ^ |
    Rev. 4   Vote: I like it +5 Vote: I do not like it

    Topsort passed pretests.

    UPD: it passed full-tests.

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

    This passes pretests : reverse the edges, then find topological sort of this new graph, and output it in reverse order.

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

      But how is one able to topsort a graph which is not guaranteed to be a DAG? I suppose there is a slick trick involved in here. Am I right?

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

    topological sort

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

    Some Hint:

    Before we let an employee in, we let all of persons he owes money in then there will be no error ;)

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

      but how this is possible for cyclic graphs (second example)?

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

        Yes its error but your attempting to hack my hint ?! :D he should figure out that himself.

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

          At least for every hint given by now, I took the second exemple from the statement (the length 3 cycle) and said: how can one use such logic on non DAG graphs? (Also mentioned this in my second post up here). Did this approaches also pass SysTests?

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

            My version: it is possible to remove some edge from the cycle without loss for the final structure. So we made DAG.

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

            My code Passed 6412544

            There can not be a cycle with 2 node ( Two persons cant both owe each other ).

            For cycles with more than 2 node its ok we can write the reverse cycle starts from anywhere.

            Ex for test2 lets start from node 1

            employe than 1 owes is 2
            employe than 2 owes is 3
            employe than 3 owes is 1 ( but we visit that so we step back)
            print 3
            print 2
            print 1
            

            Thats one of answers. The solution i used at contest was based on the Topological Sort 6407870 but this one was easier to get.

»
10 years ago, # |
Rev. 5   Vote: I like it +3 Vote: I do not like it

hacking error

What type of error it is?I am not able to post the image so I posted the link.

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

    someone made a test, your program was unable to pass

    //link does not work

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

      I used input as file , and it was not hacked by others too.

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

    UPD :I corrected the link

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

    i think it means that when u submitted the hack, another hack was already submitted and in queue before urs. so by the time ur hack was "popped" from queue, the solution was already hacked, therefore ur hack was discarded.

    EDIT: however, it looks like u have got points for successful hack of his solution 6409307! not really sure what happened here!

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

      Thanks for answer.I thought the same.So I checked my room and refresh the site again and again but found that it is showing as correct solution.

      UPD : My point has been updated after the contest, they gave me it as successful hack.

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

Is the contest rated for div2 contestant ???

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

Is it possible to solve E using RE?

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

When will the system testing take place?

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

the ranks of div 2 participants depending on div 1 participants or not ?

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

    Since the contest is only rated for div2, it's only logical that ratings of div1 participants wouldn't affect that of div2 ratings. Although I'm not sure.

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

      I hope they will judge logically.

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

      I also think so... :)

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

      Yeah, this is what they just did, but since new rating depend of the rank and the expected rank, compete with div1 can only be good for us ;)

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

6407031 6407103
i honestly dont know why users try to cheat even in unofficial contests!! -_-

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

    How do you find same solutions?

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

      i hacked one of them, and just ran into the other while checking some Failed System Test solutions. i recognized immediately when i saw n - (k+2) (i hacked first submission on same mistake).

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

    Or this one 6411312 6406588

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

      His solution was hacked because he wrote stupid "if" in code. ;)

      Sorry for my bad English.

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

        but he wrote that purposefully to hack his "fake" account! look at the handles it is clear that one person use both accounts!!

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

          Oh, I didn't noticed that. Then he had cheated.

          ____________________________________________ Sorry for my bad English.

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

      Sorry for minus in contribution, didn't notice the difference between their handles :(

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

    They are out-of-competition here because only Russian high school students are official competitors, but these guys (guy?) still get rated.

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

      Because this contest was rated for div-2 participants

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

can someone explain why no test case with output -1 was included for problem D?

is an output of -1 impossible to get and if that's the case why? Thanks.

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

When rating of Div 2 participants will be updated ?

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

oh my god, tourist use 23min to solve all the problems....

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

    too long?

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

      it's not enough for me to even read all the problems ...

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

        First Note that he read problems in Russian his native language.
        Second almost he write solution while reading the problems.
        Third he is very fast in writing.
        Forth if you used all previous features you will solve problem "E" in 23 min.
        so you need a core I_7 mind to solve all of them in 23 min.

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

Is there any editorial for this contest. Or can anybody who solved Problem D and E kindly explain the approach for solving those ?

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

    editorial is here.
    for D, there is a much easier way than editorial. explanation is here.

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

Can anyone help me with E??? It seemed not very difficult but both during the contest and after that I'm getting WA on test 13. It is a very long string and as a result I don't understand where I went wrong in my code. A very short hack would be appreciated. Thanks.

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it
    ab@@c.com
    Answer : 0
    

    failed at testcase 26 during contest due to this bug, there's probably more bug in your code

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

      Thanks a lot. Solved cases similar to that and know I'm getting WA on test 23!!! It's driving me crazy!!! I'd appreciate it if you take another look at my code. Thanks.

      • »
        »
        »
        »
        10 years ago, # ^ |
        Rev. 5   Vote: I like it +1 Vote: I do not like it
        @a_1a@_.a
        Answer : 0
        
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        The substring between @ and . should be a non empty substring consisting only of letters and numbers.

        Your code check only one occurrence of _ after the first letter.

        So in a case like : a_@b_.c ... Your code count the substring b_ as a valid substring between @ and . ... while it is not !

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

        Thanks both of you: zeulb and YellowNextYear. I noticed this condition but implemented it in my code wrongly.