### maroonrk's blog

By maroonrk, history, 3 months ago,

We will hold KEYENCE Programming Contest 2021.

The point values will be 300-400-500-700-700-1000.

We are looking forward to your participation!

• +177

 » 3 months ago, # |   +12 Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
 » 3 months ago, # |   +100 Is there any consideration of changing the naming scheme for sponsored rounds to fit the ARC123 scheme? Something like "Keyence 2021 (ARC112)". This would make it easier to keep track of folders & URLs and stuff, similar to how every CF contest has a numerical ID even if it's sponsored.
•  » » 3 months ago, # ^ |   +59 I'm not the one to decide the contest name, but, as I heard, it depends on the sponsor. Sometimes we have ARC sponsored by XXX, sometimes XXX contest.
•  » » 3 months ago, # ^ |   +1 Hey AnandOza do you make a solution video for this contest..?
•  » » » 3 months ago, # ^ |   0 Nope, no plans to.
 » 3 months ago, # |   +19 How to solve E?
•  » » 3 months ago, # ^ |   +27 We will think in DP.First, we can know that, if the behavior of Snuke taking some candy doesn't affect Ant immediately, we can just delay it until it gives effect to Ant. So, if we want to take a candy far from Ant, we don't have to take it now, we will take it sometime later.Now let's define the table as follows:$DP[i][j][k]$: if candy 1~i and j~n remains, and we have k chances to take a candy, what will be the maximum score for Snuke?Now we can calculate this easily.
•  » » 3 months ago, # ^ |   0 Similar problem — D. Two Pirates — 2
•  » » » 3 months ago, # ^ |   +5 How to solve this problem?
•  » » » » 3 months ago, # ^ |   +4 First, we sort nos as given in editorial. dp[pos][left][turn] expected gold we will get if [1...pos-1] is taken by one of the parties and [pos...n] is yet to be taken. Similar to this ARC problem left is no of gold we have delayed. turn is a boolean which denotes whose turn it is.Then we have transition states. Codedouble dp(int pos, int left, int turn){ if(pos == n) return 0; if(left > n-pos) return 0; if(memo[pos][left][turn]>=0) return memo[pos][left][turn]; double ans = 0; if(turn == 1){ ans = dp(pos, left+1, 1-turn); } else{ // with probability left / (n - pos), this was taken double tkn = left * 1.0 / (n - (ld) pos); ans += tkn * dp(pos+1, left-1, turn); ans += (1.0 - tkn) * (a[pos] + dp(pos+1, left, 1-turn)); } return (memo[pos][left][turn] = ans); } 
 » 3 months ago, # |   0 Very Sad even my correct java solution $O(5000*5000*3)$ for Task $C$ got TLE. :(
•  » » 3 months ago, # ^ | ← Rev. 2 →   -7 I learnt very important lesson. Case1 — $long[][][] dp=new\, long[n][m][3]$Case2 — $long[][] dp1\,,dp2\,,dp3=new \,long[n][m]$Case2 is much more efficient(3 times faster in my case) than Case1.(due to cach missing?) Ac_C
 » 3 months ago, # | ← Rev. 2 →   +50 https://atcoder.jp/contests/keyence2021/submissions/19476838 this was one of the closest calls ever to me, passed F 3 seconds after the contest ended :( the only difference was that I removed 0's to the right of the polynomials..... Even the TL was a close call, passed in 6000ms out of 6000ms :D
•  » » 3 months ago, # ^ |   +8 Can you explain your solution? It seems like its different from editorial's. I tried calculating number of ways dividing $t$ into $k$ segments, where each segment should fit in one period, multiplied by number of times to choose each of this segment in a period. "simple formula" from editorial wasn't so simple to me :(
•  » » » 3 months ago, # ^ | ← Rev. 3 →   +10 It's just the editorial solution without being smart enough to think about treating adjacents not "ee" separately. Bruteforce the end/starting points with a divide and conquer solution to get O(N*log^2N) solution with high constant, probably something like 10.solve(l, r) returns a vector of (start, end, polynomial where exponent is the number of groups — 1)
 » 3 months ago, # |   +36 How to solve D ?
