maroonrk's blog

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

We will hold AtCoder Regular Contest 165.

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

We are looking forward to your participation!

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

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

tough contest

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

C is tough!

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

Cool contest, especially $$$B$$$ & $$$C$$$. Maybe there is easier solution, i solved $$$B$$$ using segtree(it is straightforward to find such index $$$f$$$, that after an operation on $$$v[f : f + k - 1]$$$, $$$v$$$ is maximal. We can compare results of operations $$$v[x: x + k - 1]$$$, $$$v[y : y + k - 1]$$$ in $$$O(\log n)$$$.) $$$C$$$ is pretty cool too. Thanks!

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

    How you solved C?

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

      Binary search on asnwer. THe same as editorial.

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

      There is a solution way easier than the editorial. Make a MST, and Color the vertices by the odd or even of its depth on the MST.

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

    Share code, please.

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

    I solve B greedy: As it is sure that after sorting the array will become lexicographically <= of the original array. First I calculate the longest increasing subarray.

    Case 1
    Case 2

    May be I am wrong but give me AC. submissions/45685014

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

    can you explain how you used segtree in your solution

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

I passed D in the last 2sec!!!!!

my submission

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

how to solve A

edit : solved

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

    to make the elements a1, a2, ...., ak to have N as their LCM these should be the prime factors of the number N.
    To make the sum equal to N, you need to check if the number of prime factors are atleast 3 because one of the prime factors would always be 1, and lcm(1, x) = x, which won't let the lcm to be equal to N.

    for example consider the case N = 10, we find out the prime factors of 10 as 1, 2 and 5. We can add these as 5+2+1+1+1 == 10 and LCM(1,1,1,2,5)==10

    Again consider the case N=8, prime factors of 8 = 1, 2 even though we can make the sum of prime factors equal to 8, we won't be able to make the LCM equal to 8 because LCM of 1 and 2 comes out to be 2.

    // implement the isPrime function here...

void solve() {
    long n;
    cin>>n;
    vector<long> factors;

    factors.push_back(1);
    for(long i=2;i<=sqrt(n);i++) {
        if (n%i==0) {
            if (isPrime(i))
                factors.push_back(i);
            if (n/i!=i && isPrime(n/i)) {
                factors.push_back(n/i);
            }
        }
    }
    if (factors.size()>2) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
    → Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

is this code O(n^2)? https://atcoder.jp/contests/arc165/submissions/45684077 or did i make a error somewhere.

(I asserted some places, so i do think its O(n^2))

(The Solution is to find scc, condense them, refind scc. i pass a graph of size atmost m atmost n times and my m pointers also move atmost n times, so i believe its n^2)

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

    Since you don't clear the graph fully I believe that it can have $$$O(nm)$$$ edges, so it will work in $$$O(n^2 m)$$$?

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
      ← Rev. 3   Vote: I like it +11 Vote: I do not like it

      Towards the end of my solve function, you can check just before i call scc() i assert the graph has <= m edges

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

        Oh, I didn't notice that you don't add a new edge if the pointer didn't move.

        Well, asserts seem to confirm that it is $$$O(n(n+m))$$$. The general structure of the solution is correct.

        Probably vector<vector<int>> is not a great idea. I generated a test: 223740510.

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

          unfortunate (and surprising since my friends have as low as 200ms) but thanks anyways

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

B test cases too weak
Passed with checking for the last 100 indexes and indices of elements 1...200 and taking the best of them
https://atcoder.jp/contests/arc165/submissions/45673283

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

    The tests are not weak, maybe author don't even expect such fake solution:)

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

First time in Top 10!

Also, problem F is really similar to IOI19 arranging shoes. F just added "lexiographically smallest" to IOI19 shoes, but it made the implementation way harder.

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

Are tests for B too weak? Looking at first python AC solution: https://atcoder.jp/contests/arc165/submissions/45672082

It seems like it should fail for something like:

4 3
3 4 1 2

It outputs 1 3 4 2. I think it should be 3 1 2 4

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

I have little difference with editorial in solution to $$$C$$$. I calculate the maximum $$$x$$$, such that if we remove edges with $$$w \ge x$$$, graph is bipartite. I use binary search for it. Let it be $$$A$$$. But then I don't calcalute minimum weight of path with length $$$2$$$ for remaining edges. Instead, in the whole graph I calculate minimum weight $$$B$$$ of path with length $$$2$$$, only once. The answer is $$$min(A, B)$$$.

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

I wrote I solution to C using binary search and checking whether the graph bipartite. But is gets WA, I have no idea why. I was debugging it for an hour, then I wrote a DSU solution.

Code (WA)
→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Graph can become disjoint after removing edges. And you check only one connected component of it.

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

Why is this solution correct for B? On the following input
6 3
6 3 2 5 1 4
The program outputs
6 3 1 2 5 4
When we can obtain
6 3 2 1 4 5
By applying operation on the last 3 elements. Please can anyone tell me what i am missing?

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

How to (or, Can we) add hacks for B? Tests are too weak.

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

As some of you mentioned, tests for B were weak. We added a few extra tests as after_contest.

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

    Will the solutions be rejudged(or perhaps rating recalculated)?

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

      No, it doesn't affect in-contest submissions.

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

In second solution of C can someone explain me how to find the weight of the edge at which the graph first becomes non-bipartite when starting from a graph with N vertices and 0 edges and adding M edges in ascending order of weight. I wasn't able to understand how the approach given in the editorial works to find this.

→ Reply