We will hold Xryuk-off contest. It starts: on 6/6/2022 at 7:00 UTC+0, and ends 7/6/2022 at 7:00 UTC+0
Contest is set by: I_LOVE_ANTON_DONBASS, DJeniUp, oleh1421, timreizin You will be able to give it a try tomorrow, you can see the results here: kabanchik-raiting.pw
Link to the contest system: kabanchik.contest.codeforces.com
Link to telegram channel with important information: https://t.me/kabanchikthesolvereng
Auto comment: topic has been updated by oleh1421 (previous revision, new revision, compare).
Auto comment: topic has been updated by oleh1421 (previous revision, new revision, compare).
Contest will start in 2 hours
19.5 hours left till the end of a contest. Don't miss the timer
Thank you for the problems! Here are some of my solutions:
F — a functional graph is a forest with a loop connecting the roots, so we can uniquely determine the number of a node $$$u$$$ not on the loop as the MEX of the numbers for all nodes $$$v$$$ it connects to. In turn, this means that we can determine the only two possible values for the values on the loop: the MEX, and the second MEX in case the first MEX was taken by the node it points to. After we get this, we can fix the value of some point in the loop and do a DP to see if such an assignment is consistent.
G — let $$$dp[i]$$$ be the answer for the prefix $$$[1,i]$$$ if we only use operations within $$$[1,i]$$$. Then, we have $$$dp[i-1]+(1-a[i])\to dp[i]$$$ if we don't do anything; and for all positions $$$j$$$ such that it is possible to cover $$$[j,i]$$$ all with ones and $$$[1,j-1]$$$ without restrictions, we have $$$dp[j-1]+(0[i]-0[j-1])\to dp[i]$$$ where $$$0[i]$$$ is the number of zeroes within $$$a[1,i]$$$. It is reasonable to instead consider $$$dp'[i]=dp[i]-0[i]$$$, giving $$$dp'[j-1]\to dp'[i]$$$.
For each operation $$$[l,r]$$$ let's find the minimum possible $$$dp'[j-1]$$$ over all possible $$$j$$$, if we must use the operation $$$[l,r]$$$. Then the immediate candidate is $$$j=l$$$; we also have candidates given by the intervals $$$[x,y]$$$ where $$$x\le l\le y\le r$$$. If we keep track of the best $$$dp'[j-1]$$$ for all intervals, we can sweep line by $$$r$$$, and the problem becomes to set $$$a[i]\leftarrow \min(a[i],v)$$$ for an interval and to query $$$a[j]$$$, which can be done with a segment tree.