Supermagzzz's blog

By Supermagzzz, history, 4 years ago, translation, In English

1538A - Stone Game

Author: MikeMirzayanov

Tutorial
Solution

1538B - Friends and Candies

Author: MikeMirzayanov

Tutorial
Solution

1538C - Number of Pairs

Author: MikeMirzayanov

Tutorial
Solution

1538D - Another Problem About Dividing Numbers

Author: MikeMirzayanov

Tutorial
Solution

1538E - Funny Substrings

Author: MikeMirzayanov

Tutorial
Solution

1538F - Interesting Function

Author: Supermagzzz, Stepavly

Tutorial
Solution

1538G - Gift Set

Author: MikeMirzayanov

Tutorial
Solution
  • Vote: I like it
  • +55
  • Vote: I do not like it

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

thanks for quick editorial

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

MikeMirzayanov is that your short solution for D? Lol

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

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

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

    add high rated friends xd

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

      how will that help?

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

        high rated people are fast, so you can get an idea of which question to solve next. you can also check problem page for no. of solves but I check standings more so..

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

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

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

    can you please help me why is my code giving tle. i implemented lower and upper(well basically upper--) and from i=0 to i=n i calculated how many to right satisfy the criteria.submission edit: this is the submission not the above

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

    I did solve with two pointers directly (almost). I count all valid pairs (i, j) and (j, i) then subtract valid (i,i) and divide by 2. 118994288

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

      How does the condition l<=2*v && 2*v>=r help in finding valid(i,i)??

      Can you please elaborate.

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

      Oh, never mind. Got it! Sorry for the trouble.

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

Amazing problem set

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

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?

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

    Pretty sure a ternary search doesn't work because function isn't strictly increasing then decreasing, but feel free to correct me if I'm wrong.

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

      In my understanding there are two lines, and the optimum is reached where they cross. So it is non decreasing until that point, and non increasing afterwards.

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

        u can binary search for the maximum number of gift sets. Let a < b and diff = b-a . Let the number of gift sets equals n, n is valid if and only if we can put n items which size = diff into 2 knapsacks which sizes = x-(a*n) and y-(a*n) https://codeforces.net/contest/1538/submission/119046681

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

          I did read some texts, watched a video... but still do not get how/why binary search works here. The code inside the while(l<r) loop looks completly arbitrary to me.

          Can you explain why it works, or how it works?

                      int m = r-(r-l)/2;
                      int ra = a-(x*m), rb = b-(x*m);
                      if(ra/temp+rb/temp >= m) l = m;  
                      else r = m-1;
          
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    ternary search works but you have to use real numbers https://codeforces.net/contest/1538/submission/119051522

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

      That is what I tried to implement in my first submission Seems there is some implementation issue, maybe caused by rounding problems.

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

        I should have been clearer what I extended was the codomain, not the domain.

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

    I just noticed by the way

    Div3 is supposed to be unrated for anyone who "have a point of 1900 or higher in the rating."

    You do have such a point. But you gained rating in round 719

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

      Nah, you mix up two different things.

      It is rated for people up to 1600, current rating. And you are trusted up to 1900. Also current rating.

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

        Yeah... my bad

        For some reason I believed that it is unrated for anyone above 1600 now or 1900 any time in the past.

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

    It has a greedy solution if you're interested. first take the max(a,b) from max(x,y), and min from min. once they cross each other, or are equal,take sizes alternately like (b,a) (a,b). the submission is not clean, but it works. link

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

