We will hold Panasonic Programming Contest 2023（AtCoder Beginner Contest 326）.
- Contest URL: https://atcoder.jp/contests/abc326
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20231028T2100&p1=248
- Duration: 100 minutes
- Writer: physics0523, kyopro_friends, evima
- Tester: nok0, MMNMM
- Rated range: ~ 1999
- The point values: 100-200-300-450-450-525-625
We are looking forward to your participation!
Hopefully constructive feedback. F would be better as a Yes/No question.
I "solved" the main part but implementation was really hard. Link
It would be better if it didn't exist. It requires 0 thinking and tedious implementation.
Meet in the middle didn't click for me until it was too late, but implementation was pretty straightforward ig. My solution
How to solve D ?
Today's problem D is healthy to your brain(you know what I mean).
Just DFS.
But very complex.
I DON'T KNOW WHAT YOU MEAN
I mean that this problem racks your brain!
Trash D!
How to solve $$$E$$$ anyone?
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.
can you please elaborate on the probability stuff? (how this result came?)
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
please Explain your D
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
okay
In the editorial of problem D, it says
In 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?
For N=5, I had to enumerate 20^5 combinations and then check if they are valid or not.
Why"For each row, there are only 20 conforming permutations. ( (5×4×3)/3=20 )",Why is it needed /3
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.
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?
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)
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/47026369
But it got WA on sample testcase #1. It output:
I do not know why it got Wrong. Please help me. :(
The 4th row is wrong.
Thanks a lot, I got it!
I got WA by this way too, but I still have a doubt.
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.
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?
Yo guys, is there way to see the hidden test cases for this contest?
They will eventually be posted here.
https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0
From whic topic F belongs?
F is pretty straightforward given that you read the problem statement carefully. I misread and thought that the rotations are optional at each step.