•  » » 3 months ago, # ^ |   0 By double counting on the number of pairs of people on the same team, we find that the number of games played is a multiple of $p-1$. Then we can construct a set of $p-1$ games that works using recursion (or using bitwise magic as described in the editorial).
•  » » » 3 months ago, # ^ |   +2 Can you describe the recursive approach in more detail? The bitwise magic isn't intuitive at all.
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   +45 So first say we solved the problem for $2^{N-1}$ people. Now split the people ${1, \dots, 2^N}$ into two sets, $L = {1, \dots, 2^{N-1} }, R = {2^{N-1} + 1, \dots, 2^N }$. Now consider applying the game creation procedure for $2^{N-1}$ people to $L$ and $R$, and let the games created be represented by $PL[i][j], PR[i][j]$, where $PL[i][j]$ represents the set of people in the $i$th game of the $j$th team (where $j = 0, 1$) for the games created by set $L$, and same for $PR[i][j]$. These each have size $2^{N-1}-1$. Then we consider the following new set of games for $2^N$. First make the games of the form ${PL[i][j]\cup PR[i][j], PL[i][j\wedge 1]\cup PR[i][j\wedge 1]}$, then the games of the form ${PL[i][j]\cup PR[i][j\wedge 1], PL[i][j\wedge 1]\cup PR[i][j]}$. This is basically mashing together games, and then flipping the way we mash them up. These make up $2^N-2$ games. The final game we add is ${{1, \dots, 2^{N-1}}, {2^{N-1}+1, \dots, 2^N}}$. It can be shown that this works.
 » 3 months ago, # |   0 which test case i missed for problem b...?My solution
•  » » 3 months ago, # ^ | ← Rev. 2 →   +5 solution fails with 7 6 0 0 0 1 1 5 Answer should be 5, yours gives 6
•  » » » 3 months ago, # ^ |   0 Thank you. I got it.
 » 3 months ago, # |   0 How to approach B problem?
 » 3 months ago, # |   +10 I debugged C for a long time (> 30 min) and found out I didn't take mod in one place... Bye, rating :(
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Maybe using a modular class or struct will help you. As you can treat it like type int (in c++) you probably won’t face problems like this anymore.
 » 3 months ago, # |   0 Can someone help, why I am getting runtime error on submission for Problem C on 3rd sample case. It is running perfectly fine on my system but giving runtime on Atcoder Custom Test.
• »
»
3 months ago, # ^ |
0
Code

please help me to know what is missing

•  » » 3 months ago, # ^ |   +8 i think runtime error is due to the value of x becoming < 0 for some testcases.i submitted your code after changing x=cnt[i-1][j+1]-cnt[i-1][j] to x=max(0,cnt[i-1][j+1]-cnt[i-1][j]) and it passed.
•  » » » 3 months ago, # ^ |   +1 Ohh Thanks a lot, got the reason behnd it as well.
 » 3 months ago, # |   +55 1406A - Subset Mex is a special case (k=2) for B, but the solutions are rather similar.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +58 As the author of the problem(CF1406A), I was pretty surprised when I saw problem B. I could have been the first accepted if my local laptop compiles a little bit faster...Really liked the problems, but sadly I failed to solve D because my guess for the smallest K was wrong.
 » 3 months ago, # |   +1 how to solve C??
