Hello, Codeforces!

Once again, we've reached a round number that is a power of 2 at csacademy.com. In order to properly celebrate this, Round #64 will consist of interactive problems only. If you are not familiar with this type of problems on our platform, please read this blogpost before the contest.

The round will take place on Wednesday, 10/January/2017 15:05 (UTC). This contest will be a Div1 + Div2, with **7** tasks of varying difficulty that need to be solved in **2** hours.

#### Facebook event

Recently, Facebook has reintroduced the possibility of recurring events. If you choose "Interested" here, you will be notified before each round we organise from now on.

#### Contest format:

- You will have to solve
**7**tasks in**2**hours. - There will be full feedback throughout the entire contest.
- Tasks will not have partial scoring, so you need to pass all test cases for a solution to count (ACM-ICPC-style).
- Tasks will have dynamic scores. According to the number of users that solve a problem the score will vary between 100 and 1000.
- Besides the score, each user will also get a penalty that is going to be used as a tie breaker.

#### Prizes

We're going to award the following prizes:

- First place: 100$
- Second place: 50$

#### About the penalty system:

- Computed using the following formula: the minute of the last accepted solution + the penalty for each solved task. The penalty for a solved task is equal to log2 (no_of_submissions) * 5.
- Solutions that don't compile or don't pass the example test cases are ignored.
- Once you solve a task you can still resubmit. All the following solutions will be ignored for both the score and the penalty.

If you find any bugs please email us at contact@csacademy.com

Don't forget to like us on Facebook, VK and follow us on Twitter.

Just a reminder, the round starts in 4 hours.

The E problem looks very strongly like this CF problem and has got the same idea ... Second time in the CS the problem like in the 427 CF Round

About problem C. I still cannot understand why solution like

getc AC. If for example n = 3, isn't it enough to output just one query (for example 1 2)? This solution outputs at least two edges.

It's easy. My solution gets AC because checker (or interactor) is incorrect.

I think you should consider case when graph is not simple. Then yours is correct I believe.

UPD: sorry I dont know about it since I did not participate in the contest.But if multiple edges were allowed then solution seems correct right?

There was a public question during the contest.

anachor: Can the graph have multiple edges between same pair of nodes?

Answer: no

Will be the round still rated or rejudge expected? So many people found that it is incorrect, while I tried to find minimum number :/

Maybe semi-rated :)

The official editorial is ready! https://csacademy.com/contest/round-64/analysis/

It seems they don't care about correctness.

How can be solved the problem Eliminate Edge?

This is not very helpful, actually we can see solutions in the csacademy, I was seeking for some tips.

Here is what you should do!

SpoilerFirst you should read three integers NN, MM and QQ. After that, read MM pairs of integers representing two ndoes that share an edge.

The QQ queries follow, each consisting of two nodes vv and uu. After reading each query, you should print your answer:

If there is a unique simple path between vv and uu print 11 If the path is not unique, print 00 followed by two integers representing the edge you remove You should answer a query before reading the next one.

Fix any spanning tree

T. We'll never delete the edges fromT. AT-edge is an edge inT, aT-path is a path inT. Make a few observations:utovis unique iff theT-path fromutovconsist of bridges only.u-vis present it prevents the edges on theT-path fromutovinTfrom being bridges. Let's say that this edges 'covers' the edges in that path.We'll use heavy-light decomposition.

T-edge and query the sum on theT-path fromutovto get whether any edge on that path is covered. (Operations: path sum, path add)emaintain an unordered set in each segtree node that stores the edges that did a range-add update to that node. Treat these sets like lazy updates that do not propagate. If we walk from the segtree-node ofeto the segtree-root, we'll encounter all edges coveringein exactly in of the sets, so we can just find a non-empty set and pick an edge to delete from the sets, range add - 1 and print for the query.The total runtime is .

A simpler solution can pass for some reason (My solution with lowest memory usage uses #pragma, but it pases without it). (You might need to submit it a few times, as you can get "Something bad happened. Please resubmit and contact us.")

To check whether any edge on the

T-path fromatobis covered, iterate over all edgesu-vand check whether theT-paths fromatoband fromutovshare an edge. (If yes, thenu-vcovers that edge and can be output.) This can be done with a bunch of (but constant number of) LCA queries.Thanks! It was easier than I thought.

I was trying to keep the induced bridge tree of the graph, and recalculating at every query, or after K queries but I couldn't make it work.

I'll be glad to here other solutions for this problem (perhaps using some sqrt-technique) (without hld), since I find it very useful for a lot of problems.

My code for D didn't passed the examples during the contest and now it's is AC, amazing.

Is the checker of Limited Moves correct?

I keep receiving Wrong Answer on sample test 2(

`1024000`

) during the contest. Now, I test it in the archive and the log prints`499712`

,`1`

,`1`

,`1`

, ...,`1`

. Can't I win? or I misread something?Edit: After removing one of the

`assert`

, it got Accepted now. But, I remember that I have tried the same code without`assert`

during the contest.(Annoyed by lots of WA, I kept adding`assert`

to find out the problem) Then, why the verdict is showing`Wrong Answer`

when it went to an assertion failed?You should stop after 500 prints I guess?

As it is stated that your program must be terminated after the piles become 0 or there are already 500 interactions occured.

I am surprised that no one asked if it is 500 "turns" or 500 "moves from both players" in the real time contest.

Check the note of the third example.

You definitely need the experienced testers for rounds. I'm sure that problem Limited Moves was given several times before this round, and it's not the first problem this situation happens with.

nice contest