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

- Contest URL: https://atcoder.jp/contests/abc271
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20221001T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: m_99, Kodaman
- Tester: leaf1415, physics0523
- Rated range: ~ 1999

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

We are looking forward to your participation!

F, but with variable XOR

Also about D:

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

Edit: Problem D

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

How to solve G?

In problem D.

can anyone point out my mistake please...

It looks fine. help pls

in Output section:

:((

Thanks i wasted more than 1 hour thinking what's wrong here.

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.

Can anyone find a counter test for my solution?

My solution

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?

actually ono should use duplicate volumes first

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

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?

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

Spoilertry that case : 6 1 5 4 3 2 1

answer : 5

Counter test:

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.

Same, thought i overkilled it lol

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

E was a nice dp problem

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

Counter example:

Spoiler4

2 2 2 3

Thanks.

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

Expected: 6 Received: 5

Just a minor bug, thanks for this counter tc.

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.

Same here. Next time we'll do better!

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

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

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

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

The simplest editorial for problem C: https://atcoder.jp/contests/abc271/editorial/4937

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/

How to solve G,I can not understand 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

In problem E, if we can choose the edges in sequence $$$E$$$ arbitrarily (not sequentially). Then how to find the shortest path? Do we have to use some classic algorithm (like Bellman-Ford) on sequence $$$E$$$?

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