AkiLotus's blog

Ozon Tech Challenge 2020 Editorial
By AkiLotus, 5 years ago, In English

We apologize for the huge gap from F to G.
In the meantime, you can join the Discord server of AC — a competitive programming forum — here.

1305A - Kuroni and the Gifts

Author: Ari
Development: Ari, dorijanlendvaj
Editorialist: Ari

Tutorial
Solution (Ari, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

1305B - Kuroni and Simple Strings

Author: xuanquang1999 (remixed by antontrygubO_o)
Development: Ari, Kuroni, xuanquang1999
Editorialist: antontrygubO_o

Tutorial
Solution (Ari, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

1305C - Kuroni and Impossible Calculation

Author: antontrygubO_o
Development: antontrygubO_o, dorijanlendvaj, Kuroni, Ari
Editorialist: antontrygubO_o

Tutorial
Solution (antontrygubO_o, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

1305D - Kuroni and the Celebration

Author: AkiLotus
Development: AkiLotus, dorijanlendvaj
Editorialist: Kuroni

Tutorial
Solution (Akikaze, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

1305E - Kuroni and the Score Distribution

Author: antontrygubO_o
Development: xuanquang1999
Editorialist: antontrygubO_o

Tutorial
Solution (xuanquang1999, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

1305F - Kuroni and the Punishment

Author: Kuroni
Development: Ari, 265918, Kuroni, dorijanlendvaj, xuanquang1999
Editorialist: Ari

Tutorial
Solution (Kuroni, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, PyPy 3)

1305G - Kuroni and Antihype

Author: antontrygubO_o
Development: antontrygubO_o, Kuroni
Editorialist: antontrygubO_o

Tutorial
Solution (Approach #1) (kefaa2, C++)
Solution (Approach #2) (Kuroni, C++)
Solution (Approach #2) (pajenegod, PyPy2)

1305H - Kuroni the Private Tutor

Author: zscoder
Development: zscoder, ngfam, Kuroni, antontrygubO_o
Editorialist: zscoder

Tutorial
Solution (zscoder, C++)
  • Vote: I like it
  • +155
  • Vote: I do not like it

Comments Comments (117)
| Write comment?
»
5 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Wow! Thanks for very fast editorial and nice tasks!

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

I tried to do D using centroids, is it good idea?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    No. Tests 6-12 should've stopped you.

    (all of them are that same test but with different labels. Some people still passed with random shuffle; i guess only 7 of such tests weren't enough...)

    Edit: now 50 more were added for upsolving but it's still possible to pass by abusing the fact that codeforces rejudges a solution 1-2 times if it gets TLE. Example(worked on second try, copied from 72346371): 72366491

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

    If the idea is to always query a centroid with a neighbor then we can easily fail the solution with a star tree with the root is one of the "leafs". For every query, you will remove only one vertex.

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

    Yes,I solved D using it.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, here's what I did
    - Find the centroid
    - If it's the only remaining node, it's the answer
    - If it has only one child, you can report the answer in 1 query
    - Otherwise find it's 2 largest children, call them c1 and c2. Query their LCA, if the answer is the centroid, we know the root is not in sub-trees of c1 and c2, so block them and all their children. If the answer is c1 or c2, block all the sub-trees of children of the centroid other than the answer (c1 or c2)

    This way, we are removing at least two nodes per query, so it passes.
    My solution: https://mirror.codeforces.com/contest/1305/submission/72333569

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

      Nice solution! And any node having more than one edge can replace the centroid in your algorithm. (My English is poor TAT)

      → Reply
»
5 years ago, # |
  Vote: I like it +56 Vote: I do not like it

OMG, such a nice contest. F is really nice random task, I'm really love it. Thx Kuroni for it.

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

    non random solution for F: 72347794

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it +30 Vote: I do not like it

    In this problem there is one more solution with random. First of all, we know that the answer $$$\le n$$$. Consider the right answer: $$$a_1 + \Delta_1, a_2 + \Delta_2, \ldots, a_n + \Delta_n$$$, s.t. $$$\sum\limits_{i=1}^{n}|\Delta_i| \le n \Rightarrow$$$ the number of different $$$\Delta$$$ is $$$O(\sqrt{n})$$$. Then the probability of picking two different $$$i, j$$$ with the same $$$\Delta$$$ $$$\left(i \neq j, \Delta_i = \Delta_j\right)$$$ is $$$\Omega(\sqrt{n})$$$. Consider such $$$i, j$$$. We know that $$$gcd(a_i + \Delta_i, a_j + \Delta_j) = gcd(a_i + \Delta_i, (a_i + \Delta_i) - (a_j + \Delta_j)) = gcd(a_i + \Delta_i, a_i - a_j) = g > 1$$$ then $$$g$$$ is one of divisors of $$$(a_i - a_j)$$$. Algorithm: iterate the following thing $$$C\sqrt{n}$$$ times: pick two different random $$$i, j$$$, factorize the value $$$(a_i - a_j)$$$ and try all primes in factorization to update the answer (this part is the same as the authors solution). Thanks to dorijanlendvaj for finding corner case. There is situation when the optimal solution has the following form: $$$\Delta_i = \Delta_j \Rightarrow a_i = a_j$$$, but then the number of different $$$a_i$$$ is less than or equal to the number of different $$$\Delta$$$, so $$$O(\sqrt{n})$$$, also we know that there is such $$$i$$$ that $$$\Delta_i = 0$$$, in that case we can check all of the $$$a_i$$$'s. So, total time $$$O(\sqrt{n}(n + FACTORIZE)), FACTORIZE = O(\sqrt[4]{MAXX})$$$ with Pollard.

    Code

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

      Why do we consider only primes?

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

        Because

        $$$(a_i + \Delta_i)$$$ divisible by $$$ pq \Rightarrow (a_i + \Delta_i)$$$ divisible by $$$p$$$,

        $$$p, q$$$ are different primes.

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

          But how can I prove that $$$p$$$ need less operations than $$$pq$$$

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

            If you can make some a_i to be divisible by $$$pq$$$ using C operations then you can using the same $$$C$$$ operations make $$$a_i$$$ to be divisible by $$$p$$$)

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

Can someone explain C more efficiently?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 6   Vote: I like it +18 Vote: I do not like it

    Because of modular substraction porperty and modular multiplication property we can state that

    (a - b) % m is equivalent to ((a % m) - (b % m)) % m
(a * b) % m is equivalent to ((a % m) * (b % m)) % m

    We can consider (ai — aj) % m to be ((ai%m) — (aj%m)) % m. So we can convert all elements of the array from a1, a2, a3, .... , an to a1%m, a2%m, a3%m, .... , an%m. Which means there can be atmost m different values in array. If the number of elements n is greater than m, then there must be some value which is repeated more than once (pigeon hole principal). So there will be some pair (ai, aj) where both elements are the same, hence absolute difference of that pair will be 0. Resulting in a product 0.

    Lets's consider n = 4 and m = 3.

    4 3
1 3 4 5

    We can look at this array like:

    1 0 1 2

    Here we have a pair (1, 1) whose absolute difference is 0. No matter what the 4 elements are, there will always be atleast one such pair.

    If n < m, then we can just check all pairs (as m is small enough, 1≤m≤1000) and compute the product.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      But here (a*b)%m can be interpreted as ( |ai — bj| * |ax — by| ) % m, where ai, ax, bj, by are elements of the array. So thinking about a1%m, a2%m ... and coming to solution does not seem to be intuitive.

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

      wow thank you !! such a good explanation.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    in the first case it is very easy to solve problem like this:

    int sum = 1;
for (int i = 1; i <= n; ++i)
{
    for (int j = i + 1; j <= n; ++j)
    {
        sum *= abs(a[i] - a[j]);
        sum %= m;
    }
}

    in the second one we have that remainders under division by m are : 0, 1 ... m. So, if the number of elements is bigger than m, we will have repetetive remainders under division by m. You also can read about Dirichlet's principle here : https://en.wikipedia.org/wiki/Dirichlet%27s_principle

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

      What's the problem in having repetitive remainders? How can one conclude from that, the asked summation result will be divisible by m due to this fact?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        two numbers have the same remainder a[i],a[j] .

        (a[i]%m=a[j]%m) then (a[i]-a[j])%m=0.

        and it's not sum, it's multiply then the answer is always 0.

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

          But in this problem we were concerned about the absolute differences of the elements of the array, not the values itself. I can understand that (|a1-a2|*|a1-a3|*…)%m = (|a1-a2|%m)*(|a1-a3|%m)… but the problem is according to the solution |a1-a2| % m = |a1%m-a2%m| (I don't know if it is true or not). If it is true then I can start thinking about what happens when a1%m, a2%m … has repetitive reminder or not. Because then clearly two element having same remainder gives 0, and 1 0 means the whole multiple is 0. So given solutions are about what happens ai%m = aj%m for some i,j. But my confusion is how do you even get there from the given problem statement?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +2 Vote: I do not like it

            |ai-aj|%m!=|(ai%m)-(aj%m)|

            suppose a=(4 9) and m=7

            |4-9|%7=5 , while |(4%7)-(9%7)|=2

            what I said is (ai%m)=(aj%m) so |ai-aj|=k*m (k>=0) then |ai-aj|%m=0

            when you see (m<=1000) so you can brute force for n<=m to take all |ai-aj| for all i,j (i!=j) O(n^2).

            otherwise (n>m) in worst case the first m elements have difference remainder {0,1,2,..,m-1} and the next element has a remainder is already exist so take these two elements that have the same remainder, the absolute difference is multiply of m then the remainder is 0.

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

              Ok I see, ai % m = aj % m means ai and aj are congruent. Very nicely explained , thanks.

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

              In this problem it is not written that all the elements are different, the correct solution is based on this fact. Explain the error in my reasoning. Thanks.

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

    if(n > m) , it always exists a pair(i,j) (i < j) such that ai and aj have same modular with m.If(n <= m) you can find the solution in O(m^2)

    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there a way to solve C in $$$O(n)$$$?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    You can use segment tree to solve the problem in O(NlogN)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      How? I don't see how to do range add update and range product query.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Afaik there is a solution in $$$O(n \log^{2} n)$$$ solution here.

    → Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

C's editorial is basically the greatest plot twist for me in Competitive Programming till date

→ Reply
»
5 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Problem C is literally the most genious thing I've seen in my entire life. Dont even regret about my -120

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

    One more like this.

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

      It's not like this, and the only common link between them is perhaps taking modulo with m. But the intentions of modulo are very different. But thank you for acquainting me with such a beautiful and educational problem. I think I gained some IQ points solving "Modulo Sum" :)

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

    Pigeonhole principle is very useful and very nice technique.

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

Nice ;)

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

Nice problem A code:)

→ Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

All model solutions are now available.
I'll try implementing Java8/Py3 variants of G and H soon, but not before having a sleep first. ;)

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

    I see the editorial is still missing a Python solution on G, so here is a PyPy2 solution of G 72758499 similar to the 2nd editorial solution, but using a DSU with $$$O(1)$$$ lookup time and amortized $$$O(\text{log} n)$$$ merge. My time complexity is therefore $$$O(3^m + n \, \text{log} n)$$$ with $$$m = 18$$$.

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

      Finally understanding things a bit better (I was a bit oblivious on G+H those days and simply maintained the tutorials of those through mechanical conventions), so only till now I updated the blog with your Python solution.

      Thank you for the help, and my apologies for this severe necroposting.

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

Damn, author's solution to D is so elegant! My approach was to query about any edge that is not in the current graph, then remove all the vertices up to the lowest common ancestor, and if the LCA is on this edge — remove everyone on the path apart from the LCA itself. I got a TL for it:)

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

I think it's been a while since there was a contest with Boruvka. F is a great random problem too. Thanks everyone for making such a great problemset and excellent contest ^^.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

How to hack 72367869? I only managed to hack looping until $$$n$$$ instead of $$$100$$$ with a stress tester with $$$n=5$$$($$$n \leq 4$$$ didn't find any countercases to looping until $$$n$$$); I made a test which breaks that with $$$n=6$$$ test $$$100$$$ of test $$$2$$$, but i couldn't find any pattern from that test which extends well to larger $$$n$$$.

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

Probably B and C could have been swaped

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

In problem F, could someone elaborate more on how we calculated the probability of the solution being optimal if we pick a random x and try the prime divisors of x, x+1, and x-1?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    • The answer to the problem is at most n

    • There can't be more than n/2 elements which are affected by >1 operations (answer would be more than n/2 * 2 == n) ==>

    • ==> There can't be less than n/2 elements affected by 1 or less operations

    • n/2 is the half of n so the probability of [picking an element which needs to be affected by 0 or 1 operation] equals to 1/2

    • So we pick a random element x and we're 50% sure it will stay x or become x±1

    • If we repeat it k times, it's (1/2)^k probability. So the question is just about what's the value of k (authors recommend k = 20)

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

      Got it. Thank you.

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

      Isn't it at most n assuming d=2? ,I don't get it. Can you please explain it more precisely?

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

        With d==2 the answer is always not bigger than n (the worst case is when we have all the numbers odd so we have to add ±1 to each of them).

        If d>2 (let's say d==D1) and for d==D1 the optimal answer is bigger than n. Then it doesn't make sense to choose d==D1, cuz for d==2 it always gives us smaller answer.

        → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

When you realise why the range of $$$m$$$ is only $$$1<=m<=1000$$$: why didn't the author just use $$$m==10**9+7$$$

"You sneaky bas#ard" :P

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    I saw that $$$M\le 1000$$$ and assumed that $$$N\cdot M$$$ was intended ...

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      What's $$$N.M$$$

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

      Mind explaining your solution?

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

      I wrote the same solution as you, But I got TLE on 10th pretests.

      It looks very strange because in your solution there are N * M modulo operations. while I have only N modulo operations.

      72379501

      Even adding #pragma optimizations didn't help.

      What is the magic?

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

There's a mistake in the editorial in problem B. It should be a(i+1) <= a(k) < b(l) <= b(q-i)

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +43 Vote: I do not like it

I have a possibly correct solution to problem F, it looks like brute force but it passed system test.

It runs as follows:

  • Firstly, find out every prime number less than or equal to $$$10^6$$$.
  • Then, arbitrary choose an $$$a_i$$$, factorize all the numbers between $$$[a_i-n,a_i+n]$$$.(Because after performing all the operations, $$$a_i$$$ will be in this range)
  • In the end, use brute force to check all the prime numbers. The only thing we need to do is to break in time:
	ll ans=n;
	for(int i=1;i<=num;i++)
	{
		ll p=prime[i];
		ll res=0;
		for(int j=1;j<=n;j++)
		{
			res+=a[j]<p?p-a[j]:min(a[j]%p,p-a[j]%p);
			if(res>ans)break;// break in time
		}
		ans=min(ans,res);
	}
	printf("%lld\n",ans);

Such a solution could pass system test, but I don't know whether it's correct or not.

Could anyone prove its complexity, or hack my solution?

72344820

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

    My solution is the same to you.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    It seems really brute...but it works...

    Your "break in time" guarantees the low complexity,cause it's impossible to construct a simple that for lots of a[i],you have to sum many "min(a[j]%p,p-a[j]%p)" before you break.

    For example:

    when "min(a[j]%p,p-a[j]%p) == i" , "a[j]+i" or "a[j]-i" should be multiples of "p".

    So the numbers of possible "p" for every "i" is "log(a[j]+-i)" , equal to the numbers of factors of "a[j]+i" or "a[j]-i" , and you can't find a lot of "p" for a small "i".

    The upper boundary of complexity in total maybe "sigma(n/i * log(max a[j]))" , that is "O(nlnn*log(max a[j]))".

    [sorry for my poor English and ignorance of markdown QAQ]

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

      You are so strong!!! And your English is not poor!!! %%%

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Even better, if you pick a random index $$$i$$$ and check prime factors of numbers between $$$[a_i - 2, a_i + 2]$$$, we do get AC.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Maybe I can hack you?

      data:

      5
169999847(=17*9999991)
169999847
169999847
169999847
300469729580(=(17+2*3*5*7*11*13)*9999991+3)

      The answer is to choose $$$9999991$$$, but if you pick $$$5$$$ you will miss the correct answer.

      In this way there is a possibility of $$$0.2$$$ that your solution get the wrong answer.

      Update: hacked successfully.72392250

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

        Is it still hackable with big n?

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

          Yes. We can use $$$4x\ 16999847$$$ and $$$x\ 300469729580$$$.

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

    I did that but instead of res > ans, I compressed repeated elements and did res >= n for the breaking condition and it passed in 200ms.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

Problem D is it given that given tree is a binary tree ?? and what exactly is the definition of root of a tree ?? i'm not getting it if it's not binary then what is root for 7 vertex 1 2 1 3 1 4 1 5 1 6 1 7

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    In graphs, a tree is an undirected connected graph without any loop. But a rooted tree is a tree with one vertex defined as the root. This is the tree you may be familiar with. Converting a tree to rooted is to consider the distance between each vertex and the root, this will become the depth of each vertex. In Problem D, the root was hidden and you are to find it out. On the tree you cited above, when we ask the LCA (lowest common ancestor) for vertex 2 and 3, it will be vertex 2 when the root is 2, and vertex 1 when the root is 7.

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

Can someone clearly explain why in problem F we should take prime divisors of x, x-1 and x+1?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It was proven that in optimal answer there are a lot of numbers, which should be changed on at most one. So after changes, a particular number x will be either $$$x$$$-1, or $$$x$$$, or $$$x+1$$$. If the gcd of all number is not one, all number should have some common divisor, particularly, this one number should also be divisible by this number. We could do now bruteforce over all divisors of $$$x$$$-1, $$$x$$$ and $$$x+1$$$. But it is too slow, so lets consider only primes. It works because if we got $$$s$$$ steps for having gcd divisible by $$$z$$$, then we can do still those $$$s$$$ steps(or maybe less), making gcd divisible by some prime of $$$z$$$.

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In problem B, in the prove of claim, why we must have k>i and l<q−i+1? Why can't k < i?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Could someone pls explain, in D task, why is number of queries less than n/2?

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

For D,

I found the diameter of the graph and queried for the vertices that formed the diameter.

Then I removed those 2(or 1) edges from the lca vertex that led to the diameter vertex.

I did this until the both the edges of the diameter were the same and outputted that vertex.

Where can this approach fail?

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

    I had an idea that sounds like exactly the same one. In my opinion, there are no reasons why it should fail.

    Unfortunately, my practice implementation (72378820) got TLE and it is somewhat messy+inefficient, especially its finding-a-diameter part... And also I lost motivation about making it work (because now I know a simpler way of solving the problem D).

    The idea of taking any two leaves is really awesome, significantly simpler in implementation.

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

      Yup, there is nothing wrong with the idea indeed. I got AC.

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    The idea is almost the same as in the editorial (since first and last nodes of the diameter are obviously both leaves) but in your submission 72400841 you have bug in detecting if node belongs to a path from lca to one of the outputed nodes.

    Try test 

    5
4 1
3 1
2 1
1 5

    Where the root is 4 (vertex that isn't 1 and wasn't outputed by your code in first query).

    Basically the solution is making always only one query and think that the answer is the given lca. It's pretty surprising it has made it to the 13 test.

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

      Thanks for pointing that out.

      I forgot to mark the LCA as visited before identifying which children contained the vertices of the diameter and thus the dfs moved back into the lca and messed up the code.

      I still didn't get an AC, TLE at #27 so I guess I'll implement the editorial's approach.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 4   Vote: I like it -8 Vote: I do not like it

        Well, you're getting TLE brecause of calling (redundant) reset() after each rdfs call which makes your solution $$$O(N^2)$$$ (probably too slow with python and huge I/O including many flushes).

        UPD: Idk why I got downvotes for this, 72563170 sanvi_kiit's code without the reset calls gets AC

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      NVM I finally got it. Sorry for ping

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

You said that we can fix any string with 0 or 1 operation for problem B.This is an example that you can't fix it with 0 or 1 operations : (((()))())

→ Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Hi! I am stuck at 13th tc of D. I am not sure what's wrong with my logic. Can anyone help me with this?

72420055

Thanks in advance!

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sorry If the comment seemed casual,I am not sure how to debug it... but I'm really stuck at this and 13th tc is quite big so not able to find the mistake.

    My logic:
    Find two leaf nodes (say x , y) and find their lca.
    Now two cases :
    - if x == lca or y == lca we have our answer. break and print ans
    - else delete all the nodes in both subtrees that connect to lca of x and y(done in solve func) and set y = lca and use another leaf node for x

    Continue this until no leaf node is left and we will have our ans.

    My logic is somewhat the same as editorial hence I don't know what's wrong.

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

    The only place where you do leaves.insert() is before your main loop.
    But when you erase nodes from a tree, some non-leaf nodes become leaves.

    I think you should probably add them to 'leaves' somewhere inside the loop.

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

      Apart from LCA I don't think any node is getting set as leaf node after deletion, because the subtrees are attached to LCA at end and not affecting any other node.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I think I found the mistake , it's when I am taking LCA in the query , I should take LCA only when it's a leaf otherwise the other leaf node has a chance of being in it's subtree

      Edit : Got Ac 72535927

      Thanks for Help!

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

Thanks for the contest and nice editorial <3

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

Can anyone explain the solution of problem D 1305D - Kuroni and the Celebration ? Editorial is not clear to me.

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

    What exact part did you feel unclear?

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

      I have found the answer of my question... Now it is clear to me. Thank you AkiLotus for your response :)

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

Please help me find mistake in my code (D question): Submission Link . Thanks in advance :)

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

can anyone let me know the meaning of the verdict "cost limit exceed" in problem d

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    You used too many queries (exceeded the $$$\lfloor \frac{n}{2} \rfloor$$$ limit).

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

In D, why int last variable is used in function void purge() ??

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

    "last" here serves as the previously traversing node, to avoid repetitive recursive call.

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

G's solution can be proved constructively and I think it's a bit more intuitive that way. The key idea is that if we root the tree of invitations at the $$${n+1}$$$-th node, each non-root person is invited by their parent. It provides a bijection between trees and valid sequences of invitations.

When a person joins, the gain is equal to the parent edge weight minus the joining person's age. Since each person joins once, it suffices to maximize the weights of the edges in the tree.

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

can someone tell me how to solve E.or atleast that(i-1)/2 case.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Adding a number i will increase the count of triplets by ( i -1)/2. Suppose we have elements 1 2 .. adding 3 will increase the count by (3-1)/2=1 because 1+2=3. Now we have 1 2 3, adding 4 to the elements increases the count by (4-1)/2=1 because we have 1+3=4. Generally we take the current most left and the most right elements and add them and we get the new added element and then we take the next most left and the next most right elements and repeat the process. As if we are using two pointers starting from the first index and last index and every time we increment the left pointer and decrement the right pointer, then the sum of the 2 current elements gives us i. having 1 2 3 4 5 6 and then adding 7 , we have 1+6 , 2+5 ,and 3+4 = 3 triplets = (7-1)/2. That's the number of current elements divided by 2 which is the number of elements ( assuming all elements to be 1 2 3 ... i-2 i-1 ) before adding the new element which is i, so the count increases by ( i -1) "the current number of elements before adding i to them" / 2 , because the sum of every two elements gives us i. If you still don't get it or want me to further explain the complete solution, feel free to ask.

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

https://mirror.codeforces.com/contest/1305/submission/72570404 this submission of mine os showing wrong ans on t20. the correct answer on B t20 says only one bracket needs to be removed . someone please explain

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

    You're misreading between your output and jury's answer. Correct answer said "0".

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

Can someone please explain the proof of the $$$F$$$ ? Why the probability is $$$1/2^m$$$ if we pick only m elements and factorise them ?

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

Can someone explain what the purge function is doing in the solution of DIV2 D and why we are doing it ? Thanks in advance !

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    After asking a query $$$(u, v)$$$ and receiving the LCA $$$w$$$, the purge functions went in and delete every node (and edge) in the path from $$$u$$$ and $$$v$$$ towards $$$w$$$. If there's any nodes being separated after that, they'll be purged along as well.

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

      Thank you for your reply !. Can you elaborate "If there's any nodes being separated after that" a little please ?

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

Can anyone please explain E?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please post the solution for E? It doesn't load for me.

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

I liked problem F a lot. My approach differs from the editorial's. The main idea is that we can fix a prime $$$p$$$ and then make update in the array to have a gcd which is divisible by $$$p$$$. To do this, a couple of observations:

(1) We know that if we let $$$p = 2$$$, we can get the array to be divisible by $$$2$$$ in at most $$$N$$$ operations. So the expected value of the number of updates per element should be $$$\le 1$$$.

(2) If each element is pretty close to being divisible by that special prime $$$p$$$, we can randomly chose an element, look in the neighborhood of that element, and then decide which primes are feasible. That is, take $$$10$$$ random elements. Let's look at them one by one. Say, the first element is $$$x$$$; then the special prime $$$p$$$ is likely divisible by $$$x-3, x - 2, x - 1, x, x + 1, x - 2,$$$ or $$$x + 3$$$. So we can prime factorize $$$x - 3...x + 3$$$ to look for that prime $$$p$$$.

If this is confusing, see 141358017.

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

In problem 1305G, please note that given by Tarjan, the time complexity of DSU with $$$n$$$ vertices and $$$m$$$ queries is $$$O(m\alpha(m+n,n))$$$, and by the definition of Inverse Ackermann Function, $$$\alpha(m+n,n)\le 1$$$ when $$$m>\log n$$$，thus the tighter time complexity of Approach 2 is $$$O(3^k+2^k\cdot k)$$$ where $$$k$$$ is 18, or simply $$$O(3^k)$$$.

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

Oh my god!! I haven't seen C type of question never before!!It totally changed my view!!

→ Reply