N/A

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

    division is done because the same pair will be counted twice and not sure but the condition checks that if we should not count the same index value as we should have two value from different index

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. While performing binary search for the numbers that fulfill the condition of a[i]+a[j]>=l && a[i]+a[j]<=r, it may occur that the number itself also fulfills this condition .So to resolve this we check if the number itself fulfills the condition ( a[i]+a[i]=2*a[i] ) and if it is so we remove one pair.

    2)This is done because in the question it is mentioned that i<j i.e i is always less than j , however in our code we are unable to check for this condition so for values of i>=j also the pairs are calculated. This means that all pairs are counted twice. To remedy this we divide our final ans by 2.

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

    learn about lower_bound and upper_bound !! great stuff imo!

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

    To better understand this try thinking like this:

    1. Sort the array

    2. Now for each index, think of two pointers on the right:

    3. to get left limit substract l - v[i], similarly to get right limit r - v[i]. (imagine to get sum as l we have to get numbers greater than or equal to left limit and to get sum as r we have to get numbers upto right limit.

    4. lower_bound and upper_bound for perfect for this as they get these values in log(N) time.

    5. after getting values check for extreme cases and also we dont want to check for previously calculated values, (keep between i+1 and n-1)

    6. count numbers in the range of left limit and right limit by substracting their indices.

    7. sum up all to get final answer.

    void solve (){
      int64 n,l,r,ans=0;
      cin>>n>>l>>r;
      vector<int64>v(n);
      for(auto&i:v)cin>>i;
      SORT(v);//step 1
      for(int i=0;i<n-1;i++){
        //step 2
        int left=l-v[i];//step 3
        int right=r-v[i];
        auto lower=lower_bound(all(v),left);//step 4
        auto upper=upper_bound(all(v),right);
        int low=i+1,upp=n-1;
        int lowpos = lower-v.begin(); //getting index from position
        int upppos = upper-v.begin()-1; //getting index from position
        if(lowpos>low)low=lowpos;//step 5 for lower limit
        if(upppos<upp)upp=upppos;//step 5 for upper limit
        //while(low<n && v[low]<left)low++; 
        //while(upp>i && v[upp]>right)upp--;
        //we can also get this by linear traversing but it takes
        //but it takes `O(N)` time
        //dont count for current index if no numbers exist for current number
        if(low==n)continue;
        if(upp<=i)continue;
        ans+=upp-low+1;//step 6 count sum
      }
      cout<<ans;
    }
    

    Submission link

    check this link to understand more about upper and lower bounds.

    Now answer to your 1st Question: During lower_bound we may also count the current number as 2*v[i] as lower limit but the question says i not equal to j (take different indexes). Same applies to upper limit

    Now answer to your 2nd Question: In my solution I have discarded previously calculated values, by keeping lower limit as i+1. But in the editorial OG has calculated all the numbers (all the pairs) for each index. That means they have been counted twice. Hence divide by 2.

    Hope its worth a vote :)

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

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

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

My solution to C using policy-based ds. code

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

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

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

    That's the same thing, since we count ALL prime divisors, not just distinct ones.

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

      Well, probably you can argue that we define prime divisors of a number as a multiset, but it is really weird (at least for me).

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

        I fully agree to you.

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

          One thing seems weird in D. if a==b then shouldn't k be equal to 0 ? so like since it is not mentioned that when they are equal we stop... maybe this is the reason, but dont we sort of generally stop when we reach the condition a==b? in any other q for eg

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

            No k shouldn't be equal to 0 , as you can still divide no.s from a and b if a==b

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

Massively overcomplicated solution for F. This passes.

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

    hey just wanted to know whether problem F was a digit dp problem ??

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

      I complicated it so much and solved it using digit dp

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

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

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

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

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

    Hope it helps :p

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

      Its the same, either use "#define int long long" to stop getting WA but then you will get TLE on particular questions or try to remember using long long according to constraints and get WA sometimes. I prefer second, improves "attention" for other twists in other type of constraints too.

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

Less cumbersome implementation for D. code

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

    Are you asking for it? here

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

      I had a doubt- how to decide the upper limit of the prime numbers we need? (1000009) in your case.

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

        Its sqrt(10^9) in this case, I took 10^5 just to be safe.

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

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

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

    Your code got hacked due to Arrays.sort() function which in worst case have O(n^2) time complexity.

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

      Another problem with Java Arrays.sort() :/

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

      Is it really necessary to hack all your victims during the hacking stage to disqualify their solutions? Aren't successful hacks used as a part of system tests anyway? Or am I missing something?

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

      What kind of sort in Java is guaranteed n log n?

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

    buy a new laptop and start with C++

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