•  » » 3 months ago, # ^ | ← Rev. 2 →   +17 Suppose robot is present at position $(x,y)$.If it moves toward $(x+1,y)$ then it would never travel cells in row $x$ from column $y+1$ to $w$ . Let say number of not assigned cells in segment $[x,y+1]$ to $[x,w]$ is $C$ . Then number of ways it can move toward $(x+1,y)$ from $(x,y)$ will be $ans[i][j]*3^C*T$.Where $T=2$ if $(x,y)$ not assigned any value,$T=1$ if it's 'D' or 'X' else $0$. $3^C$ because we can assign any value to the part which it doesn't travel.Similar analogy if it's move toward $(x,y+1)$.Thus it can be solved using 2 state DP with little pre-processing (Like powers of 3 , prefix sum matrices for row and column).submission
•  » » » 3 months ago, # ^ |   0 Thanks it helped a lot
•  » » » 3 months ago, # ^ |   0 I also wrote a O(h*w) solution but it gave TLE. Can someone help me? submission
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Might be because you are using function calls, which usually takes more time compared to doing everything within one function.
•  » » » » » 3 months ago, # ^ |   0 I actually saw your submission and mine. I got TLE on random_11 to random_15 which just took 4-5ms with your code.
•  » » » 3 months ago, # ^ |   0 Nice approach thanks it really helped.
•  » » 3 months ago, # ^ |   0 See this
•  » » » 3 months ago, # ^ |   0 your explanation is the same as editorial and for me it's hard to understand.
•  » » » » 3 months ago, # ^ |   0 It's different. In editorial $k$ is different where in my case $K$ is the value that we are assigning to cell $(i,j)$ so $K$ can take value $0,1,2$ depending upon whether we are putting $R,D,X$ in the current cell.
 » 3 months ago, # |   0 Can someone please explain the last paragraph of the editorial of the problem C? I know how to do C it in $O(HW(H+W))$, but how to do it in $O(HW)$?https://atcoder.jp/contests/keyence2021/editorial/570
•  » » 3 months ago, # ^ |   -11 And, what is the meaning of $O(HW(H+W))$ ? Is $HW(x)$ some multiplication or what?
•  » » » 3 months ago, # ^ |   +6 It's O($H^2W + HW^2$) . Yes it's multiplication .
•  » » » » 3 months ago, # ^ |   0 Now I got it, thanks ;) It is not a function, it is simply parantheses arround the addition and not printing the multiplication sign.
•  » » 3 months ago, # ^ | ← Rev. 3 →   +5 Let's say $dp[i][j][k]$ is no of ways to assign value in matrix $M_{i,j}$ such that $grid[i][j]=k$ and we can reach from $(1,1)$ to $(i,j)$ . If the current cell of grid i.e. $grid[i][j]$ has already assigned a value then the number of ways to construct new matrix i.e. $Z=dp[i][j][grid[i][j]] = (dp[i][j-1][R]+dp[i][j-1][X])*3^x+(dp[i-1][j][D]+dp[i-1][j][X])*3^y$. where $x$ is no of empty cell in the $i^th$ row with column value $< j$ and $y$ is no of empty cell in the $j^th$ column with row value $< i$. Now If $grid[i][j]$ has not already assigned a value then put the above value calculated in all three possible ways i.e. $dp[i][j][R]=dp[i][j][D]=dp[i][j][X]=Z$. My_Acc_solNote- It's different from the editorial because I have defined $dp$ in different way see here
 » 3 months ago, # |   0 Can someone provide insight for C?
•  » » 3 months ago, # ^ |   +2 Let us assume the robot is currently at position (i,j)let val_right = number of paths from (i,j) to (h,w) if it moves right val_down = number of paths from (i,j) to (h,w) if it moves downdp[i][j] = number of ways to move from (i,j) to (h,w)val_right = dp[i][j+1]; if the robot moves towards right then it will never visit any cell below it in it's current column therefore all the cell in the current column below it which have not been assigned any character('R','D' or 'X') (lets call it empty cell) can take any of the 3 value and independent of those value robot will move towards it's destination. Therefore valright gets multiplied by 3^(number of empty cell in current column below the current cell)val_down = dp[i+1][j]; similar to above logic val_down gets multiplied 3^(number of empty cells in current row to the right of current cell)if(c[i][j]=='R') dp[i][j] = val_right else if(c[i][j]=='D') dp[i][j] =val_down else if(c[i][j]=='X') dp[i][j] =val_down+val_right else dp[i][j] = 2*(val_right+val_down) (because empty can be assigned either 'R' or 'D' or 'X')Taking mod at appropriate positions and prestoring modulus of power of 3 (upto 5000)) will give AC
•  » » 3 months ago, # ^ |   0 The idea I used was instead of finding number of paths for each 3^(HW-k) configurations , I counted for a valid path from (1,1) to (H,W) in how many configurations will it occur.
 » 3 months ago, # |   0 idk why iam getiing tle in 5 cases i did it in O(n) still iam getting it .. Please point my mistake. https://atcoder.jp/contests/keyence2021/submissions/19474472
