oleh1421's blog

By oleh1421, history, 2 years ago, In English

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

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by oleh1421 (previous revision, new revision, compare).

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by oleh1421 (previous revision, new revision, compare).

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Contest will start in 2 hours

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

19.5 hours left till the end of a contest. Don't miss the timer

»
2 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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.