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

vovuh's blog

By vovuh, history, 4 years ago, In English

1311A - Add Odd or Subtract Even

Idea: vovuh

Tutorial
Solution

1311B - WeirdSort

Idea: MikeMirzayanov

Tutorial
Solution (n^2)
Solution (n log n)

1311C - Perform the Combo

Idea: vovuh

Tutorial
Solution

1311D - Three Integers

Idea: MikeMirzayanov

Tutorial
Solution

1311E - Construct the Binary Tree

Idea: MikeMirzayanov

Tutorial
Solution

1311F - Moving Points

Idea: vovuh

Tutorial
Solution (Fenwick tree)
Solution (pbds)
  • Vote: I like it
  • +31
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +42 Vote: I do not like it

B works in O(n), no sort needed. Code

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

    nicely done :)

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

    Can you explain your solution? Thanks in advance...

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

      Lets call a position where we cannot swap the two elements a border. So, for every position there is a border nearest left of it.

      All elements left of the border cannot pass the border (because we cannot swap there).

      In var ma2 we maintain the maximum value left of the border. Then we compare the current element (which is right to the border) to ma2.

      The var ma is used to maintain the current maximum, which is moved to ma2 whenever we find a border position.

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

    Problem B We can use map to see can we go from a point to another and see for every a[i]
    Here is The code : 71906289

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

    nice!

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

    Thank You very much!!!!

»
4 years ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

If we use 2 pointers in E, complexity will be O(n). https://codeforces.com/contest/1311/submission/71823186

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

    Can you explain your approach ? Thank advance ^_^!!

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

      Statement 1: There is no exist the tree with sum of depths of all vertices more than unary tree.

      Statement 2: There is no exist the tree with sum of depths of all vertices less than balanced tree.

      Let's create unary tree for default. Sum of depth for this tree — is the sum of ariphmetic progression. We must decrease it to the d. Fix the deepest vertex. Fix the top vertex of the tree. If we can't attacth the lower vertex to the higher because the sum of depth will be smaller than d, it means that we must deepen the upper vertex. And as we go from top to bottom the difference on every step decreases exactly 1. It means that there isn't exist the better solution.

      Add to these the condition that every layer must be not greater than 2 size of previous layer and this will be a solution.

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

F can be solved without pbds and fenwick tree, look at this submission.

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

    I explained some reasoning behind this solution but I should have posted it here: this is it:

    First there is a trick to sum all $$$x_j-x_i$$$ for $$$i<j$$$ in a sorted array $$$x[]$$$ in linear time: Errichto wrote some blogs calling it the contribution technique.

    Now in our problem say $$$x=[100,50,75,25]$$$, and the corresponding sorted $$$v=[1,2,3,4]$$$. First we sort $$$x=[25,50,75,100]$$$. Then we can sum $$$x_j-x_i$$$ using the above technique. Look at the ways 75 gets added:

    $$$+75, +75, -75$$$

    (from 75-50, 75-25, and 100-75)

    Now let's iterate through $x$ in sorted $$$v$$$ order: when we get to the third element 75, we see that for our answer we should only have a single

    $$$+75$$$

    term due to the

    $$$75>50$$$

    ; we only want $x_j-x_i$ where $$$v_j>v_i$$$. Coincidentally this equals the net sum of the three terms above. The reason is that if $$$75$$$ has the same rank in both the sorted $$$x$$$ and the sorted $$$v$$$ versions, then there is a symmetry in how $$$[25,50,75,100]$$$ mutates into $$$[100,50,75,25]$$$: we can let other elements "jump over" 75 to anywhere on the other side, and the symmetry is that the number of jumps going right over 75 equals the number of jumps going left: 100 jumped left, but then 25 jumped right. So the rank of 75 is equal in both cases, and we don't need to correct the $$$+75,+75,-75$$$ in our final answer.

    Another case is $$$25$$$, which is rank 1 with respect to $$$x$$$, but rank 4 with respect to $$$v$$$: From the contribution method, we had

    $$$ -25, -25, -25 $$$

    due to 50-25, 75-25, and 100-25. But because the rank changed from 1 (w.r.t $$$x$$$) to 4 (w.r.t $$$v$$$), we must have had 3 jumping overs to the left: and every such jumping over means we shouldn't have included a $$$-25$$$, so we correct with $$$+25$$$ 3 times, and end up with $$$0\cdot 25$$$ in the final answer.

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

    I managed to solve F using a modified version of Merge Sort and prefix sums. Code.

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

    why after changing vector<pair<int,int> >vec(n); into vector<pair<int,int> >vec; then it will get a Runtime Error? Is the data type "pair" responsible for this? Thanks.

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

