### maroonrk's blog

By maroonrk, history, 3 years 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

| Write comment?
 » 3 years ago, # |   +12 Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
 » 3 years 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 years 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 years ago, # ^ |   +1 Hey AnandOza do you make a solution video for this contest..?
•  » » » 3 years ago, # ^ |   0 Nope, no plans to.
 » 3 years ago, # |   +19 How to solve E?
•  » » 3 years 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 years ago, # ^ |   0 Similar problem — D. Two Pirates — 2
•  » » » 3 years ago, # ^ |   +5 How to solve this problem?
•  » » » » 3 years 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 years ago, # |   0 Very Sad even my correct java solution $O(5000*5000*3)$ for Task $C$ got TLE. :(
•  » » 3 years 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 years 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 years 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 years 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 years ago, # |   +36 How to solve D ?
•  » » 3 years 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 years ago, # ^ |   +2 Can you describe the recursive approach in more detail? The bitwise magic isn't intuitive at all.
•  » » » » 3 years 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 years ago, # |   0 which test case i missed for problem b...?My solution
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 solution fails with 7 6 0 0 0 1 1 5 Answer should be 5, yours gives 6
 » 3 years 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 years 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 years 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 years 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 years ago, # ^ |   +1 Ohh Thanks a lot, got the reason behnd it as well.
 » 3 years ago, # |   +55 1406A - Subset Mex is a special case (k=2) for B, but the solutions are rather similar.
•  » » 3 years 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 years ago, # |   +1 how to solve C??
•  » » 3 years 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 years ago, # ^ |   0 Thanks it helped a lot
•  » » » 3 years ago, # ^ |   0 I also wrote a O(h*w) solution but it gave TLE. Can someone help me? submission
•  » » » » 3 years 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 years 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 years ago, # ^ |   0 Nice approach thanks it really helped.
•  » » 3 years ago, # ^ |   0 See this
•  » » » 3 years ago, # ^ |   0 your explanation is the same as editorial and for me it's hard to understand.
•  » » » » 3 years 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 years 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 years ago, # ^ |   -11 And, what is the meaning of $O(HW(H+W))$ ? Is $HW(x)$ some multiplication or what?
•  » » » 3 years ago, # ^ |   +6 It's O($H^2W + HW^2$) . Yes it's multiplication .
•  » » » » 3 years 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 years 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 years ago, # |   0 Can someone provide insight for C?
•  » » 3 years 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 years 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 years 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 years ago, # ^ |   0 It is O(n^2), not O(n)
 » 3 years ago, # |   0 Help me with the test case Solution B
•  » » 3 years 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 years ago, # |   0 Can i get a hint for problem A?
•  » » 3 years ago, # ^ |   0 $c[i]=max(c[i-1], max(a[0..i]*b[i]));$
 » 3 years 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 years 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 years ago, # |   0 Who can give me a concise Accept code of the C Problem?Please
•  » » 3 years ago, # ^ |   0 Maybe you can try reading my submission.
 » 3 years 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 years 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 years ago, # ^ |   0 To me ,there isn't any motivation to related this problem with bit mask.
•  » » 3 years 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 years 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 years 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 years 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 years 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 years 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 years 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
 » 3 years 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?
•  » » 3 years ago, # ^ |   0 Use spoiler tag. Otherwise people will just downvote it for pasting long code.
•  » » » 3 years ago, # ^ |   0 OK
 » 2 years ago, # |   0 The editorial of problem F said that "We can solve this problem in $O(L\log L)$ time with FFT and binary lifting. ", but how?