Akikaze's blog

By Akikaze, 7 months 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: Akikaze
Development: Akikaze, 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++)

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

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

Wow! Thanks for very fast editorial and nice tasks!

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

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

  • »
    »
    7 months 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

  • »
    »
    7 months 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.

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

    Yes,I solved D using it.

  • »
    »
    7 months 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://codeforces.com/contest/1305/submission/72333569

    • »
      »
      »
      7 months 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)

»
7 months 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.

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

    non random solution for F: 72347794

  • »
    »
    7 months 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

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

      Why do we consider only primes?

      • »
        »
        »
        »
        7 months 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.

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

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

          • »
            »
            »
            »
            »
            »
            7 months 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$$$)

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

Can someone explain C more efficiently?

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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.

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

      Amazing explanation man...!! Thanks a lot..

  • »
    »
    7 months 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

    • »
      »
      »
      7 months 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?

      • »
        »
        »
        »
        7 months 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.

        • »
          »
          »
          »
          »
          7 months 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?

          • »
            »
            »
            »
            »
            »
            7 months 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.

            • »
              »
              »
              »
              »
              »
              »
              7 months 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.

            • »
              »
              »
              »
              »
              »
              »
              7 months 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.

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

                You are right, there can be equal numbers in input. But we take into account not numbers from input but their modulo m residues. m <= 1000, so there can be no more than 1000 different residues (according to Dirichlet principle), so if n > m, there must be two numbers which are comparable in modulus m, which is equivalently their diffirence is comparable with 0 in modulus m, and product of all differences by mod m is equal to 0.

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

                yes they are not, but the worst case is when the numbers are different.

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

                If two numbers are same then simply their difference will be 0.

  • »
    »
    7 months 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)

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

    For case1 it's easy but the second case can be proved by pigeonhole principle. Since there are n numbers and each number can have reminder from 0 to m-1. Hence by pigeonhole principle there will be at least one value of remainder (out of 0 — m-1) for which # of numbers having that reminder will be greater than or equal to ceil(n/m) which is greater than 2 for n>m.

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

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

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

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

    • »
      »
      »
      7 months 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.

  • »
    »
    7 months 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.

»
7 months 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

»
7 months 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

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

    One more like this.

    • »
      »
      »
      7 months 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" :)

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

    Pigeonhole principle is very useful and very nice technique.

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

Nice ;)

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

Nice problem A code:)

»
7 months 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. ;)

  • »
    »
    7 months 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$$$.

»
7 months 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:)

»
7 months 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 ^^.

»
7 months 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$$$.

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

Probably B and C could have been swaped

»
7 months 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?

  • »
    »
    7 months 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)

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

      Got it. Thank you.

    • »
      »
      »
      7 months 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?

      • »
        »
        »
        »
        7 months 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.

»
7 months 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

  • »
    »
    7 months 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 ...

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

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

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

      Mind explaining your solution?

    • »
      »
      »
      7 months 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?

»
7 months 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)

»
7 months 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

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

    My solution is the same to you.

  • »
    »
    7 months 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]

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

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

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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

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

        Is it still hackable with big n?

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

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

  • »
    »
    7 months 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.

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

the submission for problem B:72330449

()(((())))()()())))() the data can hack it.

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

    it had been hacked.

    By the way,why some people also can hack somebody after the contest?

»
7 months 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

  • »
    »
    7 months 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.

»
7 months 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?

  • »
    »
    7 months 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$$$.

»
7 months 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?

»
7 months 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?

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

    Also, I'll be grateful if someone suggest another approach to solve it

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      Because after each iteration of algorithm there are only two possible options: 1). You found answer and program terminates; 2). You delete two vertexes in your graph. If you didn't find answer after int(n/2) iterations (where n is initial size of graph), you deleted int(n / 2) * 2 vertexes, and it's equal to all vertexes if n is even (it is impossible, because you always can find answer before all vertexes deleted) or to n — 1 vertexes if n is odd. In this case there's only one not deleted vertex at the end, so it's the answer.

»
7 months 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?

  • »
    »
    7 months 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.

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

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

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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.

      • »
        »
        »
        »
        7 months 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

»
7 months 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 : (((()))())

»
7 months 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!

  • »
    »
    7 months 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.

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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.

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

        Then, the LCA itself becomes a leaf :)

    • »
      »
      »
      7 months 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!

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

Thanks for the contest and nice editorial <3

»
7 months 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.

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

    What exact part did you feel unclear?

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

      If we make our query like this process, doesn't it cross the query limit that is [n/2]? I understand the solution of editorial but don't get the point why query limit is not exceeded?

    • »
      »
      »
      7 months 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 Akikaze for your response :)

»
7 months 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 :)

»
7 months 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

  • »
    »
    7 months 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).

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

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

  • »
    »
    7 months 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.

»
7 months 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.

»
7 months 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.

  • »
    »
    7 months 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.

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

https://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

  • »
    »
    7 months 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".

»
7 months 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 ?

»
7 months 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 !

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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 ?

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

Can anyone please explain E?

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

    Sorry for any grammar mistakes

    Assuming You Understood until (i-1)/2 case by the comment

    https://codeforces.com/blog/entry/74459?#comment-587005

    Let's Say the Number of special triples until now as S (let it be < M). If we add the new number there are two cases

    1. S will still be less than M (in this case we continue to add the new number).

    2. S will be greater than or equal to M.

    In the second case, we need to figure out the number which will only add M-S Special triples.

    If we use two pointers, First Pointer as 2*(M-S)+1 and second pointer as index of the last number added to the list. Every time we increment the left pointer and decrement the right pointer. The sum of the two elements will always give us a single number M-S times. So will use this number as the next number.

    At this point, we achieved the desired balance. I think After this how to handle the rest of the numbers is neatly explained by ending section of this problem editorial.

    My Code

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

For Problem F, I couldn't understand this part.

"When we apply the optimal sequence of operations there are at least n/2 elements which are affected by at most one operation."

A proof would be really helpful.

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

Can anyone please explain problem H in more detail ?

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

https://codeforces.com/contest/1305/submission/84656279 What changes do i need in my code..please explain me