How to solve F if there is integer t or positive integer t restriction.could we reduce any one restriction to nlogn time or some optimal time.

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

On problem D, I understood why do we iterate A to maximum 2a but what is the reason behind checking all multiples of A to maximum 2b? Also if we don't check for C = (c / B) * B + B, can we get the true answer?

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

    (c / B) * B and (c / B) * B + B are the two consecutive multiples of B such that C lies in between them.

    (c/B) * B <= C <= (c/B) * B + B

    So C could be closer to either of the multiples. We have to check both.

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

      I have a problem is that (c/B) * B it can't ensure the C >= B,but the ans need the B < C.So why we need to consider both? we can't get the wrong ans?Could you tell me about that?

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

        Whether C will get larger than or equal to B or it won't, we will always find an answer such that A < B < C. This is because the distance |c-C| + |b-B| will be larger when B >= C compared to any other possible solution where B < C.

        Also, when B > c (remember the lower-case letters are input variables), then c/B < 1, which means floor(c/B) = 0 and thus C = 0 or C = B which are both not feasible and will fetch us larger total distance sum compared to any feasible solution. It's hard to prove why but you can kind of imagine that.

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

          Is there actually a prove to the problem that "There is feasible solution having a smaller distance comparing to the solution that C=0 or C=B?"?

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

            I can kind of think about why it is so but cannot prove it. Maybe somebody good at Maths here can prove it

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

      Hi buddy, Please help me. For problem D, i guess my code should give wrong answer, but it got AC. Can it be proved that my solution is absolutely correct for all cases?
      My submission : https://codeforces.com/contest/1311/submission/95245170

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

        Provided that the test cases for the problem are very strong, I am confident that your submission is correct for absolutely all cases. Why do you think it should fail? Or what makes you doubt it?

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

    Could you please explain why do we iterate A to maximum 2a?thanks in advance.

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

      Because we can iterate A to 1 at the same cost as iterating A to 2a. And it's clear that 1 can divide more numbers than 2a can divide.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 4   Vote: I like it +4 Vote: I do not like it

        Oh, I understand that now. Thanks a lot.I also have some ideas to share with you.
        Thinking carefully, you'll find that the the reason behind checking all multiples of A to maximum 2b is the same as iterating A to maximum 2a.
        while $$$A>=2*a-1$$$, it works the same as $$$a=1$$$(maybe $$$a=1$$$ works more),but that costs more, so $$$A\in [1,2*a-1)$$$
        In the same way, iterating B to A costs the same as iterating B to b+b-A, but while $$$B=A$$$, it works more,so $$$B\in [A, 2*b-A)$$$

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

          You're welcome, thank you too.

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

          Thank u, I can understand now. I prefer visualizing the thinking. Because B divide by A, C divide by B, so C divide by A. If you take $$$B > 2b$$$, you always can take B = a and this choice even give c more chance to reach C, because B (with > 2b) has multiple point is subset of B (with = A).

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