Thanks for such an interesting contest!

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

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

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

    Here is an easy to understand solution 119087228.

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

      Thanks , I too had O( T * sqroot( Max(a,b) ) solution but it TLEd as it had a bit bigger constant factor.

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

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

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

    Your code marked all of the cases with $$$a$$$ equals $$$b$$$ as a no. But actually, there may be some cases when $$$a$$$ = $$$b$$$ and the answer is yes. For example:

    $$$1$$$

    $$$2$$$ $$$2$$$ $$$2$$$

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

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

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

For 1538G - Gift Set 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?

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

    Integer Programming in general is NP-hard. Just searching few points around the linear programming solution does not guarantee (integral) optimal solution.

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

    This should be correct. In this particular case, as we move away from the intersection point, we get closer to the $$$n + m = 0$$$ line, since one of the lines has a slope less than $$$n + m = 0$$$ and the other has a slope greater.

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

      It's more like intuition instead of formal proof. I would like to have formal proof, and here it is (at least some sort of).

      Messy long proof

      With this proof code becomes a bit easier: 119096819 (three points enough)

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

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?

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

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.

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

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.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like 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

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

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?

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

    Now what i did is- changed my long long to int data type and got AC plus a near about 1/3 execution time.. I have never seen so much of a difference just because of the change of data types. :(
    Could someone please give an insight on the same.

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

      Did you try it with a c++17 64 bit compiler? It is available on codeforces. Calculations with long long or long double data types are a lot slower.

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

        Ya I did so
        Result remains the same but.
        This is the submission

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

Editorial's code for D is an eyesore

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

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; }
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    sadly in contest I used long long it barely passed so I'm a little scared

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

      thanks for telling, I will try to hack:)

      UPD : I cannot, it works fine.

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

        You're welcome it's better than waiting for tomorrow to know that it's TLE :P

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

          Can you explain this line: if(x > 1) cnt++ Is this to include 1 as a divisor

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

            No in any number there could be one prime factor bigger than sqrt like 11 without this line you won't count 11 as a factor

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

Got thrown into another dimension while solving E.

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

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

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

    decrease b from the higher one and a from the remaining one this is optimal and proof left as an exercise to the reader.

    Can someone please prove it? I've done the same thing but couldn't prove it.

    EDIT: Never mind, got it now.

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

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

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

    I guess it's $$$10^4 \cdot \dfrac{\sqrt{10^9}}{\log(10^9)} \approx 30\ 000\ 000$$$ if you only check divisibility from primes.

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

      Actually, $$$10^4 \cdot \sqrt{10^9}$$$ also passes 119014291 if you don't do anything extra.

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

        Yeah, my code has passed too, but with 1544 ms runtime. I am little scared that will it pass on system tests or not :(

        It got passed, yay :)

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

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

