### atcoder_official's blog

By atcoder_official, history, 6 weeks ago,

We will hold Panasonic Programming Contest 2023（AtCoder Beginner Contest 326）.

We are looking forward to your participation!

• +57

 » 5 weeks ago, # |   0 Don't know why C wasn't accepted. Test cases were ok. Need to see editorial after the contest.
 » 5 weeks ago, # |   -8 Hopefully constructive feedback. F would be better as a Yes/No question.I "solved" the main part but implementation was really hard. Link
•  » » 5 weeks ago, # ^ |   -8 It would be better if it didn't exist. It requires 0 thinking and tedious implementation.
•  » » 5 weeks ago, # ^ |   0 Meet in the middle didn't click for me until it was too late, but implementation was pretty straightforward ig. My solution
 » 5 weeks ago, # |   0 How to solve D ?
•  » » 5 weeks ago, # ^ |   0 Today's problem D is healthy to your brain(you know what I mean).Just DFS.But very complex.
•  » » » 5 weeks ago, # ^ |   0 I DON'T KNOW WHAT YOU MEAN
•  » » » » 3 weeks ago, # ^ |   0 I mean that this problem racks your brain!
•  » » 5 weeks ago, # ^ |   0 Backtracking. It's like the N-Queens problem
 » 5 weeks ago, # |   0 Trash D!How to solve $E$ anyone?
•  » » 5 weeks ago, # ^ |   +1 First, we have to find the probability of ending at index $i$, let's say $p_i$ which would be $\sum_{j=0}^{i - 1} \frac{p_j}{n}$. The contribution of every $a[i]$ in the expected value then becomes, $a[i] \cdot p_i$. Sum over all $i$ gives us the answer.
•  » » » 5 weeks ago, # ^ |   +3 can you please elaborate on the probability stuff? (how this result came?)
•  » » » » 5 weeks ago, # ^ |   0 Let $E(i)$ denote the expected value if your variable $x = i$.Transition: $E(i) = \displaystyle\sum_{j=i+1}^n\frac{a[j] + E[j]}{n}$. Optimize by maintaining suffix sum of $a[j]$ and $E[j]$ Answer: $E[0]$ Submission
•  » » 5 weeks ago, # ^ |   0 please Explain your D
•  » » » 5 weeks ago, # ^ |   +3 I solved $D$ with optimized backtracking!While putting $\text{'A', 'B', 'C'}$ we will optimally make a recursion call by maintaining the given conditions! Submission
•  » » » » 5 weeks ago, # ^ |   0 okay
 » 5 weeks ago, # |   0 In the editorial of problem D, it saysIn fact, even when N=5, there are only 66240 grids such that each row and column contains exactly one A, B, and C.Can someone explain the math behind it?
•  » » 5 weeks ago, # ^ |   0 For N=5, I had to enumerate 20^5 combinations and then check if they are valid or not.
•  » » » 5 weeks ago, # ^ |   0 Why"For each row, there are only 20 conforming permutations. ( (5×4×3)/3=20 )",Why is it needed /3
•  » » » » 5 weeks ago, # ^ |   0 The first item of each row is already given to us. There is no need to try to enumerate 'A', 'B', or 'C'. For example, in the first test input "ABCBC" is given to us. So, the first non empty letter of the 1st row must be 'A'. The second non empty letter of the 2nd row must be 'B', and so on.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Thanks a lot, I got it!!!Orz
 » 5 weeks ago, # |   0 Can other right solves be accepted in D?
 » 5 weeks ago, # |   0 Is any one got E even F but no D like me :( ?
 » 5 weeks ago, # | ← Rev. 2 →   0 I suddenly have a cracy idea. If today's problem F's Constraints Change to:$1 \le N \le 10^3$$1 \le A_i \le 10^7$$-10^9 \le X, Y \le 10^9$How do you solve this?
•  » » 5 weeks ago, # ^ |   0 l use m-in-m to solve f but unkown to dp or other way to solve it
 » 5 weeks ago, # |   0 Thank you for the problems! I saw F and immediately thought "Isn't this NP Hard?" before realizing, hehe. Could not solve G, but it was educational (I keep overlooking Min-Cut Max-Flow Theorem, I need to practice more.)(Orz butsurizuki)
 » 5 weeks ago, # |   0 I want to know if my understanding of problem D is correct. Here is my submission during the contest https://atcoder.jp/contests/abc326/submissions/47026369But it got WA on sample testcase #1. It output: Yes AC..B BAC.. CB.A. ..ABC ..BCA I do not know why it got Wrong. Please help me. :(
•  » » 5 weeks ago, # ^ |   +3 The 4th row is wrong.
•  » » » 5 weeks ago, # ^ |   0 Thanks a lot, I got it!
•  » » » 5 weeks ago, # ^ |   0 I got WA by this way too, but I still have a doubt.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 The condition 2 and 3: means the leftmost/topmost position of number you filled in, instead of the leftmost/topmost position of the whole $N \times N$ grids.
•  » » » » » 5 weeks ago, # ^ |   0 Thank you.I got it!
 » 5 weeks ago, # |   0 Is there a constructive solution to problem D that doesn't rely on permuting through all $20^5$ grids? Or preferably avoiding anything exponential?I can only think of maintaining $dp[\text{row number}][\text{non-empty column mask}] = \text{possible (1) or not (0)}$ to allow computing answers row by row and then trying all possible combinations for a row in $O(n ^ 3)$. But this is still pretty slow at $O(n^4 \cdot 2^n)$ and is practically still an optimized brute force.Is there any clean constructive approach that solves this a faster complexity?
 » 5 weeks ago, # |   0 Yo guys, is there way to see the hidden test cases for this contest?
•  » » 5 weeks ago, # ^ |   0 They will eventually be posted here.https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0
 » 5 weeks ago, # |   0 From whic topic F belongs?
 » 5 weeks ago, # |   0 So, how to solve D ?DFS ?
 » 5 weeks ago, # |   0 F is pretty straightforward given that you read the problem statement carefully. I misread and thought that the rotations are optional at each step.
 » 5 weeks ago, # |   0 D I print Yes AC..B ..ABC ..BCA BAC.. CB.A. as the answer of sample 1, is it incorrect?