API tools faq
paste
Guest User

cf819 editorial raw

a guest
Feb 11th, 2023
785
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 16.33 KB | None | 0 0
raw download clone embed print report
  1. We'd like to thank you all for participating in the contest, and hope you enjoyed it. Hope to see you again next year!
  2.  
  3. <s>The editorial for problem F will be added soon.</s> It is now added.
  4.  
  5. ---
  6.  
  7. <h2>[problem:1726A]</h2>
  8.  
  9. Idea: [user:anubhavdhar,2022-09-06] <br>
  10. Editorial: [user:anubhavdhar,2022-09-06]
  11.  
  12. <spoiler summary="Hint 1">
  13. Which subsegments are relevant?
  14. </spoiler>
  15.  
  16. <spoiler summary="Hint 2">
  17. $a_n$ and $a_1$ can be taken up only by _some_ combination of elements, not all.
  18. </spoiler>
  19.  
  20.  
  21. <spoiler summary="Solution">
  22.  
  23. [tutorial:1726A]
  24.  
  25. </spoiler>
  26.  
  27.  
  28. <spoiler summary="Implementation">
  29.  
  30. <spoiler summary="C++">
  31.  
  32. </spoiler>
  33.  
  34. </spoiler>
  35.  
  36. <h2>[problem:1726B]</h2>
  37.  
  38. Idea: [user:anubhavdhar,2022-09-06] <br>
  39. Editorial: [user:anubhavdhar,2022-09-06]
  40.  
  41. <spoiler summary="Hint 1">
  42. Which cases of $n$ and $m$ are easy to come up with a solution? Which cases is it easy to show that no solution exist?
  43. </spoiler>
  44.  
  45.  
  46. <spoiler summary="Hint 2">
  47. What happens when $n$ is even but $m$ is odd?
  48. </spoiler>
  49.  
  50.  
  51. <spoiler summary="Solution">
  52.  
  53. [tutorial:1726B]
  54.  
  55. </spoiler>
  56.  
  57.  
  58. <spoiler summary="Implementation">
  59.  
  60. <spoiler summary="C++">
  61.  
  62. </spoiler>
  63.  
  64. <spoiler summary="Python">
  65.  
  66. </spoiler>
  67.  
  68. </spoiler>
  69.  
  70. <h2>[problem:1726C]</h2>
  71.  
  72. Idea: [user:Newtech66,2022-09-06] <br>
  73. Editorial: [user:anubhavdhar,2022-09-06]
  74.  
  75. <spoiler summary="Hint 1">
  76. When can a connected component begin?
  77. </spoiler>
  78.  
  79. <spoiler summary="Hint 2">
  80. What when two ```'('``` appear consecutively?
  81. </spoiler>
  82.  
  83.  
  84. <spoiler summary="Solution">
  85. There are several ways to solve this problem (even bash-able with data structures like DSU and Segment Trees), but here is the one that is easiest to code.
  86.  
  87. [tutorial:1726C]
  88.  
  89. </spoiler>
  90.  
  91.  
  92. <spoiler summary="Implementation">
  93.  
  94. <spoiler summary="C++">
  95.  
  96. </spoiler>
  97.  
  98. </spoiler>
  99.  
  100. <h2>[problem:1726D]</h2>
  101.  
  102. Idea: [user:Newtech66,2022-09-06] <br>
  103. Editorial: [user:Newtech66,2022-09-06]
  104.  
  105. <spoiler summary="Hint 1">
  106. what does $m \le n + 2$ mean?
  107. </spoiler>
  108.  
  109. <spoiler summary="Hint 2">
  110. What if we look at a spanning tree?
  111. </spoiler>
  112.  
  113. <spoiler summary="Hint 3">
  114. Does any arbitrary spanning tree work?
  115. </spoiler>
  116.  
  117.  
  118. <spoiler summary="Solution">
  119.  
  120. [tutorial:1726D]
  121.  
  122. </spoiler>
  123.  
  124.  
  125. <spoiler summary="Implementation">
  126.  
  127. </spoiler>
  128.  
  129. <h2>[problem:1726E]</h2>
  130.  
  131. Idea: [user:Newtech66,2022-09-06] <br>
  132. Editorial: [user:Newtech66,2022-09-06], [user:anubhavdhar,2022-09-06]
  133.  
  134. <spoiler summary="Hint 1">
  135. How will the permutation cycles look like ?
  136. </spoiler>
  137.  
  138. <spoiler summary="Hint 2">
  139. Can we fix the number of the largest sized permutation cycles and calculate the number of perfect permutations?
  140. </spoiler>
  141.  
  142.  
  143. <spoiler summary="Hint 3">
  144. How do we handle the smaller permutation cycles?
  145. </spoiler>
  146.  
  147.  
  148. <spoiler summary="Key fact">
  149.  
  150. **Key fact:** There are only $3$ kinds of cycles in almost perfect permutations: $(i)$, $(i, j)$ and $(i, j, i + 1, j + 1)$.
  151.  
  152. **Proof:**
  153.  
  154. - Cycle size cannot be $3$: Take $(a, b, c)$ as a cycle with $a < b < c$, then $p_b = a$, $p^{-1}_b = c$, but $a < b < c$ implies $\lvert a - c \rvert > 1$.
  155. - Cycle size cannot be more than $4$: Let $(a_1, a_2, a_3, a_4, a_5, \ldots, a_k)$ be consecutive elements of a cycle with size $k$ ($k \geq 5$). This means $a_1 \ne a_5$, but $\lvert a_1 - a_3 \rvert = 1$ and $\lvert a_3 - a_5 \rvert = 1$. For now assume $a_1 - a_3 = 1$ (proof of $a_1 - a_3 = -1$ is very similar). This means $a_3 - a_5 = 1$ (as $a_1 \ne a_5$) and similarly $a_7 - a_5 = 1$ and so on (if $k \leq 6$, $a_7$ is basically $a_{7 \bmod k}$; i.e. it wraps around). Now, we observe that if $a_1 = x$, then $a_3 = x - 1$, $a_5 = x - 2$, $a_7 = x - 3$. Therefore $a_{k + 1} = x - (k + 1)$. But since that cycle is of size $k$, $a_{k + 1}$ = $a_j$, for some $j \leq k$. Therefore $(x - (k + 1)) = (x - j)$, for some $j \leq k$; which means $(k + 1) \leq k$ &mdash; A contradiction.
  156. - works for any $2$ sized cycles $(i, j)$: Proof is trivial.
  157. - works for any $4$ sized cycles $(i, j, i + 1, j + 1)$: Proof is trivial.
  158. - works **only for** $4$ sized cycles $(i, j, i + 1, j + 1)$: Consider cycle $(a, b, c, d)$. $\lvert a - c \rvert = 1$, $\lvert b - d \rvert = 1$. WLOG assume $a < c$ (therefore $c = a + 1$).
  159. 1. _Case I_: $b < d$. therefore cycle is $(a, b, a + 1, b + 1)$ &mdash; of the given form.
  160. 2. _Case II_: $b > d$. therefore cycle is $(a, d + 1, a + 1, d)$, which is same as $(d, a, d + 1, a + 1)$ &mdash; also of the given form.
  161.  
  162. </spoiler>
  163.  
  164. <spoiler summary="Solution 1: the easy way">
  165.  
  166. Special thanks to [user:Um_nik,2022-09-06] for sharing this solution!
  167.  
  168.  
  169. Let's call $(i)$ as type $1$ cycles, $(i,j)$ as type $2$ cycles and $(i,j,i+1,j+1)$ as type $3$ cycles.
  170.  
  171. What we will do, is we will fix the number of type $3$ and type $2$ cycles and come up with a formula.
  172.  
  173. Let's say there are $s$ type $3$ cycles. We need to pick $2s$ numbers from $[1,n-1]$ such that no two are adjacent. The number of ways to do this is $\binom{n-2s}{2s}$. Then we can permute these numbers in $(2s)!$ ways and group the numbers in pairs of two, but these $s$ pairs can be permuted to get something equivalent, so we need to divide by $s!$. Hence we get:
  174.  
  175. $$\begin{aligned}\binom{n - 2s}{2s} \frac{(2s)!}{s!} \end{aligned}$$
  176.  
  177. Now, for the remaining $(n - 4s)$ elements, we know that only cycles will be of length $2$ or $1$. Let $I_k$ denote the number of permutations with cycles only of length $2$ and $1$. Then the final answer would be
  178.  
  179. $$\begin{aligned}
  180. \sum_{s=0}^{\lfloor \frac{n}{4} \rfloor}{\binom{n - 2s}{2s} \frac{(2s)!}{s!} I_{n - 4s}}
  181. \end{aligned}$$
  182.  
  183. Now, we would be done if we found out $I_k$ for all $k \in \{1, 2, ... n\}$. Observe that $I_1 = 1$ and $I_2 = 2$. Further for $k > 2$, the $k$-th element can appear in a cycle of length $1$, where there are $I_{k - 1}$ ways to do it; and the $k$-th element can appear in a cycle of length two, which can be done in $(k - 1) \cdot I_{k - 2}$ ways. Therefore we finally have:
  184.  
  185. $$\begin{aligned} I_k = I_{k - 1} + (k - 1) \cdot I_{k - 2}\end{aligned}$$
  186.  
  187. This completes the solution. Time complexity: $\mathcal{O}(n)$.
  188.  
  189. </spoiler>
  190.  
  191. <spoiler summary="Solution 2: the hard way">
  192.  
  193. Using the observations in **Solution 1** this can be reduced to a counting problem using generating functions. Details follow.
  194.  
  195. Now, from the remaining $n-4s$ numbers, let's pick $2k$ numbers to form $k$ type $2$ cycles. We can do this in $\binom{n-4s}{2k}$ ways. Like before, we can permute them in $(2k)!$ ways, but we can shuffle these $k$ pairs around so we have to divide by $k!$. Also, $(i,j)$ and $(j,i)$ are the same cycle, so we also need to divide by $2^k$ because we can flip the pairs and get the same thing.
  196.  
  197. Finally, we have the following formula:
  198.  
  199. $$\begin{aligned}
  200. \sum_{s=0}^{\lfloor \frac{n}{4} \rfloor}{\sum_{k=0}^{\lfloor \frac{n-4s}{2} \rfloor}{\frac{(2s)!}{s!}\binom{n-2s}{2s}\binom{n-4s}{2k}\frac{(2k)!}{2^k k!}}}
  201. \end{aligned}$$
  202.  
  203. We can simplify this to get,
  204.  
  205. $$\begin{aligned}
  206. \sum_{s=0}^{\lfloor \frac{n}{4} \rfloor}{\frac{(n-2s)!}{s!}\sum_{k=0}^{\lfloor \frac{n-4s}{2} \rfloor}{\frac{1}{2^k (n-4s-2k)! k!}}}
  207. \end{aligned}$$
  208.  
  209. Now, observe that the answer is in the form of two nested summations. Let us focus on precomputing the inner summation using generating functions. We define the following generating function:
  210.  
  211. $$\begin{aligned}
  212. P(x) &= \sum_{r \ge 0}{ \Bigg( \sum_{k=0}^{\lfloor \frac{r}{2} \rfloor}{\frac{1}{2^k (r-2k)! k!}} \Bigg) } x^r \\
  213. &= \sum_{r \ge 0}{ \Bigg( \sum_{k=0}^{\lfloor \frac{r}{2} \rfloor}{\frac{x^r}{2^k (r-2k)! k!}} \Bigg) } \\
  214. &=\sum_{r \ge 0}{ \Bigg( \sum_{k=0}^{\lfloor \frac{r}{2} \rfloor}{\frac{x^{(r - 2k)}}{(r-2k)!} \cdot \frac{x^{2k}}{2^k k!}} \Bigg) } \\
  215. &= \sum_{r \ge 0}{ \Bigg( \sum_{k=0}^{\lfloor \frac{r}{2} \rfloor}{\frac{x^{(r - 2k)}}{(r-2k)!} \cdot \frac{\big(\frac {x^2}{2} \big)^k}{k!}} \Bigg) } \\
  216. &= \Bigg(\sum_{i \ge 0}{\frac{x^{i}}{i!} \Bigg)} \cdot \Bigg( \sum_{j \ge 0}{ \frac{\big(\frac {x^2}{2} \big)^j}{j!}} \Bigg) \\
  217. P(x) &= \big(e^x \big) \cdot \big( e^{\frac {x^2}{2}} \big) = e^{x + \frac{x^2}{2}}
  218. \end{aligned} $$
  219.  
  220. We can compute the first few terms of $e^x = \sum_{i \ge 0}{\frac{x^{i}}{i!}}$ and $e^{\frac {x^2}{2}} = \sum_{j \ge 0}{ \frac{x^{2j}}{2^j j!}}$; and using FFT, we can multiply these (in $\mathcal O(n \log n)$ time) to get the first few terms of $P(x) = e^{x + \frac{x^2}{2}}$.
  221.  
  222. Finally, we can get the answer (in $\mathcal O(n)$ time) as,
  223.  
  224. $$\begin{aligned}
  225. \sum_{s=0}^{\lfloor \frac{n}{4} \rfloor}{\frac{(n-2s)!}{s!} \Big([x^{n-4s}] P(x) \Big)}
  226. \end{aligned}$$
  227.  
  228. where $[x^m]F(x)$ is the coefficient of $x^m$ in the Taylor expansion of $F(x)$.
  229.  
  230. Time complexity: $\mathcal{O}(\max{(t_i)}\log{\max{(t_i)}} + \sum{t_i})$, where $t_i$ is the value of $n$ in the $i$-th test case.
  231.  
  232. </spoiler>
  233.  
  234. <spoiler summary="Implementation">
  235.  
  236. <spoiler summary="Solution 1">
  237.  
  238. </spoiler>
  239.  
  240. <spoiler summary="Solution 2">
  241.  
  242. </spoiler>
  243.  
  244. </spoiler>
  245.  
  246. <h2>[problem:1726F]</h2>
  247.  
  248. Please note that it is no longer possible to submit solutions to this problem on Codeforces. You can read the details [here](https://codeforces.com/blog/entry/106700).
  249.  
  250. Idea: [user:little_angel,2022-09-06] <br>
  251. Editorial: [user:Newtech66,2022-09-08]
  252.  
  253. <spoiler summary="Hints">
  254.  
  255. <spoiler summary="Hint 1">
  256.  
  257. The $d_i$ are irrelevant. Take partial sums and add them to each $c_i$ modulo $T$.
  258.  
  259. </spoiler>
  260.  
  261. <spoiler summary="Hint 2">
  262.  
  263. If your start time is fixed, it is never beneficial to wait at a green light. Drive whenever you can.
  264.  
  265. </spoiler>
  266.  
  267. <spoiler summary="Hint 3">
  268.  
  269. Visualise the problem as $n$ parallel lines, each coloured with a red and green interval. Now imagine the car moving up (and looping back at $T$) whenever it has to wait at a red light, and shooting to the right immediately when the lights are green.
  270.  
  271. </spoiler>
  272.  
  273. <spoiler summary="Hint 4">
  274.  
  275. You can model this as a shortest paths problem.
  276.  
  277. </spoiler>
  278.  
  279. </spoiler>
  280.  
  281.  
  282. <spoiler summary="Solution">
  283.  
  284. There are solutions to this problem using lazy segment trees, or say, sets and maps. I'll describe my own solution here, which converts the problem to a shortest paths problem.
  285.  
  286. First of all, the $d_i$ are irrelevant, since we can take partial sums and add them to $c_i$. In the final answer, just add the sum of all $d_i$.
  287.  
  288. Now, we can offset the green (or red) intervals by the modified $c_i$ to get new red and green intervals modulo $T$.
  289.  
  290. Imagine $n$ parallel lines of length $T$, with the corresponding intervals coloured red and green. Now, consider the intervals to be static. In this picture, the car can be visualised to be moving upwards along the line (looping back at $T$) when on red intervals and shooting to the right when it reaches a green interval. Notice that for a fixed starting time, it is always optimal to drive whenever you can. So essentially, fixing your start time also fixes your answer.
  291.  
  292. Now let's convert this to a graph. Notice that only the endpoints of green intervals matter, so overall, we'll have $2n$ nodes in our graph, plus a dummy node representing the start of the journey that connects to all endpoints that can be reached without being blocked by a red interval, and a dummy node representing the end of the journey that connects to all endpoints from which you can reach the end without being blocked by a red interval. So in total, $2n+2$ nodes.
  293.  
  294. We'll add an edge between two nodes with a weight equal to the amount of time we'll have to spend waiting for the red light to turn green. We can achieve this with a multiset storing all currently visible endpoints, and then doing a little casework to add edges from nodes blocked by the current red interval and then deleting them, and adding new ones. We'll do this only $\mathcal{O}(n)$ times. In the end, whatever is left in the multiset are all the visible endpoints and we can connect them to the dummy node for the end. We can repeat this in the backward direction to get the endpoints for the dummy node for the start, though in my code, I elected to do this with an interval union data structure.
  295.  
  296. Finally, just run Dijkstra's algorithm on this graph. The answer is the sum of all $d_i$ plus the shortest path between the dummy node for the start and the dummy node for the end.
  297.  
  298. Time complexity: $\mathcal{O}(n \log n)$
  299.  
  300. </spoiler>
  301.  
  302.  
  303. <spoiler summary="Implementation">
  304.  
  305. </spoiler>
  306.  
  307. <h2>[problem:1726G]</h2>
  308.  
  309. Idea: [user:Newtech66,2022-09-06] <br>
  310. Editorial: [user:Newtech66,2022-09-06], [user:anubhavdhar,2022-09-06]
  311.  
  312. <spoiler summary="Hints">
  313.  
  314. <spoiler summary="Hint 1">
  315.  
  316. The happiness of a person can never decrease. It is obvious.
  317.  
  318. </spoiler>
  319.  
  320. <spoiler summary="Hint 2">
  321.  
  322. Let $T$ be the final value all elements are equal to. For all $x<T$, there can be at most one occurrence of $<x,1>$ in the array, where $<a,b>$ means a person with happiness $a$ and personality $b$.
  323.  
  324. </spoiler>
  325.  
  326. <spoiler summary="Hint 3">
  327.  
  328. There is only one possible $T$, given by $m+n-1$.
  329.  
  330. </spoiler>
  331.  
  332. <spoiler summary="Hint 4">
  333.  
  334. If it is possible to place multiple numbers in the order at a certain point (i.e. if there are multiple possible $<u,v>$ which when placed will all yield $<T,v>$), it is always better to prefer the larger number, and to place a number with personality $1$ over one with personality $0$ in case of a tie.
  335.  
  336. <spoiler summary="Subhint">
  337.  
  338. If $T=M$, the $<M,1>$ group is special, since it doesn't matter when you place it since the final happiness value will still be $M$, and it won't affect any other group's viability either.
  339.  
  340. </spoiler>
  341.  
  342. </spoiler>
  343.  
  344. <spoiler summary="Hint 5">
  345.  
  346. For a valid ordering (if exists), the $0$ behaving people would be sorted in non-decreasing order of initial happiness.
  347.  
  348. </spoiler>
  349.  
  350. <spoiler summary="Hint 6">
  351.  
  352. For a valid ordering (if exists) and at any intermediate step, for all $1$ behaving people $<u, 1>$ yet to speak, the number of people with a larger happiness than $u$ cannot exceed $(T - u)$. In other words, if we placed $<u, 1>$ at any intermediate step, its final happiness would not exceed $T$.
  353.  
  354. </spoiler>
  355.  
  356. </spoiler>
  357.  
  358.  
  359. <spoiler summary="Solution">
  360.  
  361. [tutorial:1726G]
  362.  
  363. </spoiler>
  364.  
  365.  
  366. <spoiler summary="Implementation">
  367.  
  368. </spoiler>
  369.  
  370. <h2>[problem:1726H]</h2>
  371.  
  372. Idea: [user:anubhavdhar,2022-09-06] <br>
  373. Editorial: [user:Newtech66,2022-09-06], [user:anubhavdhar,2022-09-06]
  374.  
  375. <spoiler summary="Hint 1">
  376. What role does the angles of the polygon play?
  377. </spoiler>
  378.  
  379.  
  380. <spoiler summary="Hint 2">
  381. Is there some overlap in the area of two such regions? How do we account for that?
  382. </spoiler>
  383.  
  384.  
  385. <spoiler summary="Solution">
  386.  
  387. [tutorial:1726H]
  388.  
  389. </spoiler>
  390.  
  391.  
  392. <spoiler summary="Implementation">
  393.  
  394. </spoiler>
  395.  
  396. ---
  397.  
  398. <h2>Vote for the problems here!</h2>
  399.  
  400. Feel free to vote for your opinion of each problem, and the best problem of the contest.
  401.  
  402. <spoiler summary="Vote here">
  403.  
  404. <spoiler summary="A">
  405.  
  406. - Best problem: [likes:1,option1]
  407. - Good problem: [likes:1,option2]
  408. - Average problem: [likes:1,option3]
  409. - Bad problem: [likes:1,option4]
  410. - Did not solve: [likes:1,option5]
  411.  
  412. </spoiler>
  413.  
  414. <spoiler summary="B">
  415.  
  416. - Best problem: [likes:2,option1]
  417. - Good problem: [likes:2,option2]
  418. - Average problem: [likes:2,option3]
  419. - Bad problem: [likes:2,option4]
  420. - Did not solve: [likes:2,option5]
  421.  
  422. </spoiler>
  423.  
  424. <spoiler summary="C">
  425.  
  426. - Best problem: [likes:3,option1]
  427. - Good problem: [likes:3,option2]
  428. - Average problem: [likes:3,option3]
  429. - Bad problem: [likes:3,option4]
  430. - Did not solve: [likes:3,option5]
  431.  
  432. </spoiler>
  433.  
  434. <spoiler summary="D">
  435.  
  436. - Best problem: [likes:4,option1]
  437. - Good problem: [likes:4,option2]
  438. - Average problem: [likes:4,option3]
  439. - Bad problem: [likes:4,option4]
  440. - Did not solve: [likes:4,option5]
  441.  
  442. </spoiler>
  443.  
  444. <spoiler summary="E">
  445.  
  446. - Best problem: [likes:5,option1]
  447. - Good problem: [likes:5,option2]
  448. - Average problem: [likes:5,option3]
  449. - Bad problem: [likes:5,option4]
  450. - Did not solve: [likes:5,option5]
  451.  
  452. </spoiler>
  453.  
  454. <spoiler summary="F">
  455.  
  456. - Best problem: [likes:6,option1]
  457. - Good problem: [likes:6,option2]
  458. - Average problem: [likes:6,option3]
  459. - Bad problem: [likes:6,option4]
  460. - Did not solve: [likes:6,option5]
  461.  
  462. </spoiler>
  463.  
  464. <spoiler summary="G">
  465.  
  466. - Best problem: [likes:7,option1]
  467. - Good problem: [likes:7,option2]
  468. - Average problem: [likes:7,option3]
  469. - Bad problem: [likes:7,option4]
  470. - Did not solve: [likes:7,option5]
  471.  
  472. </spoiler>
  473.  
  474. <spoiler summary="H">
  475.  
  476. - Best problem: [likes:8,option1]
  477. - Good problem: [likes:8,option2]
  478. - Average problem: [likes:8,option3]
  479. - Bad problem: [likes:8,option4]
  480. - Did not solve: [likes:8,option5]
  481.  
  482. </spoiler>
  483.  
  484. </spoiler>
  485.  
  486.  
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!