Agnimandur's blog

By Agnimandur, 3 years ago, In English

All the division 2 problems were created by Agnimandur. 1548E - Грегор и два маляра 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 - Грегор и криптография

Hint 1
Solution

1549B - Грегор и игра в пешки

Solution 1

Hint 1
Hint 2
Solution

Solution 2

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1549C - Паутина лжи

Hint 1
Hint 2
Solution

1549D - У чисел есть друзья

Hint 1
Hint 2
Hint 3
Solution

1549E - Три поросенка

Solution 1

Hint 1
Hint 2
Hint 3
Solution

Solution 2

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1549F1 - Грегор и нечетные коровы (простая версия)

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1549F2 - Грегор и нечетные коровы (сложная версия)

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

1548E - Грегор и два маляра

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

| Write comment?
»
3 years 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.

  • »
    »
    3 years 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 - У чисел есть друзья without segment tree and sparse table.

    • »
      »
      »
      3 years 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! .

»
3 years 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

  • »
    »
    3 years 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.

»
3 years 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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your check function?

    • »
      »
      »
      3 years 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)

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think something is wrong with your binary search implementation.

»
3 years 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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the editorial

»
3 years 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

  • »
    »
    3 years 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.

»
3 years 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

»
3 years 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?

  • »
    »
    3 years 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. using segment tree adds logN to the complexity (O(NlogNlogA)).because of that i suggest you to use sparse table, it makes the complexity O(NlogN+NlogA).
    2. when using segment tree for basic things (i.e. only query or point update) i suggest you to make it iterative. even if its not better in complexity, it is 2-3x faster than recursive
    3. please use pragma in this situations, it can let you cheese problems (like using ordered set)

    other than these tips, i couldnt see any implementation errors (like infinite loops).

    (ik this was 3 years ago, hope you see this)

»
3 years 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.

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

Hello in english

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

Regarding problem D. If i use binary search submission 218897364 it gives TLE. if i use two pointers submission 218907845 it gets Accepted.Can anyone please figure out why ?.

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

There exists a somewhat different solution (albeit with the same time complexity) for D1E if we consider rows as "representatives" instead of cells. It can be implemented in a somewhat simpler manner using dsu and sets: 252411144