•  » » 3 months ago, # ^ |   0 It is O(n^2), not O(n)
•  » » » 3 months ago, # ^ |   0 Yeah ,Thank You Got my mistake..
 » 3 months ago, # |   0 Help me with the test case Solution B
•  » » 3 months ago, # ^ | ← Rev. 2 →   +1 Try this. 15 12 13 7 7 0 11 0 2 4 7 10 10 6 4 0 1 o/p:5 urs:4
 » 3 months ago, # |   0 Can i get a hint for problem A?
•  » » 3 months ago, # ^ |   0 $c[i]=max(c[i-1], max(a[0..i]*b[i]));$
 » 3 months ago, # |   +19 How to solve D? I discovered that the minimum possible number of operations $K$ equals $2^N-1$ during the contest and even got one way to satisfy the conditions for $N=3$. However, I didn't think of one way to construct the operations for all the $N$. I have already read the editorial of D and understood it but I haven't known how to get the constructive algorithm naturally. If you know that or you have other constructive algorithms which can be got naturally, please explain it to me. Thanks so much!
•  » » 3 months ago, # ^ | ← Rev. 3 →   +30 Let f(N) be the function that solves this problem, that is, it returns a $vector$.Through observation, we can find out that the number of operations is $2^N-1$ and that $m = 2^{N-1}$.Also, we can try the recursive algorithm, and consider the relationship between f(N-1) and f(N).First, let L be $[0, 2^{N-1})$ number people and R be $[2^{N-1}, 2^N)$ number people.Let's do doubling all the strings in the result of f(N-1) (vector with size $2^{N-1}-1$). (For example, "AB" to "ABAB")Then, when looking at only L's, m = $2^{N-2}.$Moreover, it is exactly half of R that opposes to element of each L. (Because it was doubling)To make a pair where each element of L is opposed to the other half of R, we can add all of the strings in f(N-1) by flipping them. (For example, "AB" to "ABBA")Then, each element of L forms $2^{N-1}-1$ oppositions with the elements of R, and $2^{N-2}*2=2^{N-1}$ oppositions between L's. , The total number of operations is $2^{N-1}-2.$Now, if we add AAAA....BBBB...., the elements of L will oppose the elements of R $2^{N-1}$ times, and the number of operations will also match our prediction.To summarize this,1) Doubling all strings of f(N-1), and reversely add them to the original string.2) Add an operation of the form AAA...BBB...In fact, I don't know if this is intuitive.I want to know how to intuitively think of bit & solution
 » 3 months ago, # |   0 Who can give me a concise Accept code of the C Problem?Please
