thanks for quick editorial

MikeMirzayanov is that your short solution for D? Lol

Why does I got tle when I used long long in my code in D where as same code accepted when I use int.

Submission link: int-https://codeforces.net/contest/1538/submission/119078431

Submission link: long long-https://codeforces.net/contest/1538/submission/119078279

I saw F so late ugh, sucks to miss on easy points

Great contest, I solved problem C with two pointers. Calculate the total number of pairs = (n *(n-1))//2, now calculate the pairs sum < L (using two pointers) let's call it A and calculate the pairs sum > R with the same approach let's call it B. So our answer will be total pairs — (A+B). Submission

Amazing problem set

I like the solution to E, looks pretty simple, I thougt it would be much more complecated.

But binary search in G is unclear, I cannot see the trick from the formulars. Why a ternary search does not work? And how does the function work on thats result we can binary search?

N/A

Problem F is arguably easier than problem A Got stuck at A for a long time :(

My solution to C using policy-based ds. code

Editorial for D is wrong, $$$n$$$ should be the sum of exponents of prime divisors instead of the number of prime divisors.

Massively overcomplicated solution for F. This passes.

Why is the provided implementation for F so long and far-removed from the description? For example, my short implementation is here, and is immediate from the description in the editorial: 119035674

I feel dumb for getting WA 4x, only because of forgetting to use long long instead of int at problem C :v

Less cumbersome implementation for D. code

i think naitikvarshney use invalid input for hacking solution of problem C. he have already hacked 95+ solution(including me). :+(

Thanks for such an interesting contest!

Looks like the code for problem D is wrong , Please correct it , the main issues are in Solve function where there are brackets but no for loops . MikeMirzayanov

I kind of applied the same logic in D, but not able to pass the tests. Can anyone tell me what am I missing link

We can also use linear programming optimization for problem G to solve it in O(1).

For 1538G - Подарочный набор following solution pass tests. We have following set of restrictions

• n*a+m*b <= x
• m*b+n*a <= y
• n+m -> max
• n, m are integers

Forget for a moment about last requirement (n, m are integers). Then, first two restrictions is basically region on n,m coordinate plane. And n + m is cost of each point within allowed region. Then, we can draw lines of fixed cost D: it's all point with cost D = n + m. Cost = 1 is line 1 = n + m. Cost 2 is line 2 = n + m and so on. It's easy to see that all of them are parallel, and when you increase D you actually move line perpendicular to it. Given line with cost 0 is 0 = n + m we know that cost of any point is actually distance to this line (n + m = 0).

So, we want to find point within region with highest distance to the line n + m = 0. What about region we have? It's convex polygon. Thus, largest distance to the line is equal to distance to some vertex of our polygon. So, if we forget about integer n, m, we can pick this vertex as answer. This is actually explanation how linear programming works in 2D space.

What can we do with integer n and m? Well, I just did hack: round n in arbitrary direction and tried few other integers around and this passed. 119052049 The question is: is it valid solution or is there counter test?

IN G, shouldn't the inequalities be x >= a*k + b*(n-k) and y >= a*(n-k) + b*k. Also, the second equation in the four-set of equations should have y and not x?

I think there's no need of keeping length in E, because we can handle special cases by checking if the prefix or suffix's length is less than 3.

In G tutorial it should be, x >= a⋅k+b⋅(n−k) y >= a⋅(n−k)+b⋅k and similarly, the next two equations will be changed accordingly. Supermagzzz correct it.

Can someone tell me why my code is failing for problem C. It is the same logic as the editorial only with an extra condition. 119012335

Could someone plz tell me as of why this submission of mine getting TLE whereas this one is passing?

The second submission uses sieve and map to store the values, whereas mine uses normal sieve. Still contrary to what should have occured, he received AC.

I have even seen submissions having the same implementation as of mine, but passing the constraints easily.. Why is this happening?

Editorial's code for D is an eyesore

My solution to D is simpler I think

    int pfact(int x)
    { int cnt=0;
      if(x%2==0){while(x%2==0)x/=2,cnt++;}
      for(int i=3;i*i<=x;i+=2)
        if(x%i==0){while(x%i==0)x/=i,cnt++;}
    if(x>1)cnt++;
    return cnt;

    }
        int m,n,x,y,z,k,t;

        int main()
        {

        ios_base::sync_with_stdio(false);

        cin>>t;

        while(t--)
        {
            cin>>x>>y>>k;
            int xx=pfact(x);
            int yy=pfact(y);

            if(xx+yy<k) cout<<"NO\n";
            else
            {
              
              if(x==y&&k==1)cout<<"NO\n";
              else if(k==1&&x!=1&&y!=1&&(x%y!=0&&y%x!=0))cout<<"NO\n";
             else cout<<"YES\n";
            }

        }

        return 0;
        }

Got thrown into another dimension while solving E.

For problem G I have some $$$O(1)$$$ solution.

First, think about how we can solve the problem easily when constraints are $$$10^5$$$.

($$$a <= b$$$, otherwise swap them) ($$$x <= y$$$, otherwise swap them)

To solve this version we can easily brute force step by step and while we can create a new gift we will decrease $$$b$$$ from the higher one and $$$a$$$ from the remaining one this is optimal and proof left as an exercise to the reader.

But when constraints are $$$10^9$$$ we can't brute force so let's look at this solution and see what happens.

At first, let's assume $$$y - x <= b-a$$$ in this situation if we apply our brute force algorithm at each step higher one will change because $$$y-b <= x - a$$$ and their difference also won't exceed $$$b-a$$$ because $$$x-a-(y-b) <= b-a$$$,$$$x-y <= 0$$$ is true so for this type $$$x$$$ and $$$y$$$ we can solve problem with

$$$(x/(a+b))*2 + val$$$, $$$val$$$ is 1 if at the last we can't decrase $$$(a+b)$$$ from $$$x$$$ and $$$x >=a, y >= b$$$

And while $$$y-x > b - a$$$ this means we always decrease $$$b$$$ from $$$y$$$ so we can handle this until $$$y - x <= b-a$$$

Here is my implementation 119099472

Is 10^4 * sqrt(10^9) complexity code acceptable everytime?

For problem G, my solution is transfer the problem into an ILP problem, that is:

Treat it as a LP problem and then use Simplex to get the value of $$$x_1$$$ and $$$x_2$$$ when $$$z$$$ is maximized. Since $$$x_1, x_2$$$ could be float numbers, and I guess the answer for ILP problem will be around $$$(x_1, x_2)$$$, so I search a few integer points around $$$(x_1, x_2)$$$.

(FST Warning

For bugaboo D, we can find all the primes till 1e5. There are less than 1e4 prime numbers in this range. Now, for each a and b, we check the divisibility with this list of primes. If none of the primes till 1e5 divide a, it means that 'a' itself is a prime number. Because any factor more than 1e5 would need a smaller factor less than 1e5, because 1e5*1e5 = 1e10, which exceeds the constrains on a and b. UPD — My code 119080458

119103856
Can any body hack my submission for Problem G ?
I didn't use binary search.

Supermagzzz, MikeMirzayanov, I think there is a typo in the tutorial of problem G: Maybe it should be $$$\frac{(y−a⋅n)}{b - a} ≤ k$$$ rather than $$$\frac{(x−a⋅n)}{b−a} ≥ k$$$, and $$$\frac{(x−a⋅n)}{a - b} ≥ k$$$ rather than $$$\frac{(x−a⋅n)}{a−b} ≤ k$$$.

I can hardly believe this is the difficulty of div3, but the problem is very good, I like it very much, thank you for your tutorial.

Is there a wrong about problem G in Codeforces Round #725 (Div. 3) Editorial. In the tutorial (x−a⋅n)b−a≥k may be (y−a⋅n)b−a≥k

Can anyone tell which corner case I am missing in the solution to problem D? I am getting WA on token 1021 of test case 2. Here's my link 119065848. Thanks.

use Java in C, about Arrays.sort()

AC

Long[] arr=new Long[n];
Arrays.sort(arr, Long::compare);

TLE

long[] arr=new long[n];
Arrays.sort(arr);

Can anyone please point out mistakes in D's code? 119088308 It's failing on the 5053rd token in test case 2. UPD: Got it, thank you!

I got a tle in D because of using long long instead of int.

Can someone provide me the test case of G where my solution fails 119117297

https://codeforces.net/contest/1538/submission/119118611

This is my dp solution of problem G . It is giving runtime error on testcase 5 that is for large x ,y and small a,b . could someone please tell the possible reasons for the error so that I do not repeat the same mistake again in future contests . Please .. Thanks in advance..

Seriously I didn't liked the implementation of D given in the editorial. I simply used some tricks to speed up the sqrt(max(a,b)) solution and it was good enough to pass the tests. :)

Here's the link of my submission : 119025249

In problem F, I think solve two related problem which the number of changed digits in $$$[1, l]$$$ and $$$[1, r]$$$ is better. Than, we can use a simple subtraction to get the answer.

If we focus on problem as $$$[1, x]$$$, we can find a way to calculate the ans: first, each digit can provide [ $$$11 \dots 11$$$ (the number of $$$1$$$ is $$$b$$$) $$$ * 10^b - 1$$$ ] changes ($$$b$$$ mean the current number of digits), than, we add $$$n - 1$$$ to the result, n is n-digits, finally, we get the correct answer.

For example, to problem $$$[1, 5678]$$$, calculate detail is: $$$(5 * 1111 - 1) + (6 * 111 - 1) + (7 * 11 - 1) + (8 * 1 - 1) + (4 - 1)$$$.

The logic of this way is the same as editorial. Here is my code, this may be clearer than my comment.My Code

I think that the implementation of the problem D solution is complicated! I have implemented it in a simpler way. Here is my code:119017802

Supermagzzz why are we taking only a<b in 1538G - Подарочный набор?

Supermagzzz why are taking only a<b in 1538G - Gift Set ?

can anyone tell whats wrong in my code for C in given input for 4th test case it is giving ans 0.

In problem G, why both of the equation is 1. x≤a⋅k+b⋅(n−k) 2. y≤a⋅(n−k)+b⋅k instead of x>=a⋅k+b⋅(n−k)

y>=a⋅(n−k)+b⋅k ? MikeMirzayanov

In problem G's solution, if I don't write the floor function while calculating ll right and instead write it as ll right=((x — m * b) / (a — b)), then why am I getting wrong answer. The integer division should give me the floor value, then why are we using floor function explicitly. Can someone help. Thank you.

Questions about D floor and floorl What's the difference and 1.0l?

Can anyone tell me why this 119163197 for D is giving tle and not this 119163156

The editorial for G seems to be incorrect. The second reordered equation is given as (x−a⋅n)b−a>=k but it should be (y−a⋅n)b−a<=k in my opinion.

Also, I can't understand why we have used greater than or equal to in the first two equations. Can someone explain this part to me please? I think the equations should be : x>=a⋅k+b⋅(n−k)) and y>=a⋅(n−k)+b⋅k

In problem G editorial i feel it should be x>= a*k + b*(n-k) similarly for y y>=a*(n-k) + b*(k) bcs x and y should have sufficient candies.I would be very happy if someone correct my intuition.

Please can anybody find out my mistake in problem D:

My logic is to keep dividing a by 2 if it is even and increase count similarly keep dividing a by all odd numbers and increase count. Similar thing I will do for b. This count will be the maximum times I can divide a and b to get a=b=1.

In my code max==2 is for the case when both a and b are prime numbers.

My submission:https://codeforces.net/contest/1538/submission/119194346

For G I felt compelled to speak about it.

My idea for the problem is nearly the same till the part of binary search on the max answer.

What I did next was since $$$a \ge b$$$ therefore an expression like $$$ap + bq$$$ where $$$p + q$$$ is a fixed value would yield a greater result for higher value of $$$p$$$ and therefore I decided to do another binary search on finding out the pair value $$$(p,q)$$$ which would cause the expression $$$ap + bq$$$ to be just below $$$x$$$ inclusive (as mentioned in the problem). This would cause the expression $$$aq + bp$$$ to be least and that's pretty much what we want to do since $$$aq + bp \le y$$$.

My idea uses another log in time complexity due to running binary search within binary search but I found it to be a lot lesser troublesome in terms of implementation against using floor or ceilings and therefore I decided to comment on G.

Link to my solution:- https://codeforces.net/contest/1538/submission/119120664

I don't understand why E had very few submissions. Wasn't it simple bruteforce and hashing? btw I did in python.

It seems like the editorial on problem F is incorrect. The inequalities should be: $$$ x \geq k.a + (n-k).b$$$ and $$$ y \geq k.b + (n-k).a$$$. Hope the author correct it.

Can someone tell me why does the binary search in problem G code work? I'm not very experienced with binary search. Suppose we only have three possibles values right now, [1,2,3], and 2 satisfies the if condition. Then, we update the interval to [2,3]. The code stops here returning 2 as the answer. Why doesn't it check 3 too? Can't it be a posible better solution?

Can anyone tell me why i am getting memory limit exceeded with my code in python forgive me if i did a big mistake . https://codeforces.net/contest/1538/submission/119263670

who have better solve in problem D? i want to know, i can't understand MikeMirzayanov's solve in D...

plase easy write to problem D?i can't understand.

I have tried writing solutions in Java for this(I'm not familiar with it, like I am with C++).

Could we have a list of tips&tricks to speed up our solutions? I have had many issues with TLE.

So far I found: - Scanner is not always fast enough to get Accepted - same with Arrays.sort - long is very slow

Experience: I wrote the same code for problem C like in the official solution, but apparently Arrays.sort gives TLE, even after I change the algorithm after sorting to an O(n) instead of O(nlogn).

In problem D, I managed to write a solution to get accepted, but after changing long to int the solution goes from ~1100 ms to ~500ms. Lots of TLE before. If I use int, even unoptimized solutions pass(reads with Scanner, factorization without precomputing primes or even going through all even numbers as possible factors).

Also, my lack of experience with Java showed in other ways: - I had to implement swap of two variables manually(I was not able to find the library version) - I had to implement upper bound and lower bound manually, again I could not find the library version - I do not have a fast, optimized read/write class to copy/paste in my solution(frankly, I don't even know which one would that be, there seem to be many options).

.

Can anyone explain what floorl and ceill are in the solution of problem G. And is 1.0l used to convert to float like 1LL/0LL is used to convert to long long. Thanks in advance!

where the wrong in that ?? 128818547 //D

where the wrong in that ??

128818547//D

Does anyone know why this (145191446) solution fails for problem G?

I implemented the solution for problem D, but I got WA. Could someone help me figure out where my code breaks?

145908397

In problem G I think Inequalties should be x≥a⋅k+b⋅(n−k) y≥a⋅(n−k)+b⋅k

I am facing an issue in D problem 1538D - Еще одна задача про деление чисел when I use int the test case passes but on using Long Long it gives TLE I don't understand how it is creating such a big difference.