Miss Div. 3 rounds? :)

<copy-pasted-part>

Hello!

Codeforces Round 540 (Div. 3) will start at Feb/19/2019 17:35 (Moscow time). You will be offered 6 or 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that **the penalty** for the wrong submission in this round (and the following Div. 3 rounds) is **10 minutes**.

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.

**Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.**

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

**UPD0**: I also would like to thank zimpha and Arpa for help with the round testing and finding some bugs!

**UPD**: Due to the problems being really interesting the round will last 2 hours 15 minutes.

**UPD2**:

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | Ghajini | 7 | 259 |

2 | ACtest | 7 | 271 |

3 | chrome | 7 | 274 |

4 | AuSquare | 7 | 341 |

5 | bonchinche | 7 | 343 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | limstash | 73:-9 |

2 | MarcosK | 59:-6 |

3 | TheRoot | 28:-1 |

4 | yqdjl6 | 23:-6 |

5 | 2014CAIS01 | 24:-9 |

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | 1021869 | 0:00 |

B | 15Y | 0:05 |

C | oldpreisnerboy | 0:11 |

D1 | omeravci372742 | 0:17 |

D2 | Ghajini | 0:17 |

E | __1900__ | 0:12 |

F1 | Seidukan | 0:10 |

F2 | 1021869 | 1:33 |

**UPD3**: Editorial is published!

Hoping to become expert with this contest.

GoodLuck and High Rating to everyone!

big oof

I wish all

rated(<1600) users in thisDIV-3will beUnratedin the next coming div-3 rounds!:-)

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

I'm pretty sure they wish those who are Div3 now soon to get over the 1600 threshold. They wish everyone a good performance, that is.

Hugdiya

Can anyone explain to me please, how the hacking session works? I would like to try it for this round. Thanks

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!

I love vovuh's Codeforces Round!! I wish I would go to expert..

I noticed that "(or 8)" was added next to the problem count in the copy-pasted part. On the last div3 round that part wasn't included. Does this mean that this round will have 8 problems?

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

We need more div.3!!!

we also need div.4 !!!

Sorry i have changed it due my wrong opinion.

This problem is too hard for Div.4, the sum overflows int.

do you mean, now we need less div 3?

yes so that will be better for the beginners

I don't know how having less contests is better for beginners. The more the better!

yaaa... more contests are not necessary. Because we can participate in virtual contest. But division 4 will be helpful for the participant whose have rating below the 1200. and it will also encourage the rating below the 1200 and beginners. Because it not possible for everyone to cross rating 1600.

if this comment gets more than 100 votes, I'll create a div4 contest in gym

Heh heh good try riela :P

Is it rated?

His dream come true.

Is there going to be a problem with an Easy and a Hard edition ?

I love cf

Best of luck to all.

That "(or 8)" smells like an easy-hard version

An uncertain-problem number contest :D.

I wish everyone high increase in ratings today. Happy Coding!

Happy New year all...

I hoped that there will be 7 or 8 problems,because a new problem can provide you a new skill.

Please make Div 3 rounds as frequent as Div 2. It is really good from the competition point of view. Otherwise Div 2 rounds include upto 2100 rated competitors on the ranklist which push coders like me to the bottom of the ranklist. Its really hard to even get to the top 1000.

All the way to

Expert. :Dfor me lol

Good Luck and Have Fun all!!

Broken Div.3 again? Why not to use this problemset for Div.2, when its difficulty is even about Div. 1.5... Or division is adjusted only by problem A? Look at good examples of problemsets of Div.3 contests: Codeforces Round 479 (Div. 3), Codeforces Round 481 (Div. 3).

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.

This image was taken with "show unofficial" disabled, so it seems like many under 1600 rating were able to solve the problems (with the exception of F2).

After reading the problem C I hated the problem and quit solving :)

Me too :v :v :v

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

"Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy."

Sees reds failing to solve F2...O_ODiv3 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."

I don't think F2 is that hard. It is just a smart extension and careful implementation of F1 (provided I did this things correctly :p). Maybe a Div 2 F though.

I found approach for F2 similar to XDCOMP

