Unoficial Div 4 Round #2 Editorial

Revision en4, by I_Love_YrNameCouldBeHere, 2020-11-16 17:37:59

This is the editorial for the Unofficial Div 4 Round #2 created by I_Love_YrNameCouldBeHere and ssense.

We hope everyone had fun and enjoyed the contest!

Problem A — Catching the Impostor.

Tutorial

Problem B — Epic Permutation

Tutorial

Problem C — Similar Arrays

Tutorial

Problem D — Sanda's Job

Tutorial

Problem E — Count Substrings

Tutorial

Problem F — Game on Grid

Tutorial

If n = 0 (mod2) then you can split the grid into sections of squares with 4 smaller squares each, wherever Bob colours he will at most nullify 4 squares. If n = 2 (Mod 4) then if Bob always plays correct(nullifying 4 squares every moves) Alice still wins because they will play for an odd number of moves.

If n = 0 (mod 4) then then Bob's strategy is to just eliminate one colour. Because Alice needs all colours present to move the game will end in $\frac{n^2}{8}$ moves, this number being even so because playing optimally they can at most get 4 squares each move each will get the same number of squares.

If n is odd, then Bob will focus on the colour that is least present ( even column, even row ). Alice will get $4\cdot(\lfloor\frac{(n-1)^2}{8}\rfloor+1)$ and Bob will get $4\cdot\lfloor\frac{(n-1)^2}{8}\rfloor + 2\cdot n-1$ so Bob will get more for $n \geq 3$.

Exception for $n = 1$ but its easy to see that Bob would win.

History

Revisions

Rev. Lang. By When Δ Comment
en18 I_Love_YrNameCouldBeHere 2020-11-26 23:09:03 84 Tiny change: ' Editorial for the problems](https://' -> ' Editorial](https://'
en17 I_Love_YrNameCouldBeHere 2020-11-26 00:41:29 1
en16 ssense 2020-11-25 23:05:22 884
en15 I_Love_YrNameCouldBeHere 2020-11-25 19:56:56 510
en14 I_Love_YrNameCouldBeHere 2020-11-25 19:51:53 116
en13 I_Love_YrNameCouldBeHere 2020-11-25 19:48:14 323 Tiny change: 'wing.\n\n<a href="https://ibb.co/fQsCdCZ%22%3E<img src="' -> 'wing.\n\n<img src="' (published)
en12 I_Love_YrNameCouldBeHere 2020-11-25 19:26:32 116 Tiny change: 'is problem\n\nProble' -> 'is problem.\n\nProble'
en11 ssense 2020-11-25 19:18:38 691
en10 ssense 2020-11-25 19:07:51 72 Reverted to en8
en9 I_Love_YrNameCouldBeHere 2020-11-25 18:58:37 72
en8 I_Love_YrNameCouldBeHere 2020-11-25 18:55:25 30 Tiny change: ' can find cases dep' -> ' can find the answer by looking at the cases dep'
en7 I_Love_YrNameCouldBeHere 2020-11-25 18:50:43 2638 Tiny change: 'from $1$. Let \textit{even cell} denote a ' -> 'from $1$. _Let even cell_ denote a '
en6 I_Love_YrNameCouldBeHere 2020-11-16 19:56:56 21 Tiny change: ' larger then the medi' -> ' larger than the medi'
en5 I_Love_YrNameCouldBeHere 2020-11-16 18:58:06 9199 Tiny change: '2=$0 it is a d' -> '$ $2$ $=$ $0$ it is a d'
en4 I_Love_YrNameCouldBeHere 2020-11-16 17:37:59 1142
en3 I_Love_YrNameCouldBeHere 2020-10-30 12:45:45 31 Tiny change: ' it would change by $x$.\nThe sam' -> ' it would become greater.\nThe sam'
en2 ssense 2020-10-30 00:56:04 912
en1 I_Love_YrNameCouldBeHere 2020-10-30 00:43:10 2525 Initial revision (saved to drafts)