Welcome friends)

We are glad to introduce you regular Codeforces round #117 for Div.2 participants. Everyone can traditionally participate in it.

Problems are prepared by command of authors: Pavel Kholkin (HolkinPV), Ivan Fefer (Fefer_Ivan), Nikolay Kuznetsov (NALP) and Gerald Agapov (Gerald). Thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating problems.

And again score distribution will be dynamic) More information you can find here.

**Note that all problems today will be given in random order.**

Some Div.1 participants register for the contest before settings of registration were changed. Before the round it will be fixed and they will participate out of competition.

We hope that todays round would be succesful and everyone enjoys it. We wish you good luck and high rating!

**UPD**: the statement for problem 182E - Wooden Fence was formulated incorrect, correct variant of the statement will be soon, we apologize to the participants.

**UPD2**: the contest is declared unrated.

And are there dynamic problem max scores used?

`And again score distribution will be dynamic) More information you can find here.`

Hm, that's nice, but I asked before it was written in post. HolkinPV updated the post later (I can't delete my comment)...

502 Bad Gateway...Please allow me to enter

UPD:Oops...Did not realize that we have been given 10 more minutes to get ready :)Okay

wait a bit, contest was moved for 10 minutes due to server problem

Problem A will be the easiest one as the first dynamic contest ?

No

Yes. With probability 1/5.

Note that all problems today will be given in random order.

No, "Note that all problems today will be given in random order." ;-)

07:00 PM (Moscow Time), is the ideal time for a programming contest, please to keep this schedule for the future competitions.

Unable to ask questions. Getting "Field should not contain more than 1,000 characters" when the question is much shorter than that.

Maybe you have some copy-paste from HTML. And HTML source of your question exceeded 1000?

I did not copy paste the question initially, I just typed it in the box. I also tried using the "Remove formatting" option.

Thank you. I'll try to investigate it.

Unsuccessful challenge on problem E:

Input: 2 4

1 3

1 3

Output: 4

Answer: 4

How the answer is 4? It should be 2.

1) #1, rev#2

2) #2, rev#1

I asked a lot of questions during contest and got answers that for example (#1, rev#2) and (rev#1, #2) are same variants. In that case the answer should be 2 for the case above.

I think answer is 4,not 2. You get 2 combinations putting type 1 first, and 2 putting type 2 first.

According to the problem description 2 out of those 4 variants are the same.

P.S. I even asked a question to jury by specifying exactly such 4 variants, and got a response that 2 of them are duplicate.

i think that they assumed that a rotation is considered as new type

In problem E.

What is the answer for the input (2 3 1 2 1 2) ?

There are 4 sequence of fences.

seq0 : fence[0] -> turn(fence[1]).

seq1 : turn(fence[0]) -> fence[1].

seq2 : fence[1] -> turn(fence[0]).

seq3 : turn(fence[1]) -> fence[0].

But seq0 and seq1 are same, And seq2 and seq3 are same too.

So I think it is 2.

But if so, the answer for sample3 is 18 not 20.

Same issue for me :) Spent 1 hour on discussions with jury

I'm surprising when my not-finished solution passed examples(as well as the pre-tests). That is the same question. The admin's reply is just:

"I can only say, that rotation of the board does NOT change its type. So sequences with same boards but with different rotations are same."

So I don't know what is wrong: the standard solution, the statement or my understanding?

Problem C: Many people have wrong answer with pretest #15 (include me). Good pretest :D

[upd: sorry for asking the same questions other people already did. I typed the question at the same time.]

I have a question about problem E. Consider this test case: 2 3 1 2 1 2 Considering that

"Two fences shall be considered the same if the corresponding sequences of fence boards' types are the same", I think the answer should be 2 — a fence with board types A and B ((1,2),(2,1)) and another with types B and A (also ((1,2),(2,1))), where A and B are the two given types of fences. ((2,1),(1,2)) would be equal to one of these solutions, since only the type (and not the rotations) are considered during comparation.However, according to an unsucefull hack attempt, the answer is 4. I asked it during the contest, and they said that a fence with types (A,B,A) and (B,A,B) is also valid, but I can't figure out how it's possible with fence lenght 3... Can somebody? Thanks!

If we called the first block A (1,3) and the second block B (1,3) The 4 valid fences are : (A , rev_B) , (B , rev_A) , (rev_A , B) , (rev_B , A)

(B rev_B) and (rev_B B) are not allowed:

Update: the upper comment has been changed. See reiracofage's comment below.

But "A, rev_B" is equal to "rev_A, B" according the statment...

