When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

diskoteka's blog

By diskoteka, 11 months ago, translation, In English

1822A - TubeTube Feed

Idea: diskoteka, prepared: Vladosiya

Tutorial
Solution
Rate the problem

1822B - Karina and Array

Idea: playerr17, prepared: playerr17

Tutorial
Solution
Rate the problem

1822C - Bun Lover

Idea: diskoteka, prepared: diskoteka

Tutorial
Solution
Rate the problem

1822D - Super-Permutation

Idea: isosto, pavlekn, prepared: diskoteka

Tutorial
Solution
Rate the problem

1822E - Making Anti-Palindromes

Idea: pavlekn, prepared: pavlekn

Tutorial
Solution
Rate the problem

1822F - Gardening Friends

Idea: playerr17, prepared: playerr17

Tutorial
Solution
Rate the problem

1822G1 - Magic Triples (Easy Version)

Idea: pavlekn, prepared: pavlekn

Tutorial
Solution
Rate the problem

1822G2 - Magic Triples (Hard Version)

Idea: pavlekn, prepared: pavlekn

Tutorial
Solution
Rate the problem
  • Vote: I like it
  • +51
  • Vote: I do not like it

»
11 months ago, # |
Rev. 3   Vote: I like it -7 Vote: I do not like it

G2 can be solved by going threw array from left to right and for every i get all divisors of a[i] and for perfect square divisors X increase answer by cnt[a[i] / X] * cnt[a[i] / sqrt(X)]. We just need to get divisors using prime factorization which we can get by going only threw prime numbers [1, sqrt(10^9)] (only ~3000).

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

    There are ~3000 primes in [1, 10^4.5] right, not 65?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Why are you downvoting? I just wrote my approach on that problem :)

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

    Thanks for sharing this approach. I looked at your submission history, read the relevant submission and the whole Sieve & prime factorization finally clicked for me.

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

Alternatively for g2, we can prime factorize the number to look for candidates for k. Apparently prime factorization can be done with pollard(although I didn’t do this) and the number of perfect squares can be found in logM (someone needs to prove this I suck at math). Essentially g2 can be solved in o(n*M^1/4).

For the log constant on m, you can notice that the number of perfect squares is the number of each p divided by 2 and choosing how much of each p exists. The number of terms is maximum 6 or approximately 2^6 operations. If someone has a better analysis of this it would be greatly appreciated.

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

    I was thinking we can do O(n*M^(1/6)) because we are only considering divisors of the SQRT(M), which is ~(M^(1/2))^(1/3) because the number of divisors of a number M doesn't exceed O(M^(1/3))

    Ref: https://codeforces.com/blog/entry/13585?#comment-185136

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

      How would you find factors with sqrt(M) I’m curious.

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

        Imagine we are brute-forcing the largest value a[k], consider the divisors of a[k], we only need to consider divisors which are perfect squares because our value b will be the square root of the divisor. I think we can show the number of divisors which are perfect squares of some value is at most the sixth root of the value.

        Does this answer your question?

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

          The larger number could be a perfect square and not the smaller number? If you have implementation that would help.

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

            Sure, here is my implementation: https://codeforces.com/contest/1822/submission/203467962

            Hopefully this clears things up.

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

              It does seem to be the right time complexity but it doesn’t have noticeably better performance compared with my previous algorithm. This may be due to a high constant factor.

              • »
                »
                »
                »
                »
                »
                »
                »
                11 months ago, # ^ |
                  Vote: I like it -11 Vote: I do not like it

                Yeah I bet that's related to the implementation.

»
11 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Also we can solve G2 with pointers and achieve better complexity without unordered map.

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

Editorial for C missing last few characters

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

    Zooming out (from 125% to 100%) worked for me. It looks like overflowing content (on zooming in) are now made hidden instead of letting them go out of the box.

»
11 months ago, # |
  Vote: I like it -14 Vote: I do not like it

F can also be solved using rerooting dp.

Here is my submission.

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