yeah, that's why reds failed to do that during contests

I think

Eis similar to Your text to link here...I am sorry that it just have chinese description.

You can see the solution of this from Your text to link here...

And I think that it can swap

CandEWhat's pretest 6 of problem C ?

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

It may well be a matrix with odd n and quantities of several numbers not divisible by 4, but divisible by 2. For instance, consider:

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.

how to solve D1 and F1

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.

for D1, 1. sort them in decreasing order. 2. apply binary search on ans. for F1, do a dfs to know ho many reds and blues for each subtree

very good problems for DIV3 , enjoyed very much . Hope all my problems gets accepted after hacking phase.

Author should stop setting problem C.

what is testcase # 9 in D1?...T^T

I think, I should change the first sentence in the announcement to "Miss Div. 1 rounds? :)"

But surely, this was expected that F2 is a pretty hard problem ¯_(ツ)_/¯

Why I got TL in F2 https://codeforces.com/contest/1118/submission/50197337

cin/cout?

Actually the same

The problem setter of C should be banned for some time for creating such bad problem

I hate filling numbers in matrix...it's so time-costing and brain-f***ing to consider about symmetry and indices...my poor little brain...

Is it possible to optimize the dp solution for D1 to solve D2?

WTF Why B test 1 1 Answer 1 ?!?!??!?!?!??!

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

Bonus:

Solve E with additional constraint:

first and last pairs are also considered adjacent for the 4th constraint (formally

b_{1}≠b_{n}andg_{1}≠g_{n})Fun fact: seems like this problem can be solved with this limitation in all the cases when the original problem can be solved.

Who can prove it or find a counter-test (or bug) in my solution 50193010, that solves problem with this additional constraint?

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

For the test case

`4 3`

my solution printsI see no problem there.

Really enjoyed the problemset. Best Div.3 round so far.

How to solve F2?

The contest would have been great if E and C were swapped.

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

Yes all carry equal points. Your point seems good, these things actually remind us to pick easy questions first (until you reach that level when C's implementation is a 8-10 min. cakewalk for you)

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

Can someone explain D2. I can't understand why we used a binary search in this.

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

These two participants have same source code in problem A, B, C, D1, D2, F1

tim25871014 Fantasyice

pA 50167147 50183932

pB 50185024 50186012

pC 50179384 50186141

pD1 50192694 50193272

pD2 50194759 50195089

pF1 50191152 50191524

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

Is there a way for which test case my code failed for B ques. It was hacked. I implemented this logic — store prefix sum of elements in odd and even indices in an array, and store the total sun. Then loop through given array once again , and check if sum to left of it the odd(/even) and right tO it the even(odd) prefix sun if equal to (totalSum-arr[I])/2. My submission is this: https://codeforces.com/contest/1118/submission/50179395[prob. B](https://codeforces.com/contest/1118/submission/50179395)

Hack Test:

1

6575

yeah found (in submission history). Thanks.

My code is giving output as 0 for n=1. It should have been 1 instead.

When does my brand-new rating reflects? I have to show off my

[ LEGENDARY SHINING BLUE ]to my friends"I forgot to fix participant types (official <-> unofficial) if you registered before rating changes of the yesterday contest. It will be fixed after the contest. Thus, you will be a rated (official) participant if and only if your current rating is strictly less than 1600. Mike."**** Some people above 1600 had their ratings increasedOh, 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:

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

Can anyone tell why my solution for D2 fails for test 49?

In my machine its output is

1as expected?The problem is solved when is decrease the upper bound for binary search to

n + 1.¯_(ツ)_/¯

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

Why the updated rating has gone? Any particular reason?

See this comment and reply.

vovuh, Editorials please.

the user ereased rating who has been skipped

It looks like codeforces have a new way to tackle plagiarism. The one whose solutions are skipped have been given a score of 0, and their rating changes have been calculated by keeping that score in mind !!!!

How to solve F2? I don't have any idea about it. Waiting for Tutorial.

This submission 50181596 got AC on D2 and WA on D1.

can anyone plz provide me the link to editorial

Here it is. You are welcome :)