maroonrk's blog

AtCoder Regular Contest 176 Announcement
By maroonrk, history, 7 months ago, In English

We will hold AtCoder Regular Contest 176.

The point values will be 400-400-700-700-800-1000.

We are looking forward to your participation!

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

»
7 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Hoping for the best ARC Round!

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

Good luck to all who are competing!

→ Reply
»
7 months ago, # |
  Vote: I like it +60 Vote: I do not like it

As a writer,I hope everyone who participates in this contest will enjoy it. Good luck!

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

Good Luck!Hope C!

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

I didn't get the question right

→ Reply
»
7 months ago, # |
  Vote: I like it +21 Vote: I do not like it

A was kinda tricky if you don't get the point :( I spent 30+ min on it :(

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

    what was the idea?

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

    can u please explain the solution of A. I am unable to get (b[i] — a[i] + n) % n , i cant understand it even after looking at the editorial

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

      Maybe you can look at the following cases:

      One of the ways of n=6,m=1,(a,b)=[(1,3)]:
ooxooo
oooxoo
ooooxo
ooooox
xooooo
oxoooo
---
One of the ways of n=6,m=2,(a,b)=[(1,3),(5,4)]:
ooxooy
yooxoo
oyooxo
ooyoox
xooyoo
oxooyo

      Where x and y means $$$1$$$ and o means $$$0$$$. You can divide them into $$$n$$$ sets that in each set, the elements has a same $$$(b_i-a_i)\bmod n$$$.

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

        Nice Explaination , thankyou so much

        → Reply
»
7 months ago, # |
  Vote: I like it -36 Vote: I do not like it

Yet another pure math contest. I suck at math, so dislike.

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

can B be solved using bitmasks? I don't know about it but i reduced it to a point like this where quotient is

$$$ q = \frac {1000000....00_2} {111...1000...000_2} $$$

but I was unable to solve it as I'm not good enough in bitmasks and stuff

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

what is the idea behind A?

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

    The idea of the editorial is that:

    First, let's try solve the problem without the given m value-1 cells.

    How to solve m = 1? If you fill all cells on the antidiagonal with 1, then the sum of any row or column will be 1. No two cells on the antidiagonal are on the same row or column, and each row and each column are contributed by exactly one cell on the antidiagonal. (Assuming 0-based coordinate system is used) Cell v[i][j] on the antidiagonal are those where i + j = n-1. This solves the problem for m = 1.

    What if m = 2? First fill the antidiagonal with 1. Then, you can "shift" the antidiagonal by 1 to the left and fill this new "antidiagonal" with 1. This new "antidiagonal" covers all cells v[i][j] where i + j = n-2 and v[n-1][n-1], or equivalently all elements v[i][j] where (i + j) mod n = n-2.

    Applying to an arbitrary m, you just need to pick m such "antidiagonal"s and fill cells on them with 1.

    How to solve the original problem where m value-1 cells are given? You just need to fill the "antidiagonal" of those m cells first. Some of them might belong to the same "antidiagonal". Then you can fill any rest "antidiagonal"s as needed.

    → Reply
»
7 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Does B have no testcase with $$$n = m-1$$$ and $$$k=m-1$$$? I realised this condition a few seconds after submitting, but to my surprise, my code got AC.

→ Reply
»
7 months ago, # |
← Rev. 5   Vote: I like it +16 Vote: I do not like it

Data of problem A is weak. As a result of me and my friends' verification, there is not a single piece of data that is $$$M \ne N < 2M$$$. And this is the evidence.

For example, this code which I submitted during the contest must be wrong. It gives completely wrong answer with this input.

# Input
3 2
1 1
2 2

# My Output (Wrong)
6
1 1
1 2
2 1
2 2
3 3
3 3

I sent a clarification an hour ago, and I'll update as soon as possible when I see any response. I hope that I can write up a code that will allow me to get Accepted after the data is strengthened.

And I LOVE problem B. Very beautiful problem!

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

can anyone explain question b solution i did not understand

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

My First ARC got a 0pts but Rating+26, seems like it does need so many brainstroming instead of a number of algorithms at ahead problems.

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

Problem B is really a clever problem. I think I will never notice the case k=m-1 until I read the editorials. Hats off to the problem writers!

