We will hold KEYENCE Programming Contest 2021.

- Contest URL: https://atcoder.jp/contests/keyence2021
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210116T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: camypaper, maroonrk
- Tester: tempura0224 maspy
- Rated range: — 2799

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

We are looking forward to your participation!

Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).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.

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.

Hey AnandOza do you make a solution video for this contest..?

Nope, no plans to.

How to solve E?

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.

Similar problem — D. Two Pirates — 2

How to solve this problem?

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.

CodeVery Sad even my correct java solution $$$O(5000*5000*3)$$$ for Task $$$C$$$ got TLE. :(

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

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

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 :(

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)

How to solve D ?

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).

Can you describe the recursive approach in more detail? The bitwise magic isn't intuitive at all.

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.

which test case i missed for problem b...?

My solution

solution fails with

7 6

0 0 0 1 1 5

Answer should be 5, yours gives 6

I debugged C for a long time (> 30 min) and found out I didn't take mod in one place... Bye, rating :(

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.

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.

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.

Ohh Thanks a lot, got the reason behnd it as well.

1406A - Subset Mex is a special case (k=2) for B, but the solutions are rather similar.

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.

how to solve C??

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

Thanks it helped a lot

I also wrote a O(h*w) solution but it gave TLE. Can someone help me? submission

Might be because you are using function calls, which usually takes more time compared to doing everything within one function.

I actually saw your submission and mine. I got TLE on random_11 to random_15 which just took 4-5ms with your code.

Nice approach thanks it really helped.

See this

your explanation is the same as editorial and for me it's hard to understand.

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.

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

And, what is the meaning of $$$O(HW(H+W))$$$ ? Is $$$HW(x)$$$ some multiplication or what?

It's O($$$H^2W + HW^2$$$) . Yes it's multiplication .

Now I got it, thanks ;) It is not a function, it is simply parantheses arround the addition and not printing the multiplication sign.

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_sol

Note- It's different from the editorial because I have defined $$$dp$$$ in different way see here

Can someone provide insight for C?

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 down

dp[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

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.

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

It is O(n^2), not O(n)

Help me with the test case Solution B

Try this.

15 12

13 7 7 0 11 0 2 4 7 10 10 6 4 0 1

o/p:5 urs:4

Can i get a hint for problem A?

$$$c[i]=max(c[i-1], max(a[0..i]*b[i]));$$$

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!

Let f(N) be the function that solves this problem, that is, it returns a $$$vector<string>$$$.

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

Who can give me a concise Accept code of the C Problem?Please

Maybe you can try reading my submission.

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

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.To me ,there isn't any motivation to related this problem with bit mask.

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.

Re: Problem F — Keyence Repetition, and editorial

I'm unsure what the $$$O(k^3 L \log L)$$$ solution to the subproblem for the substrings of

`e`

s is, but here's one for $$$O(kL \log kL)$$$:For convenience, imagine a string of

`0`

s,`1`

s, and`2`

s 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

`e`

s 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)Can someone please explain why it is necessary that $$$(n+m)M^2= m{2M\choose 2}$$$ in problem D's editorial?

Thanks.

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.

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?

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:

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$$$).

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

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?

Use spoiler tag. Otherwise people will just downvote it for pasting long code.

OK

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?