Another solution for D: Let's precompute divisors and multiples (up to $$$2 \times 10^4$$$) for all numbers up to the $$$10^4$$$. Let's then fix a value of $$$B$$$, then $$$A$$$ has to be a divisor and $$$C$$$ a multiple. We find such $$$A$$$ closest to $$$a$$$ and $$$C$$$ closest to $$$c$$$ in $$$O(log n)$$$, compute the number of operations for that particular $$$B$$$, and repeat this for all possible $$$B$$$'s. Total complexity $$$O(n log n)$$$

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

    Great solution but I think if constraints had been n <= 1e5 or n <= 1e6, then memory limit would have exceeded because space complexity is O(N*sqrt(N))

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it +8 Vote: I do not like it

      As far as I know, the sum of the count of divisors of numbers from $$$1$$$ to $$$n$$$ is about $$$n \times \log n$$$. Please correct me if I am wrong.

      I had the same solution with limit on B set to 1e5 and it passed easily.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -16 Vote: I do not like it

        Looks like we both are making lesser accurate approximations :

        Link

        If i understood the proposed algorithm right then I calculated :

        1.The number of divisors of all numbers from 1 till n. Let this be f(n)

        f(1e4) = 93,668
        f(1e5) = 1,166,750
        f(1e6) = 13,970,034
        

        2.The number of multiples of i till 2*n for all i from 1 to n. Let this be g(n)

        g(1e4) = 191,177
        g(1e5) = 2,372,113
        g(1e6) = 28,326,296
        

        If these numbers are correctly calculated then there could have been a problem with memory limit.

        Also, I think your solution passed because the constrains were upto 1e4. I am unsure of it, so do correct me if I'm wrong.

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

          My submission.

          It considers $$$MAX = 10^{5}$$$ and precomputes all factors of numbers from 1 to $$$MAX$$$.

          There seems to be no problems with memory but problems with time, it nearly hit the TL(due to multiple tests), but memory is fine.

          And I think I know why, since according to me, it should take $$$MAX \log MAX$$$ memory which is about 1.6 million ~ 12 MBytes (assuming long long), this seems to be consistent with the memory my submission took(9.6 MB).

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

            I did not calculate the actual memory upper bound but you are right here. And your calculations are consistent with mine also. For n = 1e5, I also estimated 1.6M numbers in total. Which is passable.

            For n <= 1e6 it should fit in the memory limit as well, it would take something as high as 150 MB which is fine.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it +3 Vote: I do not like it

          About the link you gave regarding the upper bound on divisors. I think the upper bound on divisors of a single number is not tight enough to give sum of count of divisors of all numbers in a range with good margin of error. (Some numbers have more factors, some less, so error accumulates)

          See this comment for details about my estimation comment

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

            You are correct about this. Thanks for correcting me.

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

    I thought that finding closest divisor of given number has the complexity of O(sqrt(n)) since you have to iterate all the divisors of given number and check the diff of them ?

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

    Is there a way to approach find closest divisor of given number in O(log n) ?

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

      In this particular problem you can precompute all divisors of all numbers up to $$$10^4$$$ and have them in memory, so finding the closest one to a given number is a binary search so $$$O(log n)$$$. Check this code.

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

      I dont understand, can you go in more detail. I mean the source of your algorithm ?

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

        Precomputation is like sieve of prime factors, we iterate on numbers and push current number to all of its multiples. Overall complexity is given by harmonic series sum, $$$O(n + n / 2 + n / 3 + ... + 1)$$$ which reduces to $$$O(n \times \log n)$$$.

        With this, we get list of divisors of all numbers from $$$1$$$ to $$$n$$$ now use binary search to find closest divisor.

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

    great solution! But I'm wrong because I think that the range of possible B is 1 to 10^4. In your answer, you set it up to 2 * 10 ^ 4. Can you tell me why? Thanks

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

      Take for eg 137 10000 10000, the optimal solution would be 137 10001 10001, so the value(s) of a,b and c can exceed 10000.

      But we know that the value can never exceed 20000, since we could always bring down a,b or c<=10000 to be equal in less than 10000 steps.

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

      why till 2*10^4 . How did you get this number ?

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

    I did the same but why till 2e4 and in the editorial why till 2a, could u plz explain? I got some intuition but unable to formalize it.

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

      We consider only the values <= 2*a because the cost of transforming a into a value >2*a is greater than the cost of transforming it into 1, and 1 will always be solution as every number is divisible by 1

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

    Actually it's possible not to precalculate, since you can find $$$C$$$ closest to $$$c$$$ can be found in $$$O(1)$$$ and $$$B$$$ closest to $$$b$$$ in $$$O(\sqrt{B})$$$ which is roughly $$$1e8$$$ operations maximum. 155903580

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

WoW, thanks for the tutorial.

In problem B, thought if I approach find a -> find b -> find c. I have to iterator for (all possible a), for (all possible b), (find c), which run in O(q * a * b) then get TLE. But now I learn more that I just need to go for (all possible a), for (mutiples a), (find c). O(q * a log a)

»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

IN D why editorial code O((n^2)*10^2) is working even after a<=10^4 and b <=10^4 ?

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

    We are iterating over multiples of "a",to find "b" as b is a multiple of "a".Its a kind of sieve that through which we don't have to consider all the values of b<=2*10^4.

    for(int i=1;i<=20000;i++) for(int j=i;j<=20000;j+=i) (Here i represents "a" and j represents "b")

    So,the time complexity in O(t*n*log(n)).

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Does anyone uses brute force algorithm like me in problem D?XD