•  » » 3 months ago, # ^ |   0 Maybe you can try reading my submission.
•  » » » 3 months ago, # ^ |   0 Thank you very much!
 » 3 months ago, # |   0 Why I got wa in problm B.my sub
 » 3 months ago, # |   0 4 4 0 1 2 3 How come the sol of this testcase is 0 ?? Can anyone explain that ?
 » 3 months ago, # |   +1 What is the logic behind D? I mean how could someone approach that kind of problem. I still don't know how people got to that solution intuitively
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 I also didn't solve it.And I asked some people who solved it during the contest , most of them says : they just try to solve some small case (n=3 is enough) by hand and find the law in the end.Edit: and there is a better way ,you can guess you need at least $2^n-1$ operations and use dfs to solve some small case and find the law behind it.
•  » » » 3 months ago, # ^ |   0 To me ,there isn't any motivation to related this problem with bit mask.
•  » » 3 months ago, # ^ |   +28 For me: constructive problem with only one integer as input? Try to solve for N=1 then use an answer for N to solve N+1. So just think about mathematical induction.
 » 3 months ago, # |   0 Hack for Problem C: 56 1 3 1 1 D 2 1 D 2 2 R The correct answer should be 0 (no valid path) but few accepted solutions give non zero answer
 » 3 months ago, # | ← Rev. 6 →   +23 I'm unsure what the $O(k^3 L \log L)$ solution to the subproblem for the substrings of es is, but here's one for $O(kL \log kL)$:For convenience, imagine a string of 0s, 1s, and 2s of length $L$ representing "which e" each one is (let's represent it as $r_i$). We want to count the ways to achieve a count of $r_i \geq r_{i+1}$; this corresponds to a $g_i < g_{i+1}$ constraint. Considering a pair of values, it turns out that if we add $3$ to the right value whenever $r_i \geq r_{i+1}$, it is equivalent to adding $1$, $2$, or $3$ per step.If we compute the polynomial $(x + x^2 + x^3)^L$, we count the number of ways to add $k$ in $L$ steps. If we shift the result by a carefully-chosen value determined by the character to the left of our substring (basically adding a fixed $r_0$ to the left of the sequence), we can have exponent $k$ encode $\lfloor k/3 \rfloor$: the number of $g_i < g_{i+1}$ constraints between es as well as between the left neighbor and the first e, and $k \text{ mod } 3$: the identity of the last e, i.e. $r_L$. This information, along with the character to the right, can then be used to build a polynomial for later convolution. (Personally I convert at this point to a count of $g_i \leq g_{i+1}$ constraints as that's more convenient for the later combinatorial math)
 » 3 months ago, # |   0 Can someone please explain why it is necessary that $(n+m)M^2= m{2M\choose 2}$ in problem D's editorial?Thanks.
•  » » 3 months ago, # ^ |   0 Left side is no of sequences times no of possible pairs in different teams.Right side is no of different pairs times how many times each pair is in a different team. Both of them should be equal since they are two different ways to count the same thing.
•  » » » 3 months ago, # ^ |   0 Thanks for the answer.but sorry, you told me what each term in the expression is but this isn't what I was asking, Both of them should be equal since they are two different ways to count the same thing this does not help as I don't understand what the same thing are they counting?Also, I do not follow your definition of LHS, what do you mean by sequences?
•  » » » » 3 months ago, # ^ |   0 The "same thing they are counting" is the number of pairs $(i,j)$ across all rounds such that $1 \le i < j \le 2^n$ and person $i$ and person $j$ are on different teams.For example, a solution for $n=2$ is as follows: ABAB ABBA AABB In this example, the pairs $(i,j)$ are $(1,2), (1,4), (2,3)$, and $(3,4)$ for the first round, $(1,2), (1,3), (2,4)$, and $(3,4)$ for the second round, and $(1,3), (1,4), (2,3)$, and $(2,4)$ for the third round.Now, the LHS counts this by noticing that the number of "different pairs" increases by $M^2$ each round, since there are $M$ people on one team and $M$ people on the other (recall $M=2^{n-1}$). So we just multiply the number of rounds $(n+m)$ by $M^2$ to get the total number of "different pairs" across all rounds. However, by definition, there must be exactly $m\binom{2m}{2}$ "different pairs" across all rounds, since $\binom{2m}{2}$ counts the number of pairs of people, and each pair occurs on different teams exactly $m$ times (by definition of $m$).
•  » » » » » 3 months ago, # ^ | ← Rev. 3 →   +8 Thanks a lot for putting your time into clearing my confusion !!My confusion was due to not realizing $(n+m)$ is the total number of rounds
 » 2 months ago, # | ← Rev. 3 →   0 For problem F.I maintain a 3*3 matrix for NTT.But if the string is "eee...eee", it consume too much time. The editorial say：For string "eee...eee" can solve in O(KL+LlogL)，so how to solve it?
•  » » 2 months ago, # ^ |   0 Use spoiler tag. Otherwise people will just downvote it for pasting long code.
•  » » » 2 months ago, # ^ |   0 OK