At this time the Olympics in Saratov.

I only hope this round is friendly

Oh My God,, I completely missed the round not even a minute

People from Far East are not able to participate in "usual" time for you. So this is this the one of few rounds in comfortable time for them. Please be patient :) P.S. But unusual time is in case of original olympiad time, to prevent cheating.

It's also good start time for Chinese, Korean, Japanese, people live in Kamchatka, etc.

there're still some people in asia

It means that you will be given six problems and two hours to solve them.

very nice time for china

another choice is no sleeping

Can't you do both?

we always stay up late to attend the test in summer,China.....

You won't. You will do badly and have 1833 rating right after.

Scoring is usually announced later.

What does that mean?

Go and learn DP. It is very useful.

Don't go to school (if you don't have any important exam).

Try this

For Bangladesh too. It's going to be 4:30 at afternoon.

Applese is so smart that he will solve all problems in this contest!

I'm sure there is not a human, there are a lot of humans :)

He was banned about an hour before the finish of contest

a lot of people ,he should be banned

Ha-ha

each player chooses only one number

one can choose only one card

read problem statement carefully. Each player can take only one number.

I think it's just some small random test. I got wa on test 3 because I didn't maintain parent array correctly.

well pretests are weak i guess i sorted the values by d before dp and another one in my room sorted by t both pretest passed

This test help me:

5
1 2000 1
1 2000 4
1 2 19
1 4 18
1 3 17

Ans:
59
5
3 5 4 1 2

D seemed ad hoc, I got AC in pretests. The number of changes is just n-number of unique integers in the input. And change the first duplicate to 1 and then the second duplicate to the next smallest possible element that's not in the array till now and fill like this. I hope it doesn't fail O.O

Editorials will be avialable soon , link will be given in thi post after update. Also you can view editorial directly from problem page once they are released. Usually editorials are avialable with few hours .

WTF

Sort items by deadline:

dp[j][t] — maximum value you can get, when you select from first j items, when you are at time t.

Submissions not passing the first test are not shown on the standings and are not counted in penalty.

I tried the same approach as you and I cannot come with a test that makes my solution fail. Let's wait until tests are visible... :(

upd: wrong answer 3183rd numbers differ — expected: '3390', found: '125991'

I think it is better to continue thinking about it XD

upd2: try this one

5
1 2 2 4 4

Note that the missing numbers are 3 and 5. On the forward iteration we will replace the first 4 with our 3, and on the backwards one we will replace the second 2 with our 5. This will leave the array 1 2 5 3 4. However, note that we can get the array 1 2 3 4 5 by changing two numbers, too.

looks like you haven't been participating in cf rounds since more than a month bcoz these days its fast.

Consider the arrays of short ints reach[3001][3001] and nex[3001][3001][13]. Define

• reach[i][j] = 1 implies there exists a path from i to j. Easily generated with DFS.
• nex[i][j][k] is the 2^k + 1-th node on the optimal path from i to j,  or infinity if it does not exist. First generate nex[i][j][0] from reach,  and then generate nex[i][j][k + 1] from the values of nex[i][j][k].

For a query (s, t, k) first check nex[s][t][12] and nex[s][t][0] to see if there is an infinite cycle, or a path does not exist. If none of these are equal to infinity, we can just compute the k-th node on the path in a similar manner to LCA.

Of course, it is easier to just compute the answers in an offline fashion.

A solution which probably uses a bit less memory than Benq's.

After reading the input, sort adjacency lists by the endpoint node: this way doing a DFS traversal will result in ideal paths.

Group all queries by the starting node. We'll answer each group separately with a separate DFS that starts from the starting node.

Doing the traversal maintain some additional data structures:

• A stack of the nodes on the current path (append the current node to it at the beginning of the recursive function and remove at the end).
• An array to tell if a node is currently on the stack (in current path). We can reuse the same array that we use to mark whether the node has been visited.
• Unordered set of nodes that form a loop: whenever we find an edge to a node that is currently on the stack, we add it to this set; before we end analyzing the node we remove it from this set (at the same time as we remove it from the stack).

Whenever we reach a node which is an end point in any of the queries with our starting node and we did not compute the answers for them yet:

• if the set is not empty, set the answer to -1 (we know that there is a loop that we can use to continue making the path to this node lexicographically smaller indefinitely);
• otherwise, set the kth element of the stack as an answer for each of the corresponding queries.

There is no edge 3-1.

yes......wait for the ratings updation.

Greedy + Simulation. Suppose you are at 0, if you can go to 0--->a---->f without refueling go, otherwise go to f first refuel and carry on. Vice versa for a to 0. Carefully implement it.

One way to solve problem C is using Dynamic Programming approach.

Think on this function F( i, j ) = maximum amount of gas that I can have if I have had i journeys using j times gas station before.

See my code for more details: 30708352

It was updated just now :)

Congrats, post was updated :)

Sorry...I mean Problem D...(will I get lots of downvotes? scared:(

Test case 3) Participant's output 1 2 4 5 6 7 8 9 looks sorted to me

deathsurgeon

"In the third line print m distinct integers — numbers of the saved items in the order Polycarp saves them."

The answer isn't necessarily sorted x)

Firstly, I misinterpreted the question. Secondly, I also got confused between "output" and "answer" in submission. Ahh, I'm getting old at this :/ Anyways, thanks NMouad21!

That could be because of incorrect algorithm. At least mine fails thereat.

Test your solution with

3 2 1
1 2
1 3
1 3 2

It should output 3

Consider any two items. If in the optimal answer, I am only going to take one of them, then their relative ordering doesn't matter.

But if both of them are in my optimal answer, then which one would you take first? It makes sense to take the one which is ending first (i.e. has a smaller d value) than the one which is ending later (i.e. has a higher d value).

Since if you first took the one which is ending later, and then took the one which is ending earlier, then you can also do the inverse, i.e. take the one which is ending earlier and then take the one which is ending later.

Its about the order of choosing of course its better to choose the items with less d first so they wont be expired

Imagine that d[i] + 1 is a moment when explosion hits i-th item. And DP approach here is just a process of caching recursive brute-force which would traverse items in increasing order of d[i] because it optimizes order preserving O(n!) bruteforce and overcomes 0-1 preserving O(2^n) bruteforce (there is no other simple bruteforces I've thinked about here).

try this case

7
6 1 1 6 1 1 6

Your output

5
2 1 3 5 4 7 6

Answer

5
2 1 3 4 5 7 6

What's more...I failed to analyze the code so no solution or reason to be provided. :(