#define n (20000)
int a,b,c;cin>>a>>b>>c;
int ans=9999999,_a=0,_b=0,_c=0;
for(int i=1;i<=n;++i) for(int j=1;j<=n/i;++j) for(int k=1;k<=n/i/j;++k) 
{
	int now=abs(i-a)+abs(i*j-b)+abs(i*j*k-c);
	if(now<ans) _a=i,_b=i*j,_c=i*j*k,ans=now;
}
cout<<ans<<endl<<_a<<' '<<_b<<' '<<_c<<endl;

I heard that a lot of people were hacked because they set the limit only 10000 XD

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

    I was hacked...

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

      That's bad :-(

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

        I was rank 62 when I went to sleep,and rank 226 when I woke up,and found myself hacked.

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

    why are we setting limit to 20000? I do not understand this, can you please explain. Thank you

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

      because i know that 10000 is not enough (for example 173 10000 10000)
      but i can't find the real limit so i just set the limit 20000.(it's easy to prove that 20000 is enough)
      maybe 15000 is enough

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

On problem D, I understand why we iterate A to maximum 2a but what is the reason behind checking all multiples of A to maximum 2b?

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

    Oh I understand that now. B must satisfy: |B-b|<=|A-b|, thus B<=2b.

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

      hi could you please elaborate a little more. Thanks in advance.

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

        if |B-b|>|A-b|, then change B to A, and the result will be better

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

can anyone please tell me what is wrong in my solution for problem B :

#include <bits/stdc++.h>
using namespace std;
#define deb(x) cout << #x << " : " << x << endl;
 
bool cmp(pair<int, int> a, pair<int, int> b){
			return a.first < b.first;
}
 
int main() {
	const int N = 105;
	int t;
	cin >> t;
	while (t-->0) {
		int n, m;
		cin >> n >> m;
		vector <int> b(N);
		vector <pair<int, int> > a(n);
		for (int i=0; i<n; i++) {
			cin >> a[i].first;
			a[i].second = i;
		} 
		sort(a.begin(), a.end(), cmp);
		for (int i=0; i<m; i++) {
			int val;
			cin >> val;
			b[val]++;
		} 
		bool flag = true;
		for (int i=0; i<n; i++) {
			int pos = a[i].second;
			// deb(i);
			// deb(pos);
			// deb(a[i].first);
			for (int j=min(pos, i); j < max(pos, i); j++) {
				if (b[j + 1] == 0) {
					flag = false;
				}
			}
		}
		if (flag) cout << "YES\n";
		else cout << "NO\n";
	}
}
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also got wrong answer during the contest. And the wrong answer was always on test 4. After the contest, I found the problem is on the cmp function. You can delete the cmp function and change "sort(a.begin(), a.end(), cmp)" into "sort(a.begin(), a.end())". Then you will get accepted. But I still don't know the specific reason until now and want to know why this type of cmp will cause wrong answer. I hope this can help you.

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

      thankyouu :) williamwangx

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

        Try changing your comp function to this:

        bool comp(pair <int, int> a, pair <int, int> b) {
            if (a.first != b.first) return a.first < b.first;
            else return a.second < b.second;
        }
        
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

" A cannot be bigger than 2a, " Proof please. (Problem D)

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

    Let's say A is bigger than 2a, then in order to get A from a, we need A — a > a add operations. No matter what B we pick, we can always use a — 1 subtract operations to get A = 1 from a, which always meet the requirement B % A = 0. So going over 2a always yields a worse answer than simply decrease a all the way down to 1.

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

For D I have different approach. I brute force C up to 2c. We know that number of divisors for numbers up to 20000 maximum is 60. So, if you prebuild all divisors for all numbers up to 20000, then for each C you can try each B (divisor of C) and for each B try each A (divisor of B). So each test is done roughly in 2c * 60 * 60 tries.

I didn't prove that C is not exceeding 2c. Is there proof? Or, perhaps hack? 71792331

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

can someone tell me why this submission got WA 71787302. and this AC 71788262. why could defining arrays in main is wrong?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    you should have defined P with size of N not M as the set of positions is in range (1 ≤ pi < n)
    your code after defined P with size of N 71849815

    sorry for my bad english

»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

In Problem B you can try the logic of Bubble sort.. 71787966

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Any good source to learn pbds?

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I made B, by using dfs

