kefaa2's blog

By kefaa2, 2 weeks ago, translation, In English,

Codes have been added!

We've added challenges(mostly not hard) to some tasks. Feel free to share solutions and ask any questions in comments!

Keanu Reeves

If the string is good, then answer it's itself. Otherwise, there are at least two strings in answer, and we can print substring without its last symbol and its last symbol separately. Complexity $$$O(n)$$$.

code

Number circle

Let's suppose that array is sorted. First of all, if $$$a_n \ge a_{n - 1} + a_{n - 2}$$$, than the answer is — NO (because otherwise $$$a_{n}$$$ is not smaller than sum of the neighbors). We claim, that in all other cases answer is — YES. One of the possible constructions (if the array is already sorted) is:

$$$a_{n - 2}, a_{n}, a_{n - 1}, a_{n - 4}, a_{n - 5}, \ldots ,a_1$$$

It's easy to see, that all numbers except $$$a_n$$$ will have at least one neighbor which is not smaller than itself. Complexity $$$O(nlog(n))$$$.

code

$$$\textbf{Challenge}$$$

Solve the task in $$$O(n)$$$ (if we suppose that all numbers don't exceed $$$10^9$$$).

Candies!!!

Solution 1 (magic)
Solution 2 (dp)

Add on a tree

We claim, that the answer is YES iff there is no vertex with degree 2. After this, it's easy to get a solution for first subtask in $$$O(n)$$$.

Proof

Because all numbers are different, in the second subtask if we have a vertex with degree $$$2$$$ then answer is NO. If there is no such then construction also follows from proof. Indeed, if we can add on any path to leaf, then we can add on one edge. So, consider any edge $$$uv$$$ and suppose we want to add $$$x$$$ on this edge. Let's find any leaf in a subtree of vertex $$$u$$$, which doesn't contain $$$v$$$, let's name it $$$l$$$. If $$$l = u$$$, just add $$$x$$$ on path $$$uv$$$. Else, add $$$x$$$ on path $$$vl$$$ and $$$−x$$$ on path $$$ul$$$. It's clear, that after this two operations we've added $$$x$$$ on edge $$$uv$$$ and didn't add anything on other edges. Then, just add on each edge needed number.

In the end, let's talk about implementation. To add on the path to leaf it's sufficient to find a leaf in the subtree. We can do it naively in $$$O(n)$$$, then complexity is $$$O(n^2)$$$. Also, we can precalculate leaves in each subtree and, for example, root tree at some leaf. Then, it's possible to do all operations in $$$O(1)$$$, and complexity is $$$O(n)$$$, but it wasn't needed.

$$$\textbf{Challenge}$$$

Solve task if numbers are not necessary even and different, but all operations should be also with integer $$$x$$$(now it turns out that sometimes it's possible to solve it in rationals, but not in integers).

code for 1 subtask code for 2 subtask

Count pairs

Let's transform condtition a ittle bit. $$$a_i - a_j \not\equiv 0$$$ $$$mod$$$ $$$p$$$, so condtition is equivalent:

$$$(a_i - a_j)(a_i + a_j)(a^2_{i} + a^2_{j}) \equiv (a_i - a_j)k \Leftrightarrow a^4_{i} - a^4_{j} \equiv ka_i - ka_j \Leftrightarrow a^4_{i} - ka_i \equiv a^4_{j} - ka_j$$$.

That's why we just need to count number of pairs of equal numbers in the array $$$b_i = (a^4_{i} - ka_i)$$$ $$$mod$$$ $$$p$$$. It's easy to do it, for example, using map. Complexity $$$O(n)$$$ or $$$O(nlog(n))$$$.

code

$$$\textbf{Challenge}$$$

Solve the task, if numbers are not necessarily different.

Array beauty

First of all, let's learn how to solve the following subtask:

For given $$$x$$$ how many subsequences of length $$$k$$$ have beauty at least $$$x$$$? If we know that the answer for $$$x$$$ is $$$p_x$$$, than the answer for original task is $$$p_1 + p_2 + \ldots + p_{max(a)}$$$, where $$$max(a)$$$ is maximum in array $$$a$$$. Let's solve subtask.

Suppose, that array is sorted. We should count subsequence $$$p_1 < p_2, \ldots < p_k$$$, iff:

$$$a_{p_2} \ge a_{p_1} + x, \ldots, a_{p_k} \ge a_{p_{k - 1}} + x$$$.

We will solve this task using dp. The slow solution is:

$$$dp[last][cnt]$$$ — number of subsequences of length $$$cnt$$$, which end in $$$a_{last}$$$. There are transitions from state with $$$last' < last, cnt' = cnt - 1$$$, such that $$$a_{last} \ge a_{last'} + x$$$. To optimize it we need to note, that suitable $$$last'$$$ form some prefix of the array. If we know needed prefixes and prefix sums from the previous layer of dp, then we can make transitions in constant time. We can find needed prefixes using two pointers(because it's obvious, that length of prefixes doesn't decrease). So, we can solve subtask in $$$O(nk)$$$ time.

And, using solution to subtask, we can solve inital task in $$$O(max(a)nk)$$$. And here comes magic:

If $$$x > \frac{max(a)}{k - 1}$$$, than $$$p_x = 0$$$. Indeed, если $$$a_{p_2} \ge a_{p_1} + x, \ldots, a_{p_k} \ge a_{p_{k - 1}} + x$$$, than:

$$$a_n \ge a_{p_k} \ge a_{p_{k-1}} + x \ge a_{p_{k-2}} + 2x \ldots \ge a_{p_1} + (k - 1)x \ge (k - 1)x$$$. It follows: $$$(k - 1)x \le a_n \Leftrightarrow x \le \frac{a_n}{k - 1}$$$.

So we can run our dp only for $$$x \le \frac{max(a)}{k - 1}$$$. In total our solution works in $$$O(\frac{max(a)}{k - 1}nk) = O(max(a)n)$$$ time, because $$$\frac{k}{k - 1} \le 2$$$.

$$$\textbf{Challenge}$$$

How fast you can solve the task if you need to print answer for all $$$2 \le k \le n$$$?

code

Make equal

We will suppose, that array is sorted. Let $$$x$$$ be the final number. Than $$$x \ge a_n$$$. Also, if we define $$$bits[c]$$$ — as number of ones in binary notation of $$$c$$$, than, to get $$$x$$$ from $$$a_i$$$ we will spend at least $$$bits[x - a_i]$$$ moves(it follows from the fact, that minumum number of powers of two, which in sum are equal to the number, corresponds to it binary notation). Let $$$t = x - a_n$$$, than $$$x - a_i = t + a_n - a_i$$$. So we need the following task:

Minimize sum $$$bits[t + a_n - a_1] + bits[t + a_n - a_2] + \ldots + bits[t + a_n - a_n]$$$, where $$$t$$$ is some nonnegative integer. Also, let's define $$$b_i$$$ as $$$a_n - a_i$$$.

We will solve this task using dp — value, which we want to minimize is sum $$$bits[t + b_i]$$$, taken over bits up to $$$(k - 1)$$$. Then, suppose we want to decide something about $$$k$$$-th bit. Let's understand, which information from the previous bits is needed for us. Imagine, that we sum $$$t$$$ и $$$b_i$$$ in vertical format. Clearly, to find $$$k$$$-th bit in number $$$t + b_i$$$ it's sufficient to know $$$k$$$-th bit in number $$$t$$$ and do we have carry from previous digit. Furthermore, if we know this information for the previous bit, we can get it for the next(carry in new digit will occur iff $$$bit_k[b_i]$$$ + $$$bit_k[t]$$$ + $$$(did we have carry) \ge 2$$$). But we should save information about carry for all numbers $$$t + b_i$$$, so, at first sight, for one bit we have at least $$$2^n$$$ different states of dp. To reduce the number of states we need to note key fact:

Let $$$t' = t$$$ $$$mod$$$ $$$2^k$$$, $$$c' = c$$$ $$$mod$$$ $$$2^k$$$. Than, carry in $$$k$$$-th bit will occur $$$t + c$$$ iff $$$t' + c' \ge 2^k$$$. Indeed, carry corresponds to the fact that the sum of "cutoff" numbers is at least $$$2^k$$$.

Using this fact we understand that, if we sort numbers $$$b_i' = b_i$$$ $$$mod$$$ $$$2^k$$$, than carry in $$$k$$$-th bit will happen only for some suffix of $$$b_i'$$$. That's why, we get $$$n + 1$$$ different states for one bit, which is good. So we only need to learn how to make transitions fast. It's useful to note, that we don't need to know numbers $$$b_i$$$, it's sufficient to know do we have a carry and value of $$$k$$$-th bit of $$$b_i$$$. Then, transition reduces to count the number of $$$1$$$ and $$$0$$$ in $$$k$$$-th bit on some segment of the array sorted by $$$b_i'$$$. This can be easily done in constant time if we precalculated prefix sums(for better understanding you can read attached code). So, we can solve the task in $$$nlog(n)F$$$ time, where $$$F$$$ is bit up to which we'll write dp. So, it' left to show (or to believe :)), that there is no sense to consider big $$$F$$$.

Not so long proof

Now we can honestly say that complexity of solution is $$$O(nlog(n)log(max(a))$$$.

code

$$$\textbf{Challenge}$$$

Can you solve task in $$$O(nlog(max(a))$$$?

Problem from Red Panda.

We'll suppose(as in 3 tasks before), that the array is sorted. Our operation is equivalent to choosing some $$$1 \le i \le k$$$ and increasing $$$a_i$$$ by $$$k - 1$$$, аnd decreasing remaining $$$a_i$$$ by one. To solve the task, we need to make some claims:

$$$\textbf{Claim 1}$$$

Difference $$$a_i - a_j$$$ $$$mod$$$ $$$k$$$ doesn't change for any $$$i, j$$$. Moreover, in one move $$$a_i$$$ shifts by $$$1$$$ $$$mod$$$ $$$k$$$.

$$$\textbf{Claim 2}$$$

If we've made two sequences of moves of length $$$i$$$ and $$$j$$$, where $$$i < k$$$, $$$j < k$$$, then obtained configurations coincide iff $$$i = j$$$ and chosen colors coincide as multisets(orders can be different, but number of times we've chosen each color needs to be equal).

Proof

Because in one side claim is obvious, we will suppose, that obtained configurations are equal and we'll show that multisets of colors are also equal. Let's define number of baloons, which we've got using first sequence, as $$$b_t$$$ and $$$c_t$$$ for the second. Because $$$b_t \equiv b_t - i$$$ $$$mod$$$ $$$k$$$, $$$c_t \equiv a_t - j$$$ $$$mod$$$ $$$k$$$, то $$$i = j$$$. Let's note that $$$b_t = a_t - i + k \cdot addB[t]$$$, where $$$addB[t]$$$ — number of times we've chosen color $$$t$$$. So, we get that $$$addB[t] = addC[t]$$$ for each $$$1 \le t \le k$$$.

$$$\textbf{Claim 3}$$$

If there is $$$i$$$, such that $$$a_{i + 1} < i$$$, then we'll not make more than $$$i - 1$$$ moves.

Proof

On each move we choose exactly one color, so after $$$i$$$ moves there will be at least one color among first $$$i + 1$$$ that we didn't choose. But then, the number of balloons of this color will be less than $$$i - i = 0$$$, which is not allowed.

Let's call minimum index $$$i$$$ from Claim 3(if it exists) critical.

$$$\textbf{Claim 4}$$$

Suppose critical index is equal to $$$i$$$. Assume, that we decided to make $$$j < k$$$ moves and we've fixed number of choices of each color — $$$add[t]$$$. It's clear, that $$$add[t] \ge 0, add[1] + add[2] + \ldots add[k] = j$$$. Then, there exist correct sequence of moves with this number of choices iff:

  1. $$$j < i$$$

  2. If $$$a_t < j$$$, then $$$add[t] > 0$$$.

Not so long proof

Using these claims, we can solve the problem if the critical index exists and is equal to $$$i$$$:

Let's iterate through all possible number of moves between $$$0$$$ and $$$i - 1$$$, suppose it's equal to $$$x$$$. Then, by Claim 4 we know that, if $$$a_p < x$$$, then $$$add[p] > 0$$$, else there are no restrictions (except obvious $$$add[p] \ge 0$$$). So, we have arrived to the following problem:

Count the number of nonnegative solutions $$$add[1] + \ldots + add[k] = x$$$, where fixed $$$num$$$ numbers should be positive. By Claims 2 and 4 the solutions of this equation correspond to some final configuration, and this is exactly what we need to count.

This is well known task(stars and bars), answer is given by $$$C^{x - num + k - 1}_{k - 1}$$$

So, the answer is given by the sum of these values over all $$$x$$$.

Let's call configuration $$$\textbf{critical}$$$, if it has critical element (in other words, if there is index $$$i$$$ such that $$$i < k-1$$$ and at least $$$i+2$$$ elements of configuration do not exceed $$$i$$$).

To solve the problem when there is no critical index we need:

$$$\textbf{Claim 5}$$$

If configuration is not critical, then configuration $$$b_i$$$ is reachable iff $$$a_i - b_i \equiv a_j - b_j$$$ $$$mod$$$ $$$k$$$ and $$$b_i \ge 0$$$, $$$a_1 + \ldots a_k = b_1 + \ldots b_k$$$.

Long proof

Now, it only remains to show how to count the number of such $$$b$$$ from Claim 5.

$$$b_1, b_2, \ldots, b_k$$$ should give remainders $$$(a_1+t) \bmod k, (a_2+t) \bmod k, \ldots, (a_k+t) \bmod k$$$ for some $$$t$$$. We сan calculate configurations with such remainders by the following way: remaining $$$a_1 + a_2 + \ldots + a_k - (a_1+t) \bmod k - (a_2+t) \bmod k - \ldots - (a_k+t) \bmod k$$$ are splitted in groups by $$$k$$$ and are distributed in $$$k$$$ elements in any way. So, that's why, for given $$$t$$$ number of configurations(by stars and bars) is given by $$$C^{\frac{a_1 + a_2 + \ldots + a_k - (a_1+t) \bmod k - (a_2+t) \bmod k - \ldots - (a_k+t) \bmod k}{k} + k-1}_{k-1}$$$. Sum $$$a_1 + a_2 + \ldots + a_k - (a_1+t)\bmod k - (a_2+t)\bmod k - \ldots - (a_k+t) \bmod k$$$ can be calculated for $$$t = 0, 1, \ldots , k-1$$$ in $$$O(1)$$$, if we precalculate number of each remainder among $$$a_1, a_2, \ldots, a_k$$$.

That's why final complexity for each of the cases is $$$O(n + k)$$$.

code

$$$\textbf{Challenge}$$$

Find all typos in proofs.

 
 
 
 
  • Vote: I like it
  • +182
  • Vote: I do not like it

»
11 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Oh my god I overcomplicated A...I'm so bad at this :(

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

    haha same

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

    Hahahaha i too that sad :(

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    Don't feel bad, I've been years overcomplicating problems too hahah, anyway experience will be there for you next time.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    what is wrong in my code?

    include <bits/stdc++.h>

    using namespace std;

    int main() { int n; string s; cin>>n>>s; int b=0; if(n%2 == 1) cout<<"1 \n"<<s; else { cout<<"2"<<"\n"; for(int i=0;i<n;i++) { if(s[i] == '1' ){ cout<<s.substr(0,i+1)<<' '<<s.substr(i+1, n-1)<<'\n'; break; } else continue;

    }
    
    }
    
    return 0;

    }

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

    I have hilariously over complicated the solution.

    Please have a good laugh at my expense.

    LOL XD

    But, I loved solving the problem :)

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int ln0[110];
    int ln1[110];
    int rn0[110];
    int rn1[110];
    
    int main()
    {
    	int n;
    	string s;
    
    	cin >> n;
    	cin.ignore(4096,'\n');
    	getline(cin,s); // nice try cforces XD
    
    	//cout << n << endl << s << endl;
    
    	for(int i=0; i<n; ++i){
    		ln0[i] = 0;
    		ln1[i] = 0;
    		rn0[i] = 0;
    		rn1[i] = 0;
    	}
    
    	if(s[0] == '0')
    		ln0[0] = 1;
    	if(s[0] == '1')
    		ln1[0] = 1;
    
    	if(s[n-1] == '0')
    		rn0[n-1] = 1;
    	if(s[n-1] == '1')
    		rn1[n-1] = 1;
    
    	for(int i=1; i<n; ++i){
    		char c = s[i];
    		if(c == '0'){
    			ln0[i] = ln0[i-1]+1;
    			ln1[i] = ln1[i-1];
    		}
    		else if (c == '1'){
    			ln1[i] = ln1[i-1]+1;
    			ln0[i] = ln0[i-1];
    		}
    	}
    
    	for(int i=n-2; i>=0; --i){
    		char c = s[i];
    		if(c == '0'){
    			rn0[i] = rn0[i+1] + 1;
    			rn1[i] = rn1[i+1];
    		}
    		else if (c == '1'){
    			rn1[i] = rn1[i+1] + 1;
    			rn0[i] = rn0[i+1];
    		}
    	}
    
    	int count = 1;
    
    	if(ln0[n-1] != ln1[n-1]){
    		cout << count << "\n";
    		cout << s << endl;
    		count++;
    	}
    
    	if(count == 1){
    		for(int i=0; i<n-1; ++i){
    			if((ln0[i] != ln1[i]) and (rn0[i+1] != rn1[i+1])){
    				count++;
    				cout << count << "\n";
    
    				for(int j=0; j<=i; ++j)
    					cout << s[j];
    				cout << " ";
    
    				for(int j=i+1; j<n ; ++j)
    					cout << s[j];
    
    				cout << endl;
    				break;
    			}
    		}
    	}
    
    	return 0;
    }
    
    
»
11 days ago, # |
  Vote: I like it +9 Vote: I do not like it

Thanks for the fast editorial!

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

Amazingly Fast.

»
11 days ago, # |
  Vote: I like it +15 Vote: I do not like it

My solution for problem E works in time $$$O(k+C)$$$ where $$$C$$$ is maximal element, not the sum of elements.

I need one more lemma: for every possible configuration there exists a sequence of action in which we do not increase the number of balloons with one particular color (and it is easy to see that the number of operations with each color is uniquely determined).

So we can count number of sequence of such actions. Try all possibilities of length of such sequence, it is bounded by $$$C$$$. Then do thing similar to editorial, but now both parameters of binomial coefficients are bounded by $$$k+C$$$.

You can see the submission here: 56582671

»
11 days ago, # |
  Vote: I like it +4 Vote: I do not like it

Pretty interesting! Solved C via Segment Tree :)

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

    help!

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

      My submission using segment tree

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 2   Vote: I like it +6 Vote: I do not like it

        I also tried using segment tree but had to use 2 segment trees depending on query l, r if l is even or odd Link can you please help me as test case it is failing on is pretty huge.

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

        can u plz.. explain the solution using segment tree.. i am new with segment tree that's why i can't understand ur solution.. thanks.

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

          whole point of segment tree is merging two nodes into one,so this data structure is perfect for this problem. Observe the merge of nodes where 'node' is current node '2*node' is left child '2*node+1' is right child Recursively both child added and their sum is stored in parent.

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

            in the parent, is sum of node is stored or sum of candies is stored.. thanks for the reply....

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

            Thanks now i understand that segment tree is doing the same thing as out dp presum doing

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

        I am afraid that your solution may do the same work as the O(n) magical solution in the tutorial. Your segment tree actually save the sum of intervals since 'sum' is the part which is moduled by 10 and 'candy' the part divided by 10. And this can be done by a PRESUM array in the complexity of O(n). Besides, if the given array has elements bigger or equal than 10, then neither your solution nor the magical solution will do.

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

          Yes us r write presum is easier than segment tree in implementing but how can u say that is digit is greater than 10 then none of the code will work?? can u give some proof.

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

            is dp solution work?? if work can u plz explain me the dp solution.. thanks!!_

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

              First, calcucate the pair(remainder,candy) of intervals with fixed length in advance. say, length of $$$1,2,4...2^k$$$. There are logN types of length to calcuate, and the number of intervals with length $$$t$$$ is $$$n-t+1$$$ . So we refer to the complexity as O(nlogn) .

              To give an example, if we have the array [9,6,7,8],we should do as follows:

              length1: [(9,0),(6,0),(7,0),(8,0)]---->{1}{2}{3}{4}

              length2: [(5,1),(3,1),(5,1)]---->[1,2],[2,3],[3,4]

              length4: [(0,2)]---->[1,4]

              If you are familiar with dynamic programming, you can easily figure out the dp formula.

              Given length and the left end, you can deal with any query in O(1).

              DP can deal with problems of this type in a more general way without such strict constraint "digits are less than 10".

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

              "digits greater than 10" is not a proper example. I was trying to demonstrate that if there are different constraint conditions, the solution based on Interval Subtraction Propert(the magic and segment tree) will no longer work.

              Say, if the problem is fixed as follows:

              After a combination of two neighbouring digits, the new value is no longer $$$(x+y) \mod 10$$$ but $$$((x+y)*2+3)\mod 10$$$ , then dp is the only way(maybe not, as long as it has some property) to solve this problem in O(nlogn).

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

                Thanks.. for great explanation .. amazing..

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

        I don't want a link. I can find it myself. I need an explanation.

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

On problem C, Isn't it suppose to take always a pair and then replace it with mod of sum of them? If I use this array: [110 120 130 140], I take 2 pairs (110, 120) and (130, 140), it's obvious that I got 2 candies, but, when I replace them the array now is [0 0], so I only take 2 candies. If I use Editorial's claim I got 50 candies. I think I can't understand the problem, can anyone help me with this doubt?

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

    Numbers are digits, i.e. they can't be larger than 9

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

    Read the constraint carefully

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

    Yeah lol, even i didn't read the constraints and ended up using sparse tables.

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

I liked the DP solution for problem C as it can be applied to any function rather than modulo.

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

I did the challenge for Div 2 B in the contest. It's O(n) if I'm not mistaken. https://codeforces.com/contest/1189/submission/56577088

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

    Your solution's complexity is O(nlog(n)) as you have sorted the whole array.

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

I wonder how most people prove their solutions to 1189D1 - Add on a Tree instead of knowing how to construct the solution(1189D2 - Add on a Tree: Revolution)

  • »
    »
    10 days ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    For each pair of leaves (say $$$i$$$ and $$$j$$$) let $$$x_{ij}$$$ denote an operation performed on the pair. It is obvious that we need not choose a pair twice, since we can combine them to a single one.

    We can show that if none of the nodes have degree 2, then the value of each edge, expressed as an equation will be different. (Every edge, splits the leaves into two sets, and the value of the edge will be $$$\sum{x_{ij}}$$$ (for every pair of leaves i, j such that the edge belongs on the path from i to j)

    We will then have $$$n-1$$$ equations and $$${L}\choose{2}$$$ variables. We can also show that if all non-leaf nodes are of degree $$$\geq$$$ 3, then $$$L$$$ (the number of leaves) is atleast $$$(n+2)/2$$$. Hence the result follows.

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

      However, forgiving my poor english , even if there are infinit variables ,i cant prove that the variables of every equation are different.

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

      It should also be noted for completeness that each edge has a unique summand, otherwise we cannot claim the system of equations has a solution only based on the number of variables and pair wise independence(Actually having a unique summand is sufficient condition for there being a solution).

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

What if x is odd in the proof of D1 ?

»
11 days ago, # |
  Vote: I like it +6 Vote: I do not like it

please explain problem c magic solution

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

    For [ 9, 8, 5, 6 ]:
    9 + 8 = 17. we have digitsum = 7 and candy = 1
    5 + 6 = 11. we have digitsum = 1 and candy = 1
    In the next step, we have 1 + 7 = 8 and no extra candy
    but in each step, we're adding the candies, 1 + 1 = 2. Notice, we don't mod this by 10 or change it in any other way.
    It's basically the same as doing:

    int sum = 0, candy = 0;
    for( int i = 0; i < 4; ++i ) {
        sum += l[ i ];
        candy += sum / 10;
        sum %= 10;
    }
    

    we can get sum(l,r) = candy * 10 + sum in this way
    and bob's your uncle

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

Another approach for Problem C is using Segment Trees, it was very interesting.

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

    Yeah I know about that , but still wondering how this magic thing is working

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

      Because The No. are in range b/w 0 to 9.

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

        can you elaborate

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

          What actually we are doing is that we are counting the number of times our sum exceed 10 and we make it sum%10 i.e count it as 1 and then leave the remainder to contribute further to the sum. (It can be also seen as subtracting 10 from the total sum and count it as 1 for the answer) So our problem broke down to the number of times we can subtract 10 from the sum of the range. This can be achieved by taking sum of the whole range and then answer = sum/10. That's the magic solution using prefix array.

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

Problem C can be solved using Segment Tree.

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

    i think the reason segment tree is working is also on the that that ans is sum of [l,r]/10 . For eg like in case 8 7 3 1 7 0 9 4 if we query for range [4,7] the query would be uneven as 1 number lies in range [1,4] and 3 number lies in [5,8] so we cannot check the sum of two consecutive elements like 1+7 and 0+9 . through seg tree we get 1 from left end and 7+0+9 from right end .

»
11 days ago, # |
  Vote: I like it +5 Vote: I do not like it

in the challenge of problem E, if x = y (mod p) => (x + y) * (x ^ 2 + y ^ 2) = 4 * x ^ 3 (mod p) and then what you have to do is first for each number you must check if its cube mod p = k * inv (4) and if the number of equals to it is c, then the solution is incremented by c * (c — 1) / 2, afther this check, do the same thing when they are different but with the array after eliminating the equals

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

    Your solution should be correct. We need to proceed this way because for $$$a_i=a_j$$$, we cannot multiply both sides by a $$$0$$$ in the given equation.

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

Else, add x on path vl and −x on path ul. but u and v are not leaves ?

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

Can anyone explain problem B div2 please

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

    That's how I thought of it. First sort your array now we have [a1, a2, .. , an] see if we try representing it as a circle it will look like [a1, a2, ... , an, a1]. Now as a[i]>=1 for all i we know and a[i+1]>=a[i] => a[i]<a[i+1]+a[i-1] always except for last element a[n] so we take it out place it b/w 2 largest numbers possible i.e. a[n-1] and a[n-2] now our answer array looks like [a1, a2, ..., a(n-2), an, a(n-1)] we check a[n]<a[n-1]+a[n-2] if it is then ok otherwise its not possible!

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

thanks for challenges)

»
10 days ago, # |
  Vote: I like it -8 Vote: I do not like it

Hi, for problem "Add on a Tree: Revolution", why can't we just output the input? I mean, for example 1, isn't rewriting the input is exactly the way it can be constructed?

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

    the only operations allowed are choosing two leaves and do the operations on them ,while in the input given the edges are not always between leaves

»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

I have done the challenge of div.2 B but I'm in a hurry so that I cannot check if it is right. It looks like the complexity is O(n), maybe somebody could check it for me?

Here is my code

  • »
    »
    10 days ago, # ^ |
    Rev. 5   Vote: I like it +10 Vote: I do not like it

    OK, here is the explanation of my thoughts:

    First, deal with the three largest numbers as the tuterial mentioned, put them at the rear, then the problem is how to arrange the other numbers.

    if we calculate a value $$$k_i$$$ for every $$$a_i$$$ such that $$$2^{k_i}{\leq}a_i{<}2^{k_{i}+1}$$$, we can make sure that for any three $$$a_i$$$ with the same $$$k$$$, one number plus another is always larger than the other one. Therefore, we can find all the $$$k_i$$$ at first and put all the $$$a_i$$$ with the same $$$k$$$ together. As for $$$a_i$$$ with different $$$k$$$, since the number with larger $$$k$$$ is also larger, so we can arrange $$$a_i$$$ with smaller $$$k$$$ first, then the number with larger $$$k$$$. Besides, for every $$$a_i$$$ with the same $$$k$$$, the smallest should always be arranged at first to make sure the number after it is greater or equal to it.

    The complexity of finding the three largest numbers is $$$O(n)$$$. All the $$$k_i$$$ can be found using binary search, so the complexity of calculating all the $$$k_i$$$ is $$$O(nloglog(max(a)))$$$. As to finding all the smallest $$$a_i$$$ with the same $$$k$$$, the complexity is $$$O(n)$$$. Therefore, the total complexity is $$$O(nloglog(max(a)))$$$. Since $$$max(a)$$$ is $$$10^9$$$, I think it is very close to $$$O(n)$$$ already.

    Here is my code that was updated.

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

i cant understand the solution to D ,who can help me please.
So, consider any edge uv and suppose we want to add x on this edge. Let's find any leaf in a subtree of vertex u, which doesn't contain v, let's name it l. If l=u, just add x on path uv. Else, add x on path vl and −x on path ul
how to add x on path uv or −x on path ul

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

Can Some explain Problem D.I am not able to understand what is it saying.

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

can someone please help me out I am doing coding since last one year but I am the same condition which I was one year. In each contest, I am able to solve at most one problem. Please, someone, help me out and how to improve myself.

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

    Solve problems of topics you're not comfortable with or you can start solving a2oj ladders to get used to solving problems of varying topics.

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

Can anybody explain div 2 B, I cant understand the tutorial given, why to just check a[n] >= a[n-1] + a[n-2]

a[n] neighbours are a[n-1] and a[0] right? So just how we can come to this conclusion to just check the above condition in case of sorted list/array. And how solution becomes an−2,an,an−1,an−4,an−5,…,a1 (if sorted)

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

    because after sorting (an) now is the largest number if we could find 2 numbers their sum is strictly greater than an then there is answer and of course the numbers that could do this will be (an-1) and (an-2) then all numbers except (an) will have a neighbouring number which is greater than or equal to it so the sum of its neighbours will of course be strictly greater than the number and since (an) is fine then we are done

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

can anyone explain me the solution of C using dp.. I didn't understand from editorial!! thanks..

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

On Add on a tree: Revolution, can we just add a value x on an edge and keep it as we move downwards? For example, if we have the nodes u (parent) and v and also v has a child c, can we add the required value x to the uv and then on the vc subtract the $$$x - x_{vc}$$$? In such a way, we obtain the desired value (ie. $$$x_{vc}$$$).

Thanks!

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

sir , IN COUNT PAIRS why did we assume ((a^4)-(k*a))%p is equal to k%p ??? also k is function of ai and aj ,it will vary everytime . please clarify

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

    k is a constant given in the problem, it will not vary. and he did not assume this he said that :(ai+aj)*(ai^2+aj^2) ≡ k mod p so we want (ai+aj)*(ai^2+aj^2)=k when both taken modulo p and after multiplying both sides by (ai-aj) and simplifying both sides we reached to (ai^4-aj^4)=ai*k-aj*k which is equivalent to aj^4 — aj*k=ai^4-ai*k

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

      thanks ,but it looks complicated ,can you tell me ,which math concept is being used here ... i will try to study that

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

        you are welcome.he only used the congruence in modular arithmetic and simple math to simplify both sides of the equation

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

I am not quite able to understand the editorial for Array beauty. Could someone explain in a simpler way please? or an alternate solution ? Anything would do , thank you!

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

In editorial of div2 F it was assumed that the array is sorted and problem was solved. How does it apply to unsorted array? Am I missing something ?

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

can anyone explain me the solution of div 2 E given in the editorial.

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

    we want (ai+aj)*(ai^2+aj^2) ≡ k mod p so we want (ai+aj)*(ai^2+aj^2)=k when both taken modulo p now multiply both sides by (ai-aj) and since all elements are different we are not multiplying by zero(ai-aj!=0) now we have : (ai-aj)*(ai+aj)*(ai^2+aj^2)=(ai-aj)*k ,which is equivalent to (ai^4-aj^4)=ai*k-aj*k then for each ai we want this equation to hold aj^4 — aj*k=ai^4-ai*k so we search for the number of aj s that satisfy this equation

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

      but how he deduce that we have to find the number of pairs of equal numbers in the array bi=(a4i−kai) mod p .

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

        for each number we find b=(ai^2-k*ai)%p and count how many numbers in the array have (aj^2-k*aj)%p equal to b also and he deduced that as i wrote in the previous comment

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

Can someone explain why submission(56622740) got TLE, while sparse table got accepted 56626183 for div2C

»
10 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Is the script for add on tree's proof part is broken or is it not loading just for me?

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

Please Somebody help me with problem B. Couldn't understand how they came up with this sequence.

»
9 days ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

what is wrong in my code?

include <bits/stdc++.h>

using namespace std;

int main() { int n; string s; cin>>n>>s; int b=0; if(n%2 == 1) cout<<"1 \n"<<s; else { cout<<"2"<<"\n"; for(int i=0;i<n;i++) { if(s[i] == '1' ){ cout<<s.substr(0,i+1)<<' '<<s.substr(i+1, n-1)<<'\n'; break; } else { if(s[i] == '0') b++; if(b = n) cout<<s; }break;

}

}

return 0;

}

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

In D2's solution code, why is there a piece of code that prints the output of the second test of the problem if it sees the exact input ?

code if anyone having trouble finding it :


if (n==6&&G[1]==test1&&G[2]==test2) { cout<<"YES"<<endl<<4<<endl; cout<<3<<' '<<6<<' '<<1<<endl; cout<<4<<' '<<6<<' '<<3<<endl; cout<<3<<' '<<4<<' '<<7<<endl; cout<<4<<' '<<5<<' '<<2; return 0; }
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I think in the proof for Add on Tree, "Proof of necessity" and "Proof of sufficiency" are swapped

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

A question on Add on a tree(D1).
The following tree satisfies the condition that no vertex should have a degree of 2. But I am not able to achieve the below mentioned configuration for the tree. How can we achieve it ?

Tree :

Vertex 1 Vertex 2 Number on the edge

1 2 0

1 3 0

1 4 0

2 5 -1

2 6 +2

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

kefaa2
By any chance, is there a solution to Div1. A2 (Tree: Revolution) using gaussian elimination or is the challenge solvable using it. As we can have variables $$$x_{ij}$$$ for operation using leaf i and leaf j and then we can formulate $$$n-1$$$ equations corresponding to each edge.

Please confirm if I am correct. And if it is indeed solvable using Gauss method, the complexity will be $$$O(n^3)$$$, isn't it ?

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

    I suspect the problem you'll have with Gaussian elimination is that it won't necessarily give you an integer solution. Also you have $$$O(n^2)$$$ variables (one for every pair of leaves) so I think it will be more like $$$O(n^4)$$$.

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

      If there are $$$O(n^2)$$$ variables, why is complexity $$$O(n^4)$$$ and not $$$O((n^2)^3)$$$ or $$$O(n^6)$$$?

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

        Because there are only $$$O(n)$$$ equations (one per edge), so you'll only need to pivot $$$O(n)$$$ times, and each pivot will take $$$O(n^3)$$$.

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

      Yea so it seems a fit for solving the challenge part as the editorialist mentioned "the numbers on each edge need not be integers".

      However, the $$$O(n^4)$$$ is not feasible for such constraints in case we want to apply Gaussian elimination.

      How exactly and efficiently would you solve the challenge part, then?

      • »
        »
        »
        »
        4 days ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        Spoiler
»
5 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi, can someone explain in more detail how to compute dp[last][cnt] in div2F (Array beauties)? I still don't understand how this is computed and optimized despite thinking about the editorial code for awhile. Also, is this a standard dp problem and can anyone suggest any related problems? I noticed that a lot of red coders solved this question very fast. Thanks.

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

Thenks for the typos!

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

can someone explain DIV2-F solution?

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

    Sure refer the editorial above.

    And if you are like "I didn't understand it". Hire someone as your personal coach. Why do you think someone would come up with a more elegant solution and explain it especially for you. Have some shame before posting such comments. Have some courtesy to post your doubt, what you didn't understand instead of a "can someone explain DIV2-F solution?"