chokudai's blog

KYOCERA Programming Contest 2022（AtCoder Beginner Contest 271） Announcement
By chokudai, history, 19 months ago, In English

We will hold KYOCERA Programming Contest 2022（AtCoder Beginner Contest 271）.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

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

Comments Comments (32)
| Write comment?
»
19 months ago, # |
  Vote: I like it +9 Vote: I do not like it

F, but with variable XOR

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Also about D:

    If I am not wrong, then I think I have seen it on topcoder (in recent SRMs)

    Edit: Problem D

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah, I realized as well.. that I have seen similar problem before!

      → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G?

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D.

can anyone point out my mistake please
→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in Output section:

    be H if the i-th card should be placed with its front side visible, and T with its back.

    → Reply
»
19 months ago, # |
  Vote: I like it -28 Vote: I do not like it

Don't think it proper to put such a problem at Ex. All it requires is careful drawings. Maybe it's better to put it at E or F.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C, why this complecated rules to implement.

Why not read volumes in order if exist, else sell the two with higest volume numbers?

Tried to implement it, but WA. Why?

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    actually ono should use duplicate volumes first

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I did read this in the tutorial. Why?

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        because they are useless, we just read each volume once.

        take this as an example: currently 1, 1, 2, 2, 4, 5. and you finish reading volume 2. what should you do next?

        → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The following input should result in answer of 5, not 4.

    Spoiler
    → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try that case : 6 1 5 4 3 2 1

    answer : 5

    → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Counter test:

    5
1 2 2 3 5

    Actually, I just used binary search. It is easy to implement and not easy to get wrong. Here is the implementation, in case anyone is interested.

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Same, thought i overkilled it lol

      → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, tried greedy and failed thrice, switched to BS implemented it in one go T_T rank so low only because of this

      → Reply
»
19 months ago, # |
  Vote: I like it +17 Vote: I do not like it

E was a nice dp problem

→ Reply
»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Could someone help me figure out that one test case this implementation for problem C fails on.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D seemed easier than C. My submission is giving WA on 6 cases. Can someone provide a counter? Thanks in advance.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem F, it took me a long time to come up with the idea of meet-in-the-middle, but it was a pity that I didn't finish coding in time. Anyway, great problems, and hope next time I could do better.

→ Reply
»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Problem D and F are exact questions which was asked to me in a Google OA.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this logic didn't work in F?

Divide the square matrix into 2 equal triangles then start from $$$(1, 1)$$$ and calculate for every cell $$$(i, i)$$$ in the diagonal of the triangle, the no of ways to reach with xor sum as $$$k$$$ (say $$$dp[i][k]$$$, when $$$i = j$$$).

Then do a dfs from $$$(n, n)$$$ [with $$$(i - 1, j)$$$ and $$$(i, j - 1)$$$ moves], when reaching to cell $$$(i, i)$$$, say we have current xor sum as $$$k$$$ add $$$dp[i][k$$$ xor $$$val[i][i]]$$$ to the answer.

implementation

→ Reply
»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

E was nice, tried heavy dfs implementations, only to realise that a simple dp array will suffice

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

In editorial of G, I don't understand the O(N) solution part. Can someone explain please?

In O(logN) part, how are we getting this formula for DP

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F's same and a bit harder version https://www.geeksforgeeks.org/count-of-possible-paths-of-given-matrix-having-bitwise-xor-equal-to-k/

→ Reply
»
19 months ago, # |
  Vote: I like it +13 Vote: I do not like it

How to solve G,I can not understand it.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I am assuming that you understood infinite sum part. Take a dp matrix of size 24*24, dp[i][j] = probability that next move is at jth hour if last move was at ith hour. The probability of 1st move at jth hour is dp[23][i], i.e, setting 23 as the last move. So we can get the 1*24 matrix which would store the probability of getting at ith hour after 1st move by multiplying matrix initialState(it is of size 1*24, all values except 23 is 0 and initialState[0][23] = 1) by dp matrix

    Now let dp[i][j][k] (NOTICE: this is different state from editorial for simplification purpose first) = probability of ending at kth hour on ith move if last move was at jth hour. Now to get the probability of getting (i+1)th move on kth hour, let's assume that we are at xth hour on ith move and now we need to go on kth hour in next move, the conditional probability will be dp[1][x][k], so total probability will be dp[i][j][x]*dp[1][x][k]. So, dp[i+1][j][k] = $$$\sum_{x=0} ^{k-1} dp[i][j][x]*dp[1][x][k]$$$. So dp[i+1] can be written as dp[i]*dp[1], note that dp[i] and dp[1] are matrices of size 24*24

    So dp[i] = $$$(dp[1])^{i}$$$

    You can solve the above matrix with matrix exponentiation method and for getting probabilities you can multiply with matrix discussed in paragraph 1

    → Reply
»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

m_99, the English version of the editorial of G is completely broken and doesn't deliver your message. Could you please take a look and rectify the errors? Thanks.

I was only able to understand the solution after putting the Japanese editorial into a translator...

→ Reply