atcoder_official's blog

Panasonic Programming Contest 2023（AtCoder Beginner Contest 326） Announcement
By atcoder_official, history, 2 years 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?
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve D ?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Trash D!

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

→ Reply
»
2 years ago, hide # |
 
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
  • »
    »
    2 years ago, hide # ^ |
     
    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
    • »
      »
      »
      2 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        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
»
2 years ago, hide # |
← 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
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

From whic topic F belongs?

→ Reply
»
2 years ago, hide # |
 
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