→ Reply
»
7 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Data of problem C is also weak

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

    The Editorial of C says:

    If $$$v$$$ does not exist or $$$X_v<k$$$, the answer is immediately determined as $$$0$$$.

    and I forgot to check this case ($$$X_v < k$$$) during the contest, but my code got AC.

    There is an input for this case:

    Input:
10 9
1 2 10
1 3 10
1 4 10
1 5 10
1 6 9
6 7 9
6 8 9
6 9 9
6 10 9
Output:
0

    my code during contest will give $$$40320$$$.

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

      My code passed your case, but for this case:

      Input:
5 3
1 4 3
4 5 4
4 3 4
Output:
0

      my code will give 4.

      I'm not sure whether this is common.

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

        I hacked a lot people when I try to use their codes to check my wrong code. I'm so helpless. Who could help me?

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

Can someone explain the following code for problem A — 01 Matrix Again ?

import java.util.*;
public class Main {
   public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] a = new int[m];
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            a[i] = scanner.nextInt() - 1;
            b[i] = scanner.nextInt() - 1;
        }

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < m; i++) {
            set.add((b[i] - a[i] + n) % n);
        }
        for (int i = 0; i < n; i++) {
            if (set.size() == m) {
                break;
            }
            if (!set.contains(i)) {
                set.add(i);
            }
        }

        System.out.println(n * m);
        for (int p : set) {
            for (int i = 0; i < n; i++) {
                System.out.println((i + 1) + " " + ((i + p) % n + 1));
            }
        }
    }

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

    There are total of n^2 elements in matrix so each (i-j)%n will occur atmost n times.

    (you can draw the matrix of (i-j)%n for some n to see it youself)

    since element are occurring on separate row and col we can assign 1 to such element that will increase the sum by n. How many times we need to do this? m times

    So at last we just need to select m remainders out of n and assign 1 to those positions.

    since some pairs are already given, we can just use remainder of those.

    I hope it helps...

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

can someone explain me the problem problem D in it ,I cant understand how transition states are made.

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

    Consider solving the subproblem for k, where we convert all p[i] <= k to 0 and p[i] > k to 1. The subproblem is to calculate, after m swaps, the number of (p[i], p[i+1]) such that one of them is 0 and the other is 1. Let s0, s1, s2 represent the states of containing 0, 1, 2 ones in an adjacent pair (p[i], p[i+1]) respectively.

    Now, let's consider the transitions of a single swap:

    • s0 -> s0, or to say p[i] = 0 and p[i+1] = 0 before and after the swap. There are 3 scenarios:
      • The swap doesn't involve i and i+1. The number of elements except i and i+1 is n-2. The number of swaps of this kind is C(n-2, 2).
      • The swap is (i, j), where p[j] = 0 and j != i+1. There are k zeros in total. Since both p[i] and p[i+1] are zeros, the number of rest zeros is k-2, and thus the number of such swaps is k-2.
      • The swap is (i+1, j), ... Similar to the above case, there are (k-2) such swaps.
      • The swap is just (i, i+1). Ofc the count is 1.
      • In conclusion, the number of swaps turning s0 to s0 is C(n-2, 2) + 2*(k-2) + 1
    • s0 -> s1: The swap is (i, j) or (i+1, j), where p[j] = 1. Since the number of ones is (n-k), the number of such swaps is 2 * (n-k).
    • s0 -> s2: There's no way to turn 2 zeros to 2 ones in a single swap.

    Transitions starting from s2 is just symmetrical to the above transitions starting from s0:

    • s2 -> s2: C(n-2, 2) + 2*((n-k)-2) + 1
    • s2 -> s1: 2 * k
    • s2 -> s0: 0

    Transitions starting from s1 can be similarly deducted:

    • s1 -> s0: k-1
    • s1 -> s1: C(n-2, 2) + (k-1) + ((n-k)-1) + 1
    • s1 -> s2: (n-k)-1

    With the above transitions, you can construct a 3x3 matrix M, where M[a][b] = the number of ways for the sa -> sb transition in a single swap. Let MM = M^m. Then MM[a][b] = the number of ways for the sa -> sb transition in m swaps. Let S be the 3x1 matrix where S[a][0] = the number of sa states in the original permutation. Let T = MM * S. T[a][0] will be the sum of the number of sa states after all possible m swaps. The answer to the subproblem is T[1][0].

    → Reply