big oof

the only way it's happening is if next Div-3 will be unrated because of some problems. Is that what you wish?

Hugdiya

Iirc you get 12 hours after the contest to hack any solutions you want, but not for credit like the normal rounds. The only reward is to named as top 5 hackers (though the top spot is almost always halyavin!

Yes, I suppose :^) But one spoiler: two of them will be in two (easy-hard) versions.

we also need div.4 !!!

for me lol

• 479 https://prnt.sc/mn9x8x
• 481 https://prnt.sc/mn9xic
• 540 https://prnt.sc/mn9xq1

I know when you're this low rating you shouldn't really complain, and I am not. I am genuinely interested who should be able to solve these problems ? Is it aimed for people with rating around 1600? first ones were.

Anyways, liked the round and thanks for doing this to help beginners.

Me too :v :v :v

C was very interesting, there are several different ways to implement it (I think so), and you are to choose (find) one which is easiest to implement.

The only thing which came to my head(after reading C) was to jump out of the window

I think quality of rounds must be more important than quantity of them, seen many implementation and brute-force recently...

Задачи D-F решило около 10-15 % рейтинговых участников, поэтому очевидными называть их неуместно (в рамках раунда Div. 3, по крайней мере).

Div3 Problem Setters these days —

If (We have Div1F problem)
__ Print "Let's announce a Div3 round."
else
__ Print "Let's Wait for a Div1F problem."

me too ! i got WA at pretest 6 :((

maybe try: 3 1 1 1 1 2 2 3 3 4

answer

YES

1 2 1 3 4 3 1 2 1

my code accepted after handling this test case

try this

5 1 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 8 8 9 9 7 7 6 6

My code works well for all the above cases.

Maybe a case when N is odd and not equal to 3. I rectified that case and got AC on C.

For F1:

You need to count total number of red vertices and blue vertices in all the tree, then you can use simple dp to calculate for every vertex i the number of red children and blue children, let this value is pair<int,int> dp[i], now let's root the tree at node 1 and traverse using dfs, for each edge joining vertex "u" and vertex "v" you can remove it and check the number of red & blue vertices in each new tree in O(1) using (total number of red & blue vertices, number of red & blue vertices of the child), and count good edges

D1: binary search to check if we can get m pages in range [1, n] days

optimal strategy to finish m pages in x days is to use largest value in 1st days, 2nd largest in 2nd days, ..., x largest in 1st days again (cyclic)

D2 : Binary search on number of days. To find maximum number of pages he can write in d days, Greedily pick largest a[i]'s and distribute them over d-days. This will work because in optimal solution, difference between number of elements in any two days is less than or equal to 1.

F1 : First store the red and blue vertices in subtree rooted at v for all v, using dfs.

D1 or D2 : Let's apply binary search on the number of days required. For the current mid, let us greedily write pages restricting ourselves to at most "mid" number of days. We take the maximum value of a and write a[n] pages on day1, a[n-2] pages on day2 and so on. If at any point we exhaust the number of days, we continue by reading 1 less page from the current book. If at any point we are able to read m pages then mid is a candidate for the answer. submission

F1 : let's root our tree at vertex 1 for simplicity. For every vertex, let's calculate the number of blue and red vertices in its subtree. We can do this using dfs. After this we can check for every vertex by removing an edge to one of its children. The number of red and blue vertices left in each of the new trees is blue[v], red[v], red[1] — red[v] and blue[1] — blue[v]. Here we are at vertex u and v is one of its children. We can calculate answer easily then. submission

For D1:

I dont know if my solution will pass, but i used dp.

First, i noticed that if we will drink k cups in some day, then we need to drink the lower first, keeping the higher amount of caffeine to the end, so i sorted the array of inputs in the beginning.

Then, the dp state is dp[i][rem] is the number of days we need to write rem pages, using cups with indices from i to n, the recurrence is simple as we try to drink k number of cups in each day such that k is in this range [0,n-i+1].

solve( idx , rem ) = min( solve( idx+1 , rem ) , solve( idx + k , max( 0 , rem-k ) ) + 1 )

This solution is O(n*n*m) which is not bad. That's why i didn't manage to solve D2 as this solution will not pass the time or the memory limit.

cin/cout?

Because giving away 1 candy would mean even and odd sum are equal to 0 because no element remains. So the answer should be 1.

The amount of candies you eat in odd days is the same as the amount you eat in even days, which is 0 because you don't eat in any.

0 = 0

i solved the problem with a simple pattern that also satisfy this constraint

first use all pairs i(from 1 to k) and i + 1 mod k

then all pairs i and i + 2 mod k

after that pairs i and i + 3 mod k

and so on,you can easily see that this patern satisfies all the constraints

I don't see how your solution solves this problem. It fails on the first testcase itself, I think (b1=b4).

What purpose swapping them will serve. Afaik both of them carries equal points??

Problem E is rated 2000. If E and C were swapped,it would be rated no more than 1600.

Forget about the binary search for now, the idea is that for every number of days we know the optimal cups to drink, and their optimal order too, so we can get for every number of days the maximum number of pages we can write (we will talk about this optimal order later).

So if we know this kind of information, we can simply check all numbers of days between 1 to n, and select the least one that allows us to write at least m pages, and that's will be our answer.

Here's where binary search helps, as if we can write x pages in k days, then we can write x or more using more than k days.

The optimal cups to drink for a given number of days k is:

The largest cup in the first day, then the second largest one in the second day, and so on until we take k cups in the k-th day. Of course we can take more than one cup in a day, then we extend for the first day by drinking the k+1-th cup (don't forget to subtract the number of cups that are already drank as in the first day we actually will drink the k-1-th cup first then drink the largest cup, so we need to subtract it, same goes for all days), and for the second day we also extend it with the k+2-th cup, and so on.

submission

Probably Fantasyice is an alt account of tim25871014. Don't worry though, they will be skipped =)

Hack Test:
1
6575

Oh, sorry. I'll fix it soon. So don't be surprised with temporary disappeared ratings. I'll fix the issue and return ratings back.

Also, "Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

take part in at least two rated rounds (and solve at least one problem in each of them),
do not have a point of 1900 or higher in the rating."

Check https://mirror.codeforces.com/contest/1118/ratings, in top 10 you can see 7 are giving the contest first time

Because in the test 49 n=1 , but in the fuction check ,

for(ll i = 0; i < mid; i++) pgs += arr[i];

the i is too large , and then the arr[i] is unexpected

See this comment and reply.

Here it is. You are welcome :)