$$$ max. z = x_1 + x_2 \\ s.t. \left\{ \begin{array}{ll} ax_1 + b x_2 \le R\\ bx_1 + a x_2 \le B\\ x_1, x_2 \text{ are non-negative integer} \end{array} \right. $$$

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

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

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

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

    how to find the sequence of primes <1e5 : for(i -> 1e9)????

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

      We only need primes till 1e5 not 1e9. You can use sieve() and then store the primes in some vector.

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

        i did that but wrong on test 3 , I don't understand why I'm wrong, you can check help me, please

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

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

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

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

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

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.

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

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

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

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    if(k==1&&a!=1&&b!=1&&(a%b!=0&&b%a!=0))cout<<"NO\n";
    
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bro, I covered all corner cases still getting WA, c=this case also I have covered. Can you point out any possible case I am missing. Thank you.

      int p=max(a,b),q=min(a,b);
      
          if(p%q==0 && k==1) {
              cout<<"YES"<<'\n'; continue;
          } 
          if(factors(p)+factors(q)>=(ll)k && k!=1){
              cout<<"YES"<<'\n'; continue;
          }
          else cout<<"NO"<<'\n';

      Submission link: https://codeforces.net/contest/1538/submission/119430768

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

        In your factors function you should write while(a%2==0) instead of while(a%2!=0) so it's just a typo not logic mistake and you may get tle because in for loop you are writing i++ instead of i+=2 this i++ makes dividing a by 2 in the while loop pointless

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

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);
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can anyone tell, why it happens. even I am facing same issue, why its TLE while using long[] and passes on using Long[] ?

    Confused. Need help

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

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!

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

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

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

    Why, using long long would increase memory only and TLE could be understandable when recursions were used, but here no such cases are there. Please explain... I also submitted with long long only but it passed...119115670

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

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

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

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

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

    I think it is giving Runtime error because for large values of x and y and a and b being small, the size of map would be greater than INT_MAX so you would not be able to store that many values and it is giving RE.

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

    Let's say we get the range [3.5,5.5] because we're getting integers

    So the left interval is going to be 4, and the right interval is going to be 5

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

    Casting to an int will truncate toward zero. $$$floor()$$$ will truncate toward negative infinite. So, $$$int(-0.9) = 0$$$ and $$$floor(-0.9) = -1$$$

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

      Ok. So, can we say that, since the value here can be negative as well that is why we need to use floor. If it was guaranteed that the result will always be positive then we don't need to use floor function.

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

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

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

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

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

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

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

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.

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

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

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

    If a == b and a is not prime then you are setting min = 1 but atleast 2 division operations will be required in this case.

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

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

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

    cool idea...But I didn't understand how the idea of maximizing the value p(in second binary search) gives optimal answer?

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

      You want to make sure the first expression is $$$ \le x $$$ and second expression is $$$ \le y $$$

      so if u maximize the first expression as you can to be just below $$$x$$$ it would cause the second expression to go as low as possible.. and that's what we want because it's always better to take a lower value for any expression.

      Actually you can also do that other way around maximize the $$$q$$$ but then you have to run binary search for maximizing the second expression. ($$$aq + bp$$$)

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

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

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

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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like 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?

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

    In the editorial solution, l and r are taken as such that l <= n < r (where n is the req solution). So u don't need to check at r. U can look this

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

      So updating r = m and not checking it as a solution is the same as updating r = m-1 and do check it. Got it. Thanks!

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

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

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

    Memory limit exceeded doesn't mean your code is wrong. The strings won't fit in some tests. Note that the input can be a first line with := and then 49 lines like x = x + x, so the string will need more than 2**49 bytes, and I believe 256MB to be 2**28 bytes, which is the limit for the problem.

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

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

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

    There are some observations.

    1. Any number can be written as a product of its primefactors, and is divisible by all those primefactors, and all products of a subsets of those primefactors
    2. We can make the number a or b equals 1 in one operation, by choosing c equals to a or b, so we can make them both equal 1 in two operations.
    3. We can make the numbers a and b equal in one operation if a divides b or b devides a.
    4. The most operations we can do on a number until it equals 1 is the number of primefactors it has.

    From those rules above we can find a minimum number of operations, and a maximum number of operations. If k is in between them then ans="Yes".

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

      Sorry, didn't get this part. Why is this true?

      If k is in between them then ans="Yes".

      EDIT: I took one example and it's clear now.

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

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).

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

.

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

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!

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

where the wrong in that ??

128818547//D

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

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

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

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

145908397

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

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

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

I am facing an issue in D problem 1538D - Another Problem About Dividing Numbers 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.

PS:

INT: passed test cases i.e. Accepted (1559ms) 169586396

LONG LONG: TLE on 6th test case (2000ms) 169586970

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

How to calculate sum of exponents of prime divisors of a in problem D ``

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

For F, I don't know if its correct or not...I was trying to find a dp solution, here is my dp state that i defined, dp[i][j] refers to the maximum number of changes if we start from ith digit and have j number of operations, so for i=0 to i=8 dp[i][j] = dp[i+1][j-1] and for i=9 dp[i][j] = dp[0][j-1] + dp[1][j-1] as 9 would give 0,1', and then we can reduce one operation form there, base case would be dp[i][0]=0 anddp[i][1]=1 for i=0-8 and for i=9 dp[i][1] =2'.

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

why does the solution given in ed, work for f

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

I can solve G in O(1) link: 279042769