I took a look at the last example case and “deduced” that rotation also matters in the sequence comparison… I was getting WA locally for a long time, because that was not so clear from the problem statement, but I finally got it when there were about 10-15 minutes left; otherwise, I could have gotten C I think, using BIT :(

Does anybody know the solution to the Problem C? I try to use the Red Black Tree, but my answer is wrong..

It can be solved with treap.

Can I have the solution?

on a separate note, why isn't the system test starting?? [NOTE: I said this at the time when the blog did not contain the update; don't get this wrong :)]

There is a mistake in author's solution for problem E. Now authors are trying to fix it.

would that mean the problem would get invalidated? the last example case would not be reconcilable... if the statement is wrong/example case is wrong, IT SHOULD HAVE BEEN ANNOUNCED during the contest. I took it as a case where the statement is wrong AND the example case is right...

I think trying to fix the solution retroactively won't really work.

This will be another unrated round now i think.

let's see what the admins say about this.

I think there is no mistake, just a problem is missing something like: Two fences shall be considered the same if the corresponding sequences of fence boards' types

and dimensionsare the same.Too much thinking :) Your version and the initial one are different problems. Let's just wait the officials. Don't overthink.

I think missing something is also a mistake. I spend some time thinking and coding another method, and found I get WA on sample 3.

yea, I had to change my solution assuming something not stated within the problem statement, so as to fit the example test case (I thought something was missing in the statement but moved on, being under a time pressure) ;P

I didn't have any idea to count different types of board sequence. Can you share your code ?

you should get 18, on third sample.

Got the same answer. I wrote recursive DP with some hashes, comparing them at the end of recursion.

UPD: My Code here:

Usual dynamic programming, but as it will count duplicate cases also (like the ones on which author solutions are wrong) there is a way to count the number of these duplicate sequences separately and then subtract from original answer. To calculate duplicate cases, you need to consider the quantities of equal boards with different types, for example if there are K boards with the same size A x B and if required length is divisible by (A + B), then there are K * (K-1) * (K-1) * ... * (K-1) duplicates ((K-1) is repeated (length / (A+B)) * 2 — 1 times).

I`m not sure your solution be correct. there is a lot of possible paths (to build a fence), that have same sequence types with different width and length. I meant your solution doesn't count all paths.

Show example in that case.

I have a close idea with yours during the contest. But I think the subtract method you mention works only for A[i]!=B[i]. If A[i]==B[i], you should have a different subtract method or deal with it when dynamic programming.

I have excluded A[i] == B[i] during dynamic programming, you can just check if A[i] == B[i] then don't consider the variant when the board is rotated.

There is a bug in authors solution to problem E...Read the blog again...Its updated...I think this round is going to be unrated :(

I respect your opinion but I think that should be rated for div 2 because several people made a big effort to solve other exercises, including me. Thanks.

system testing is in progress... what's admins final decision?

See blog above: UPD2: the contest is declared unrated.

it's a pitty

I didn't consider to types of board, just i checked rotation of

squareboard with same type shouldn't count twice, and got Accepted! I think something is wrong yet.My comment was wrong, sorry...

Right, you suddenly decided that your comment became wrong the moment it got downvoted a lot :)

Whats case 15 in Problem C?

Try this smaller test cases:

out 16

out 7

In problem A, "Vasya moves at speed 1 meter per second in either direction." This makes it seem like he can move in either horizontal or vertical direction. This poor choice of words really confused me.

spending my time from 22.00 — 02.00 waiting the systest while I have mid test in the next day and the contest end with unrated. . what a pitty. .

Comment deleted after a bit of thought, for more details read my reply 2 branches down this comment :)

Oh seriously, how the hell is that anywhere near a trivial question or a "bad contribution to the community" that it gets downvoted?

Is it a good contribution or a non-trivial question, really? :-)

On a serious note, the editorial is already published here, it's just not translated into English yet. Most problem setters on Codeforces are Russian-speaking, so translating editorials takes longer than writing them, and it's a lot of work. Have patience.

Yeah, thanks Nickolas. I'm not trying to justify my comment or anything; but I was frustrated about my bad performance yesterday :) To tell you the truth, I think I don't actually care about the editorial, I just wanted something to complain about. Sorry and thanks again!

There is russian one

Thanks!

How did so many manage to solve E during the competition? It only passes if you make the same mistakes as the author; the answer to the first test case should be 3 since the second board lying down is a beautiful fence as well. You can see on the second test case that just having one board is okay.

Very old blog, but incase someone is stuck on problem C like I was, the idea is to maintain a set of K maximums using two sets.