maroonrk's blog

AtCoder Regular Contest 176 Announcement
By maroonrk, history, 13 days 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
  • +53
  • Vote: I do not like it

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

Hoping for the best ARC Round!

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

Good luck to all who are competing!

→ Reply
»
12 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck!Hope C!

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

I didn't get the question right

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

    what was the idea?

    → Reply
  • »
    »
    10 days 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
    • »
      »
      »
      9 days 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 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nice Explaination , thankyou so much

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

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

→ Reply
»
12 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the idea behind A?

→ Reply
»
12 days 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
»
12 days 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
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain question b solution i did not understand

→ Reply
»
11 days 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
»
11 days 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
»
10 days ago, # |
  Vote: I like it +24 Vote: I do not like it

Data of problem C is also weak

→ Reply
  • »
    »
    9 days 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
    • »
      »
      »
      8 days 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
      • »
        »
        »
        »
        8 days 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 days 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
  • »
    »
    44 hours 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