atcoder_official's blog

Panasonic Programming Contest 2023（AtCoder Beginner Contest 326） Announcement
By atcoder_official, history, 13 months ago, In English

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

We are looking forward to your participation!

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

Comments Comments (30)
| Write comment?
»
13 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Hopefully constructive feedback. F would be better as a Yes/No question.

I "solved" the main part but implementation was really hard. Link

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    It would be better if it didn't exist. It requires 0 thinking and tedious implementation.

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

    Meet in the middle didn't click for me until it was too late, but implementation was pretty straightforward ig. My solution

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

How to solve D ?

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

    Today's problem D is healthy to your brain(you know what I mean).

    Just DFS.

    But very complex.

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

Trash D!

How to solve $$$E$$$ anyone?

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

    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.

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

      can you please elaborate on the probability stuff? (how this result came?)

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

        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

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

    please Explain your D

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

      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

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

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?

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

    For N=5, I had to enumerate 20^5 combinations and then check if they are valid or not.

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

      Why"For each row, there are only 20 conforming permutations. ( (5×4×3)/3=20 )",Why is it needed /3

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

        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.

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

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?

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

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)

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

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:

Yes
AC..B
BAC..
CB.A.
..ABC
..BCA

I do not know why it got Wrong. Please help me. :(

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

    The 4th row is wrong.

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

      Thanks a lot, I got it!

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

      I got WA by this way too, but I still have a doubt.

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

        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.

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

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?

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

Yo guys, is there way to see the hidden test cases for this contest?

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

From whic topic F belongs?

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

F is pretty straightforward given that you read the problem statement carefully. I misread and thought that the rotations are optional at each step.

→ Reply