Agnimandur's blog

By Agnimandur, 9 months ago, In English

All the division 2 problems were created by Agnimandur. 1548E - Gregor and the Two Painters was created by Benq. I hope that this hint-based editorial helps you, no matter what your rating is! Solution code is provided in both C++, Java, and Kotlin when available.

Solution Code Repository


1549A - Gregor and Cryptography

Hint 1
Solution

1549B - Gregor and the Pawn Game

Solution 1

Hint 1
Hint 2
Solution

Solution 2

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1549C - Web of Lies

Hint 1
Hint 2
Solution

1549D - Integers Have Friends

Hint 1
Hint 2
Hint 3
Solution

1549E - The Three Little Pigs

Solution 1

Hint 1
Hint 2
Hint 3
Solution

Solution 2

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1549F1 - Gregor and the Odd Cows (Easy)

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1549F2 - Gregor and the Odd Cows (Hard)

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

1548E - Gregor and the Two Painters

Hint 1
Hint 2
Solution
 
 
 
 
  • Vote: I like it
  • +73
  • Vote: I do not like it

»
9 months ago, # |
Rev. 2   Vote: I like it +65 Vote: I do not like it

Sorry about having to create a new editorial!

The old one passed some character limit built into Codeforces. Whenever I attempted to edit the old one, I was re-directed to the bug page, and the edit was not saved!

Thus, the editorial went offline for a while. Ultimately, a new and shorter editorial, was the only viable solution.

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

    Could you post the old editorial page without the edits? There were several helpful (at least for me) discussions about GCD and solution of 1549D - Integers Have Friends without segment tree and sparse table.

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

      Sorry, it's already been deleted.

      Ask the questions again and I will respond! .

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please point out what's wrong with my code for 2D? 125022309 Getting Runtime error on test 3

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

    I prefer a segment tree to a sparse table :v

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

    The iterator j should iterate in log(n). You're iterating it till n, this is trying to access out of bound memory. Thus the error.

»
9 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone please help me debug my solution for div 2 problem D. I am getting WA on test case 5.

Basically what I am doing is implementing binary search on the answer and if I find that lets say answer k is possible then I am searching for answer > k, and if answer k is not possible then I am searching for < k.

WA Solution

If my logic is wrong you are most welcome to correct it :)

UPDATE: Got it friends, there was a little problem in binary search implementation. AC Solution

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

    Can you explain your check function?

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

      So the param that I am passing to the function is the answer that I want to check whether it is possible or not. For this I am forming 2 arrays where array pre will store GCD of all the elements from index i to index j and suf will store GCD of all the elements from index j to i+m-1.

      And if you analyze it you can see that if(__gcd(suf[i], pre[i+m-1])!=1)return true; this piece of code will return true if GCD of m elements starting from i is > 1. If it is true then we can say that our array b has at least one subarray of size m who's GCD>1.

      (The main motive behind forming pre and suf arrays is to find GCD of any subarray of length m in O(1) time)

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

        I think something is wrong with your binary search implementation.

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I can't understand how getting the value of p(k) can help in 1549E? How to expand it? What is polynomial long division? How to get the sum of coefficients of k^x? Also, a implementation with sufficient comment for this type of editorial would be good for Pupil like me.

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

thanks for the editorial

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

Solution for D div2 (B div1) without segment trees, sparse table:

After building the difference array $$$D$$$, for each $$$r$$$ we will maintain a list of uniques gcds that we can get if we start at position $$$r$$$ going backwards, i.e. all the possible values of $$$gcd_{l \dots r}=gcd(D_l, D_{l+1}, \dots, D_r)$$$ for all $$$1 \leq l \leq r$$$. Also for each value $$$g$$$ of this list we will also keep the maximum $$$length$$$ such that $$$gcd_{r-lenght+1 \dots r}=g$$$ so that we can update the answer for the problem. We can simulate all this process with a map.

Key observation: The size of the list at each iteration (that is, the number of unique gcds) is $$$O(\log MX)$$$, where $$$MX$$$ is the maximum value of $$$D_i$$$. That's because $$$gcd_{i \dots r}$$$ is a divisor of $$$gcd_{i + 1 \dots r}$$$ for each $$$1 \leq i < r$$$. So if $$$gcd_{i \dots r}$$$ is different from $$$gcd_{i + 1 \dots r}$$$, then $$$gcd_{i \dots r} \leq gcd_{i + 1 \dots r} / 2$$$.

Based on that, total complexity will be $$$O(n \cdot \log^2 MX)$$$ (the second $$$log$$$ is for the $$$gcd$$$ complexity). But maybe using the analysis of this blog (also cited in the editorial) the complexity can go down to $$$O(n \cdot \log MX + \log^2 MX)$$$ or $$$O(n \cdot \log MX \cdot \log \log MX + \log^2 MX)$$$ if you take into account the map complexity.

Link to my submission

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I have another approach to get around the log factor from segtree / sparse table.

    I used a two pointer approach to find the subarray and represented the elements with a queue that always knows the gcd of contained elements. The technique is better known as a min-queue but same applies for gcd. It can be implemented with linked lists or like I did with two stacks.

    Here is my submission.

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

in problem E,could give the code by way in the solution 2? please,i really want to know,it's so exciting.

»
9 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Here is a solution without the segment tree, just using prefix and suffix array for problem D solution

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

Has anyone solved Div2D with Segment tree?. I am getting TLE with two pointers{ increase right pointer till gcd >1 in the difference array} and take the maximum size of all valid subarrays.

Here is my submission : 126619908

Is there any scope for improvement here?

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

    can you explain your sol thoroughly? because i think two pointer will not work in this i guess.

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

F2:

After I got struggled for hours with why "B is always even", I found "the area of the fence is an integer" in the problem statement.

QwQ.

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

Agnimandur proof for B please

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

int div2 D I used segment tree then used binary search for each index to find the farthest point where gcd is not 1. according to me it should be under the given time limit. 143473490

this is my submission which gave tle but using 2 pointer was under the limit