maroonrk's blog

By maroonrk, history, 4 years ago, In English

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!

  • Vote: I like it
  • +177
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +100 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

How to solve E?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Similar problem — D. Two Pirates — 2

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      How to solve this problem?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        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.

        Code
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it -7 Vote: I do not like it

    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

»
4 years ago, # |
Rev. 2   Vote: I like it +50 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it +10 Vote: I do not like it

      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)

»
4 years ago, # |
  Vote: I like it +36 Vote: I do not like it

How to solve D ?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

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

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 3   Vote: I like it +45 Vote: I do not like it

        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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

My solution

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +55 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +58 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

how to solve C??

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +17 Vote: I do not like it

    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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks it helped a lot

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice approach thanks it really helped.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See this

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone provide insight for C?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Help me with the test case Solution B

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can i get a hint for problem A?

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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!

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +30 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      To me ,there isn't any motivation to related this problem with bit mask.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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.

»
4 years ago, # |
Rev. 6   Vote: I like it +23 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain why it is necessary that $$$(n+m)M^2= m{2M\choose 2}$$$ in problem D's editorial?

Thanks.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 3   Vote: I like it +8 Vote: I do not like it

          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

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?