Gerald's blog

Coder-Strike 2014: Round 2
By Gerald, 11 years ago, translation, In English

Good day!

Coder-Strike 2014: Round 2 will start tomorrow at Russian morning. If you want to participate, please register for the contest on the page.

In much the same way as the first round, all users can take part in the competition. But this round will be usual rated round only for the second division participants. The first division participants can take part too, but for them the round will be unrated. Please, do not get upset, the next Coder-Strike round (finals) will be rated round for the first division participants.

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

Good luck, and see you on the contest!

UPD 1. Sorry for delay, the score distribution is standard.

UPD 2. The contest is over, congratulations to the winners, hope you like the problems!

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

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

Will the finals be rated for both divisions or the first division only?

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

    May be the finals problems will be too hard for div.2 participants. Now I cannot tell this for sure.

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

When will the finals be held?I hope it's also held at Russian morning(or afternoon) so it will be convenient for coders in China and other east asia countries.

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

    I am very glad to tell you, that mostly it will be held in Russian morning. =)

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

for the rating of this round when you get a best rank between Div 2 participants but between both participants you get the higher rank like 20! wich one is count for your rating?( I got the answer after the end of the Contest THX btw;) )

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

It coincides OpenCup. dafaq?

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

I think problem A of Round 2 have an ambiguity .....the value of ti must be ,min<=ti<=max ... correct me if i am wrong ??

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

    wrong you can see it by exp3

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

    ur not wrong in terms of the answer.
    but since the question doesnt specify these constraints, it means that u must print Incorrect in this case.

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

I don't know if it's why I've been awake for so long, but statements of problems C and D were a bit difficult to understand.

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

    yes, the explanation of problem D just make me more confused

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

      For the ones not knowing the games 2048, it would be much more difficult to understand

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

    A bit!!!I couldn't understand C through out the entire contest. and still I don't know how the game continues!

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

      I couldn't understand C either, I didn't realize that the questions can be selected in any order.

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

        even i took about 10-15 minutes to realize this fact, because problem statement said:

        then the questions are chosen by the one who answered the previous question correctly.

        since question was so confusing (especially about order), atleast explanation to example cases should have been included!

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

      we have to take care of R2 company only.......

      and they can choose any problem which is not taken already without considering any order......

      for 1st test case, take 1st,2nd and 4th at first then take 3rd no question.....

      The description of C could be more specified.... have no idea about D.

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

So fast systest. Very wow.

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

Nice problems

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

I don' t think there r much div 2 participants...

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

What is the solution to problem D?

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

    hint: You can use dp with bitmask

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

    You do a DP keeping an increasing sequence of powers of 2 by using a bitmask.

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

      Ah, I get it now, thanks. I should have noticed that only the increasing powers of 2 matter :P Also, it is very nice that when we add the number 2 or 4 to the mask, it modifies the mask according to the rules of the game. :D

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

    At first figure out what was the problem . weird statement, one more disgusting contest with poor statement.

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

    Just realize that it can be solved using dp bitmask, anyway i have a different dp solution by considering that it is possible to get 2^{K} if there's 2^{K-2} consecutive 4 (two consecutive 2 can be merge into 4)

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

And also I have no idea why my first submission for Problem C got RE. I changed the size of arrays then I got AC later, but why?

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

    I have the same situation, but with problem B :/

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

      in problem B I have same situation too, but that's because i miscalculated array for n is 2000 not 20000 .. LOL

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

        But I' m sure the size is big enough, for the number of auction problems is at most 30.

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

    u have a statement c[i] = a[b[i]], where 1 <= i <= n (not 1 <= i <= m). this is the reason for RE.
    change 35 to 105 and u will get AC.

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

is it problem C can solved by greedy?

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

    Yes! U can calculate the sum of the points of regular problems and the add the points of other problems

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

      how can it be? can you explain a bit more?

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

        well, I' m afraid my poor English can' t explain it clearly... U can view my code. that' s much clearer, I think.

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

    Yes. Basic idea is to take all regular questions first (since you need to take them at some point anyway), then sort auction questions by decreasing order of price and, for each, either double your score or increase it by the auction question price (whichever is greater).

    The point is that you want as high a score as possible when getting to a specific auction question, so you should always start with the highest values.

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

when will the ratings be updated???

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

First Time to uncheck box "show unofficial" & didn't see any one all of us are unofficial :D

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

Why don't the problems of any Coder Strike round appear in the problemset?

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

    They do. Look at 413 A, B,...

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

      ya thanks i expected them at the top they appeared lower in the list :P my bad

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

What is the solution to E? Is there some approach using segment trees/BIT ?

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

    I used DP in segments of length equal to a power of 2 and then merged them to solve the queries. You could also do that with a segment tree.

    Code: 6427362

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

    Yes, there is a solution using segment tree.

    Consider the interval [l; r].

    Cell of maze will be denoted a pair (i, j) — the index of row and column.

    For interval [l; r] we will store an array d[2][2]. d[i][j] — length of shortest path between (l, i) and (r, j).

    For segments [l; l] is easy initialize the array d. We can easily merge two adjacent segments s1 = [l; m] and s2 = [m+1; r].

    d[i][j] = 1 + min(s1.d[i][0] + s2.d[0][j], s1.d[i][1] + s2.d[1][j])

    My submision: 6425791

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

There's some editorial for this contest?

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

← Rev. 2: Problem C Spoiler Alert!

→ Reply