»
4 years ago, # |
  Vote: I like it -23 Vote: I do not like it

For D -> The Upper Bound of B and C should be mentioned in the problem statement.

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

    No

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

    I don't agree, it was a good aha moment for me to figure out upper bounds, and I think it is a big part of the problem.

    By the way, my weak/loose bound on $$$C$$$ was $$$4 \times 10^{4}$$$ but I took $$$5 \times 10^{4}$$$ during the contest just to be sure.

»
4 years ago, # |
Rev. 4   Vote: I like it -8 Vote: I do not like it

Why the complexity of the solution of Problem E in this tutorial is $$$O(nd)$$$. The while loop from n*(n-1)/2 to the lower bound that approximately equal nlogn. So I suspect it's complex is $$$O(n^3)$$$. (n<700) And I copy the solution written at the tutorial, and add a variant to count the time complex as below:

code

It is my input :

1
650 5000

It is my output:

4837
268511100
YES
1 2 3 4 5 6 7 8 9 ...

It seems that the complex is bigger than $$$O(nd)$$$. 650*5000=3250000 and it iters 268511100 times.

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

    could you help me please? @Kirundel

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

    Please place codes in spoilers.

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

    It seems $$$O(n * (n^2 - d))$$$, but the algorithm just runs if there is an answer.

    Therefore $$$n\log_2 n \leq d$$$ or $$$n \leq \frac{d}{\log_2 n} $$$ and the algorithm runs in $$$O(\left( \frac{d}{\log_2 n} \right) ^3)$$$ which is enough to pass. This result also matches your experiment as $$$\left(\frac{5000}{\log_2 650}\right)^3 \approx 153204056$$$.

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

    Code is O(max value possible — min value possible) per test case. If you only take cases where min value possible <= 5000 then the max possible gap is 218448 so final complexity is O(2*10^8) with pretty low constant

»
4 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Another solution for B is use DSU. We will define x and x + 1 is an edge, then we merge them . Then we sort the array A with storing the original position. We will consider all elements of A ( after sorting ), Call POS[] is a array to store the original pos, If Pos[i] < Pos[i + 1] we continue the loop, else we check if they have the same root , if not the answer is NO and we return, else the answer is YES. My solution : https://codeforces.com/contest/1311/submission/71846993

»
4 years ago, # |
Rev. 5   Vote: I like it -17 Vote: I do not like it

I can't figure out which is the editorial, the blog or the comments? :D

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

vovuh For problem F, I am not familiar with the fenwick tree coordinates compression technique. Can you elaborate a bit more on this?

The following statement in your editorial probably has something to do with this technique? add our current point to the Fenwick trees (add 1 to the position Vi in the first tree and Xi to the position Vi in the second tree).

I have some knowledge on fenwick tree but not so much with the coordinates compression technique. I assume it is needed because the input can be in range[1, 10^8] which would consume too much memory, right?

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

More clear explanation for sentence in D editorial "Then let's iterate over all possible multiples of A from 1 to 2b. Let this number be B." While we want to choose B if we choose it bigger than 2b this mean we need to have at least (b+1) operations. Except this if we just equalize the B to A at most we do b operations. Because highest value of |b-A| can be (2a-b) or (b-1) and these are smaller or equal to b because a<=b. So that we can't choose B upper than 2b.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

is there a proof for solution to E?

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

I am getting the error for testcase4 in Problem B. Please help me my code

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

It seems like for D, any reasonably tight bounds will work: here is the one I came up with (after the contest...) and a proof:

  • $$$a$$$ ranges from $$$i = 1$$$ to $$$2c$$$;
  • $$$b$$$ equals $$$ji$$$ where $$$j$$$ ranges from $$$1$$$ to $$$ji\leq 2c$$$

Complexity: $$$O(c\log c)$$$ by counting all pairs $$$(i,j)$$$ with $$$ij\leq 2c$$$ (use harmonic series).

Proof: $$$a$$$ will never be above $$$2c$$$: because instead of taking $$$a$$$ to $$$>2c$$$, $$$b$$$ to $$$>2c$$$, and $$$c$$$ to $$$>2c$$$, we could simply take $$$a$$$ and $$$b$$$ to $$$c$$$.