In problem C how we had known the length of the polylines links?

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

Nice, Thanks

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

Can someone hack this solution

It should get a TLE verdict.

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

I don't know why my solution was not TLE. Could you help me? This is my g2 solution

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

    Thanks for sharing this wonderful trick for solving this problem.
    Here's my implementation to do the same.

    I believe the Time Complexity for this approach would be around O(N*log^2(N)). Hence it passed all test cases.
    Here's what I have observed for calculating the TC

    Any other suggestions, ideas and improvements are welcome :)

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

nice div3

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

Good editorial.

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

Thank you so much! this is really helpful

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

Can someone explain to me problem D? I still do not get it. Thank you

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

Can someone pls tell why I am getting TLE at test 16 For Problem G1 even though my idea is same as the official editorial. Link of submission: (https://codeforces.com/contest/1822/submission/203514583)

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

Can u give a test cases where this solution did not pass link of my solution https://pastebin.ubuntu.com/p/kVh39TVsk5/

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Input
    Expected output
    Your output
    Explanation
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How does one solve D? Is it just finding the pattern? I could only figure out that there is no answer for odd (>1) and n would be the first number.

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

    the solution is kind of hidden in the last sample. one can construct the array on other even numbers and see if it works.

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

fine good contest

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

I think $$$a=[n, 1, n−2, 3, n−4, 5, …, n−1, 2]$$$ is wrong.

Isn't it $$$a=[n, 1, n−2, 3, n−4, 5, …, 2, n-1]$$$.

That's how your code is written.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    can you prove the formular?

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

      I'm a little late.

      If

      $$$a = [n, 1, n - 2, 3, n - 4, 5,\dots, 2, n - 1]$$$

      ,

      $$$b$$$

      will be

      $$$b = [0, 1, n - 1, 2, n - 2,3, n - 3, 4, \dots, \frac{n}{2}]$$$

      .

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

      What's your problem?

      Thanks.

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

Does 10 ^ 8 complexity passes in CF ?? asking becouse of editorial of G1

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

    depends on time limit. Here we have 4s. it should pass.

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

can anybody tell me what is wrong with my solution ?
a test case where my code fails will also be useful

https://codeforces.com/contest/1822/submission/203552879

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

Alternative Solution for Problem F

Intuition and Solution

-> Code

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

    thank you so much for the solution, it was way more simpler to understand

    however i dont really get why we dont have to also DFS from the other end point of the diameter (which can be found in the process of DFS from A) but only from A to find the answer?

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Let's dive in and Think of it.
»
11 months ago, # |
  Vote: I like it +19 Vote: I do not like it

how to tell that the time complexity for G2 passes ? O(M^(1/3)nlogn) seems bigger than 10^8 for M = 10^9, n = 2*10^5

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

Where can I have a mistake?:

Problem F — Wrong answer on test 36.

But it works:

Problem F — Accepted.

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

    you put assign(n, 0), instead of assign(26, 0)

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

I should definitely stop complicating problems. I used Binary Lifting to solve F.

If anybody wants to check the stupid submission: 203630946.

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

Yet another solution for G2 using sqrt decomposition(excuse my English):

First,for each prime number in (1e9^(1/4),1e9^(1/2)],simply iterate over all multiples of its square.The time complexity is at most O(M^(1/2)lnM^(1/2)),and it is clear that each number <=1e9 can have at most one of these square numbers as its factor because (1e9^(1/4))^2*(1e9^(1/4))^2=1e9,so we can precalculate it using std::map in O(M^(1/2)lnM^(1/2)logM^(1/2)).

Next,for each number,iterate over all prime numbers in [2,1e9^(1/4)].It doesn't takes long since there are less than 100 primes in [2,1e9^(1/4)].Then check the map for its factor in (1e9^(1/4),1e9^(1/2)] (if exist) in O(logM).At last,iterate over all its factors.Since 2^2*3^2*5^2*7^2*11^2*13^2~=9e8,there are at most 2^6=64 factors to iterate over for a single number.The total time complexity is O(M^(1/2)log^2(M^(1/2))+(100+logM+64)n). Solution:203320262

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

For F you can dfs 3 times to find the maximum distance to the leaves.

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

very good competition. I enjoyed it.

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

Can anyone explain E.I still don't get it.how is ans max(m,ceil(k/2))??

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

I don't understand the tutorial of G1. Can someone explay it in newbie language? ∑ni=1(cnt[ai]−1)⋅(cnt[ai]−2) I don't know exactly what are we doing here

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    sum = 0;
    for (i = 1; i <= n; i += 1) {
      sum += (cnt[a[i]]-1) * (cnt[a[i]]-2);
    }
    
    • »
      »
      »
      11 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      What I don't get is the part inside the loop. Cnt[a[i]-1] * (cnt[a[i]] — 2); code is quite clear. I want to know what exactly is this .

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

        We need to choose 3 numbers $$$x$$$, $$$y$$$, $$$z$$$ such that $$$x * b = y$$$ and $$$y * b = z$$$.

        When $$$b = 1$$$, $$$x = y = z$$$. In this case, we need to select 3 of the same number.

        Let's say the count of $$$x$$$ is $$$cnt_x$$$. In how many ways can you select 3 different $$$x$$$ from $$$cnt_x$$$?

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

For E there is an observation that if we store freq map for pair for si==sn-i-1 suppose 3 pair with freq as a=3 b=3 and c=2 then the optimal way to make swaps are with 2 swaps we can reduce 4 pairs aa aa bb cc with 2 swaps we will get (a,b) ,(b,a), (a,b),(c,a) this is where i got WA on test case 13

here is my submission using priority queue :- 203984993

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

The key to question E is to figure out that if m*2>=k, the answer is m/2+m%2,isn't it? In other words,there must exist some way to match every two pairs that are not the same letter when m*2>=k. I probably know how to prove it through mathematical induction, it may seem unnecessary though.

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

Problem 'C' can also be solved using a simple equation → ans=26+((10+n-4)*(n-4)) Here's the code

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

In problem F cant both down1[p] and down2[p] lie in the subtree of v? playerr17

also please explain what is int64_t ans = -1'000'000'000'000'000'002;

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

why is this not passing? code is in segfault function

https://codeforces.com/contest/1822/submission/205472462

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

UPD: solved it.

The tutorial for G2 says the time complexity $$$O(n \cdot M^{\frac{1}{3}} \cdot \text{log } n)$$$ with the use of std::map will pass. Why does my solution TLEs then?

https://codeforces.com/contest/1822/submission/205547154

pavlekn what do you mean? I don't understand.

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

deleted comment

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

Another solution for G2, I believe is much simpler but is somehow getting tle. Can someone verify this?

*Time Complexity: O(n*pow(M,1/3)) *Idea:

  • Array a has distinct sorted numbers and hash map f stores the frequency of these.
  • Also, a[i]*b==a[j] and a[j]*b==a[k]
  • thus a[i]*b*b==a[k]
  • From the above equation, b should lie in range [1 , pow(a[k]/a[j],1/2)] or [1,pow(M,1/2)] here is M is max(a).
  • Now, for i>=pow(M,1/3) we have b in range [1,sqrt(M/pow(M,1/3))] = [1,sqrt(pow(M,2/3))] = [1,pow(M,1/3)] .
  • so we loop through this entire range of b if i>1000 ( as elements are distinct and sorted i>1000 means a[i]>1000 ). Hence, O(n*pow(M,1/3))
  • Also for i<pow(M,1/3) we can iterate through all j>i => O(n*pow(M,1/3))

so we have ensured that time complexity is O(n*pow(M,1/3)) submission

pavlekn Help Orz

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

I was solving D for practice and it seems like a question which solely depends on you somehow finding the pattern and there's not much reasoning leading upto it other than figuring out that the first element will be n. So you basically don't know what you want. Not really happy with the ad-hoc nature of this question,

Also there's a mistake in a=[n, 1, n−2, 3, n−4, 5, …, n−1, 2], it should rather be a=[n, 1, n−2, 3, n−4, 5, … 2,n−1].

Okay, on further exploration I somewhat accept that this question can be solved reaching the pattern in structured way and figure out this (and few other) pattern by trying to cover all mod values, beginning from 0 and n/2 being already covered. So, thinking of mod of n in a cycle from 0 to n-1 to 0,we can then think of a pattern which has sums reaching all values and this works out for various patterns. Obviously, we can't try to cover the mod values one by one so we can think of covering them in an alternate way, there are multiple ways of alternating, one can be trying to cover numbers from n/2+1 to n in one alteration and 1 to n/2-1 in the other. Other patterns include covering 1 to n/2 and n-1 to n/2 in the other direction. It all makes sense once you start seeing it from a pattern hit-trial with all the necessary equations. Another alternating pattern which you can try is covering one odd and one even number eventually collapsing to n/2.

On even further thought, maybe not so many patterns do actually fit in really which makes me take back my original stance. ;-;

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

    I understand there isn't a rigorous way to solve this problem as it is constructive, but I still believe that the problem was spoiled by the last sample test case, making it quite easy. One can easily arrive at the fact that odd n > 1 don't work and that n must always be in front. The last sample is 6 5 2 3 4 1. We can actually generalize a whole algorithm from here in a rigorous way by basic observations: Array: 6 5 2 3 4 1 Residues:0, 5, 1, 4, 2 One can notice that after every two residues the numbers decrease. Why? Well in the array we added blocks of n — 1. So n — 1, 2n — 2, 3n — 3. Clearly, the residues decrease if reduce this modulo n. So the last sample suggests we should center some construction around decreasing residues every other time. Now, interestingly enough the residues also increase starting from 1. Goes from 1 to 2. The sample again suggests we should do something similar to this. More clearly, the sample gives us the intuition that maybe there is some construction in which we start from n — 1 decrease the residues until we reach the halfway point and start from 1 increase residues in till we reach the halfway point. From, there you can easily prove that putting even numbers and n — 1 — even numbers always work. Say you want residue 1 and you have n — 1 before it, obv you need 2, ...no we know that for the next thing, we will have residue n — 2 (since we chose to decrease like this), well then obviously we need 4 to get this residue to increase from 1 to 2. So in general when we want residue i we know we have residue n — i from before it so we will need 2i. 2i never gets too big where it won't already be reduced mod n. I think this is extremely intuitive, and something you don't need to prove.

    In conclusion, this question boils down to simple problem-solving by generalizing patterns by sample test cases. It would definitely be much harder without them, but since they are there I think the question is fairly straightforward.

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

I'm not sure whether G2 is Good or Bad

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

solved A after the contest

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

Thanks for the great questions and editorial.

In the editorial for problem F, I believe this statement is misleading or perhaps incorrect, at least from what I understand from the code,

Let for vertex v the values down1[v],down2[v] are the two largest distances to the leaves in the subtree of vertex v of the source tree

I think it should be, "Let for vertex v, the values down1[v] and down2[v] are the two largest distances to the leaves following different subtrees of vertex v."

                if (u == parent[v] || u == down[v].first.vertex) continue;
                if (down[u].first.value + 1 > down[v].second.value) {
                    down[v].second.value = down[u].first.value + 1;
                }

Please correct me if I'm wrong or if you agree.

Otherwise, with the current wordings, the two largest distances to the leaves can happen in the same subtree of vertex v and this statement doesn't make much sense

If the leaf farthest from p is in the subtree v , then you will need to take down2[p] , otherwise down1[p]

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

for problem E can someone tell me why my code doesnt work, i am trying to implement editorial solution.

Code

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

Can anyone explain what can we learn from genious problem D?

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

for G1 why does creating the cnt[x] array inside the main function gives TLE while when declared globally gets aceepted

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

For F:

Intuition

my submission: https://codeforces.com/contest/1822/submission/227252588