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!

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

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

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.

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

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;) )

It coincides OpenCup. dafaq?

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 ??

wrong you can see it by exp3

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.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.

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

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

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

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

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

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

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.

So fast systest. Very wow.

hope the rating changes will be that fast ! :D

aaaanddddd... the rating changes are slow lol

relevant comment

Nice problems

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

What is the solution to problem D?

hint: You can use dp with bitmask

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

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

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

Just played that game:)

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)

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?

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

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

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

u have a statement

`c[i] = a[b[i]]`

, where`1 <= i <= n`

(not`1 <= i <= m`

). this is the reason forRE.change

`35`

to`105`

and u will getAC.is it problem C can solved by greedy?

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

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

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

i'm getting WA for test 20.. LOL

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.

haha.. i sort it ascending and get WA on test 20 LOL

now i just get accepted just as you say sort it by desc order

thanks for your explanation

when will the ratings be updated???

Sorry, I' m wrong.

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

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

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

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

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

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

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

There's some editorial for this contest?

← Rev. 2: Problem C

Spoiler Alert!