And for the same reason, $$$b$$$ will never be above $$$2c$$$; because the number of moves in raising $$$b$$$ to $$$>2c$$$, and in raising $$$c$$$ to $$$>2c$$$, already exceeds the number of moves in making both $$$a$$$ and $$$b$$$ equal to $$$c$$$: $$$(c-a)+ (c-b) \leq 2c$$$.

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

In problem E, what is the logic behind calculating lower bound ld?

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

For E, Can anyone explain me why the time complexity is O(nd)?

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

why is this incorrect for fourth question (D).

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

In F , what if the points start moving simultaneously at time t=0. how to solve then?

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

Can anyone explain why we need to consider only upto 2*a in problem D?

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

    If Suppose A=2a+1 then |A-a|=a+1 so better convert a to 1. So, the difference then will be a-1.

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Could anyone share the simplest way you've figured out to build that tree(in E)? Thanks in advance.

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

why in problem D the harmonic series is estimated as log n? (I would like to see the proof)

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

    One can use comparison of $$$\sum\limits_{n=1}^M \frac{1}{n}$$$ with $$$\int\limits_{1}^M \frac{1}{x} \, dx$$$

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

Problem B solution using disjoint sets

include<bits/stdc++.h>

using namespace std;

int giveParent(int x,int *parent) { if(parent[x] == -1)return x; else{ return giveParent(parent[x],parent); } }

void solve() { int n,m; cin>>n>>m;

int a[n+1],b[n+1];
for(int i=1;i<=n;i++){
       cin>>a[i];
       b[i] = a[i];
}


int parent[n+1];
memset(parent,-1,sizeof(parent));
while(m--)
{
    int x;
    cin>>x;
    parent[x+1] = x;
}

sort(b+1,b+n+1);
bool visited[n+1];
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;i++)
{
    if(b[i] ==  a[i])
    {
           visited[i]=true;
           continue;
    }
    else{
        int j;
        for( j=1;j<=n;j++)
        {
            if(b[j] ==  a[i] && visited[j] == false)
            {
                if(giveParent(i,parent) == giveParent(j,parent)){
                    visited[j] == true;
                    break;
                }

            }
        }

        if(j==n+1)
                {
                    cout<<"NO"<<endl;
                    return;
                }
    }
}

cout<<"YES"<<endl;

}

int main() { int T; cin>>T; while(T--) solve(); }

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

For problem F,while updating and querying Fenwick tree we generally isolate the last bit and the update our loop control variable as x+=(x&-x) and x-=(x&-x).However,here we are using different updating statements in the functions(pos=(pos & (pos + 1)) — 1) and (pos |= pos + 1).Can someone please explain me this.I am new to Fenwick trees. Thank you!

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

in problem A how we are geting only 1 & 2 as output .can any one please explain in easy way

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

    if a == b then obviously answer is 0,
    if a < b then we have to add a number to get from a to b, but we can add only odd numbers which is good if a is odd and we want to go to even number (o+o=e), or if a is even and we need to go to odd numbers (e+o=o), other wise we can subtract 1 from a to get to one of the above mentioned stage,
    do the same reasoning for a > b..

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

In the fourth question, we can enumerate a, B and C. the upper bound is 2 * C, which can also be crossed.

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

can anyone tell me why I am seeing O(n^2) and O(n^3) answers getting accepted in probD, here n = 10^4, how is that even possible, isn`t 10^8 too much to pass through 2 seconds limit.

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

https://codeforces.com/contest/1311/submission/76479163

Firstly, I supposed the tree as complete binary tree and used the depth sum as initial sum. I checked that if I can move any vertex down from it's original depth and if I could then did it and incremented the sum till it becomes d. I thought it would be a tle as we are running two loops. Why it isn't.

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone explain me how the time complexity of the problem D is O(nlogn) ?

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

    For each value of $$$A$$$ from $$$1$$$ to $$$2a$$$, you iterate over all possible multiples of $$$A$$$ from $$$1$$$ to $$$2b$$$. So the number of iterations is:

    $$$\sum_{A=1}^{2a} \lfloor \frac{2b}{A} \rfloor \leq {2b} \sum_{A=1}^{2a} \frac{1}{A} \leq {2b} \cdot (\log_2 2a + 1) = O(n \log n) $$$

    according to harmonic series

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

2

1 4

2 0

How is it coincide??

Anyone help please

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

Im practicing DSU and just found out that the problem B can be solved by DSU, here's my solution: 196218629, but I wonder about the time complexity of this code