Блог пользователя Supermagzzz

Автор Supermagzzz, история, 4 дня назад, По-русски

1538A - Каменная игра

Автор задачи: MikeMirzayanov

Разбор
Решение

1538B - Друзья и конфеты

Автор задачи: MikeMirzayanov

Разбор
Решение

1538C - Количество пар

Автор задачи: MikeMirzayanov

Разбор
Решение

1538D - Еще одна задача про деление чисел

Автор задачи: MikeMirzayanov

Разбор
Решение

1538E - Смешные подстроки

Автор задачи: MikeMirzayanov

Разбор
Решение

1538F - Интересная функция

Автор задачи: Supermagzzz, Stepavly

Разбор
Решение

1538G - Подарочный набор

Автор задачи: MikeMirzayanov

Разбор
Решение
Разбор задач Codeforces Round #725 (Div. 3)
 
 
 
 
  • Проголосовать: нравится
  • +55
  • Проголосовать: не нравится

»
4 дня назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

thanks for quick editorial

»
4 дня назад, # |
  Проголосовать: нравится +77 Проголосовать: не нравится

MikeMirzayanov is that your short solution for D? Lol

»
4 дня назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.com/contest/1538/submission/119078431

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

»
4 дня назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
4 дня назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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 дня назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Amazing problem set

»
4 дня назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 дня назад, # ^ |
        Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

        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.com/contest/1538/submission/119046681

        • »
          »
          »
          »
          »
          3 дня назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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;
          
          • »
            »
            »
            »
            »
            »
            3 дня назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            I misread the input and used a, b as the total number of candies and x, y as the number of candies per gift set . But the logic remains the same

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    2 дня назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
    click
»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

First of all Thank You for the Editorial !!!

I am facing difficulty in understanding Problem C Number of Pairs Editorial. In the code attached I could not get the significance of the following lines

if (l <= 2 * v[i] && 2 * v[i] <= r) Why we are checking for this particular condition ?

cout << ans / 2 << "\n"; Why are we dividing our final answer by 2 ?

  • »
    »
    4 дня назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    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 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Got it !!! Thanks a lot :)

    • »
      »
      »
      3 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks

    • »
      »
      »
      47 часов назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Everything makes sense, but theres just one thing I don't get and it would be a great help if you would explain it to me: Taking the example of v=1 1 2 5 5 10 and v[i] = 5 and i = 3, and l = 9, r = 13, We have r-v[i] = 8 & l-v[i] = 4, and the upper_bound(r-v[i]) = 5 and lower_bound(l-v[i]) = 3. So instead of adding in 3 elements in the range of 4 — 8, why are we adding 2 elements? And how does this work?

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    learn about lower_bound and upper_bound !! great stuff imo!

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Basically in Problem C we have to find all the pairs in range L to R whose sum is in this range .

    So what we can do is that we can find all the pair till L-1 and all pair till R.

    now we can subtract the pair found and get our desired result

    in order to find the pair till sum x we can follow a two pointer technique whose algo is :

    step 1) assign low = 0 , high = n-1 step 2) while ( low < = high ) will be our bounding condition step 3) if sum at a [ low ] + a[ high ] < x then pairs between low and high would be our ans now we increment our low pointer step 4) in case sum at a[low] + a[high ] > x we decrement our high pointer

    the simplified solution is here : 119093049

    please see : you can use PBDS for the same

  • »
    »
    4 дня назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    I can't understand it either, but I wrote it myself according to the explanation:

    int n, l, r;
    int a[maxn];
    
    void solve(){
        read(n, l, r);
        rep(i, 1, n) read(a[i]);
        sort(a + 1, a + n + 1);
    
        int res = 0;
        rep(i, 1, n){
            int A = upper_bound(a + i + 1, a + n + 1, r - a[i]) - (a + i) - 1;
            int B = upper_bound(a + i + 1, a + n + 1, l - 1 - a[i]) - (a + i) - 1;
            // debug(A, B);
            res += A - B;
        }
        cout << res << endl;
    }
    

    Look at the complete code

  • »
    »
    3 дня назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    2 дня назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    We are checking if the pair (v[i],v[i]) is valid I.e v[i]+v[i] lies in the range.If it is then answer must be decreased by 1 because we would have included that case when we are finding the upper bound. And ans/2 is because we would have included both the pairs (a,b) and (b,a). So the actual answer is 1/2 of what we have obtained in the for loop.

»
4 дня назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My solution to C using policy-based ds. code

»
4 дня назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

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

    • »
      »
      »
      4 дня назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      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 дня назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        I fully agree to you.

        • »
          »
          »
          »
          »
          9 часов назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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

          • »
            »
            »
            »
            »
            »
            8 часов назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 дня назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I thought the same way

»
4 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

deleted

»
4 дня назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

Massively overcomplicated solution for F. This passes.

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 дня назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    #define int long long
    

    Hope it helps :p

    • »
      »
      »
      4 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      it help in 1e9 integer overflow

  • »
    »
    2 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    did the same mistake ;;

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Less cumbersome implementation for D. code

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

anyone can point out mistake in F ? 119076961

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 дня назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Problem C video Editorial (using Binary Search) link : https://youtu.be/_2-iretTWqc

»
4 дня назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Thanks for such an interesting contest!

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Here is an easy to understand solution 119087228.

    • »
      »
      »
      4 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I was initially doing same as yours but getting TLE(on test 6). Later came to know we have to use prime seive to get max count in O(T*log(max(a,b)) Otherwise, time complexity would be O(T*sqrt(max(a,b)). I wonder how yours got accepted. XD

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could solve first 2 problems, hoping to improve.

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks, missed that condition, just now realized that if K>1 and a and b are equal then also the answer is yes.

»
4 дня назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 дня назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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?

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 дня назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    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 дня назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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 дня назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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 дня назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E problem seemed very tricky

»
4 дня назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

For C. I use Java, and write my own binary search, but got TLE?

public class TaskC {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int l = in.readInt();
        int r = in.readInt();
        int[] ary = in.readIntArray(n);
      **  Arrays.sort(ary); // O(n^2)  very bad**
        long res = 0;
        for (int i = 0; i < n; i++) {
            int low = lowerBound(ary, l - ary[i]);
            int up = upperBound(ary,r  - ary[i]);
            res -= low;
            res += up;
            if (l <= 2 * ary[i] && 2 * ary[i] <= r)
                res--;
        }
        out.printLine(res / 2);
    }
    int lowerBound(int a[],  int x) {
        int l= -1,r= a.length;
        while(l+1<r) {
            int m=(l+r)>>>1;
            if(a[m]>=x) r=m;
            else l=m;
        }
        return r;
    }
    int upperBound(int a[],  int x) {
        int l= -1,r= a.length;
        while(l+1<r) {
            int m=(l+r)>>>1;
            if(a[m]<=x) l=m;
            else r=m;
        }
        return l+1;
    }

Update: Got it.

The sort() is O(n^2).

I put numbers in List and use Collections.sort(). it works.

»
4 дня назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 дня назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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 дня назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 дня назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Editorial's code for D is an eyesore

»
4 дня назад, # |
Rev. 4   Проголосовать: нравится +2 Проголосовать: не нравится

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 дня назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Got thrown into another dimension while solving E.

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here D editorial solution is very complex.....
Over the head... Btw It's not so complex how he show it!

»
4 дня назад, # |
Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

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

  • »
    »
    3 дня назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I don't understand the official solution, but your method is really simple and easy to understand.That’s amazing:)

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 дня назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

thanks for quick editorial

»
4 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think the problems should be sorted by increasing difficulty

»
4 дня назад, # |
Rev. 10   Проголосовать: нравится +12 Проголосовать: не нравится

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 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    if(k==1&&a!=1&&b!=1&&(a%b!=0&&b%a!=0))cout<<"NO\n";
    
    • »
      »
      »
      7 часов назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.com/contest/1538/submission/119430768

      • »
        »
        »
        »
        100 минут назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I solved C using 2 hash maps . One that stores the difference of the minimum sum and arr[i] and second that stores the difference of maximum sum and arr[i]. and then for each arr[i]. Found the number of integers in the array so that they are between low[arr[i]] and high[arr[i]]. But I was not sure if it was fast enough to pass the system tests. I would be grateful if anyone can hack it!

[EDIT] here is the link to the solution 119064844

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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);
  • »
    »
    2 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      2 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You can take a look at the Java source code for Array.sort(). You will find that when using long[] it is DualPivotQuicksort, and Long[] is TimSort. In the worst case, DualPivotQuicksort is still O(n^2), while TimSort is O(nlogn).

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    exactly, me too!

    but while practice, just figured it out!

    Converted it to int and it got AC

  • »
    »
    3 дня назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Such a nice contest with excellent editorial.

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 дня назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.com/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..

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 дня назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      is there a size limit for storing elements in a map ? also , could you please tell is there a way to fix this problem?

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Lightning fast editorial.Kudos to the team

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Добрый день! Подскажите, пожалуйста, как-то можно посмотреть тесты к задачам? Простое переборное решение для задачи "Количество пар" даёт WA на 2-м тесте, и я не могу понять, в чём дело. Стресс-тестирование с авторским решением ничего не находит.

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
3 дня назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 дня назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The "x" on the G is wrong. It should be "y".

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Great contest!!

I solved problem D using sieve of Eratosthenes, hope it helps!!

Also, any suggestion for optimization in the code would be appreciated!!

SubmissionID

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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

  • »
    »
    3 дня назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      3 дня назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
3 дня назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I am a begineer on codeforces so forgive me if i have done a blunder . can anyone help to tell me why i am getting tle for d which i code today as practice on test case 2 here is the link to my solution

https://codeforces.com/contest/1538/submission/119155153

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Luckily exact same code got accepted in pypy3 in just around 800 ms while the same in python 3.9.1 gave tle on only test case 2

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why am i getting a tle for D. I did save the results from previous states to avoid tle https://codeforces.com/contest/1538/submission/119065595

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In G, it will be better if taken r=(x+y)/(a+b)

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It was my code and for python 3.9.1 it gave tle on test case 2 and i got ac in pypy3 with same code instantly .

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can any body tell me how k>=(y-a*n)/(b-a) while given equation was y>=(n-k)*a+kb I guess equation should be k<=(y-a*n)/(b-a).

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

if test case will be like a=2 b=2 k=1 then the output should be 'YES" or "NO"? since a==b already, do we need to change values of a and b??

»
3 дня назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

The solution of problem C can be written more efficiently as you are going through the already visited pairs again and again in each iteration of loop so i slightly modified the code to be more efficient do see my code for the problem thanks :) here's my submission link

»
3 дня назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain me what is going on with the solution code for problem D? I understood the editorial but didn't understand the code.

Here is a list of the things I think I've understood: - precalc() generates a sieve. - calcPrime(n) returns the size of the "largest prime factorization" from which we can obtain n. - decompose(n) decomposes n into the "largest prime factorization" from which we can obtain n.

But what do these parts do?

This part of the main function:

{
    int t;
    int ta = 1;
    while ((t = __gcd(a, g)) != 1) {
      a /= t;
      ta *= t;
    }
    high += calcPrime(a);
    if (a != 1) {
      low |= 1;
    }
    a = ta;
  }
  {
    int t;
    int tb = 1;
    while ((t = __gcd(b, g)) != 1) {
      b /= t;
      tb *= t;
    }
    high += calcPrime(b);
    if (b != 1) {
      low |= 2;
    }
    b = tb;
  }

The entire check function:

bool check(const map<int, int> &divs,
           map<int, int>::const_iterator it,
           map<int, int> &divsA,
           map<int, int> &divsB,
           int low,
           int high,
           int k) {
  if (it == divs.end()) {
    return __builtin_popcount(low) <= k && k <= high;
  }
  for (int p = 0; p <= it->second; p++) {
    int pa = divsA[it->first];
    int pb = divsB[it->first];
    int nextLow = low;
    if (p != pa) {
      nextLow |= 1;
    }
    if (p != pb) {
      nextLow |= 2;
    }
    if (check(divs, next(it), divsA, divsB, nextLow, high + pa + pb - 2 * p, k)) {
      return true;
    }
  }
  return false;
}

Thanks in advance.

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you please explain O(1) solution to Problem G? (easy to understand if possible)

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Wished the editorial explained the "if (l <= 2 * v[i] && 2 * v[i] <= r) "... the edge cases should be included in the editorial too!

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

anyone can give me any good video tutorial about porbem E.

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am not getting editorial of D question. Is there any theory I need to refer or if someone has any other solution, pls help.

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What is the logic behind this line for problem C?

  if (l <= 2 * v[i] && 2 * v[i] <= r)
      ans--;`
  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Our condition is that l<= a[i] + a[j] <=r , where i and j are two pairs(i<j). It can occur that the a[i] itself can satisfy this condition and we may pair a[i] with itself. This can occur because every time we check suitable pairs for a[i], a[i] itself is also included in the array. If this happens then it means a[i]=a[j] so, l<= 2*a[i] <=r . Since we want different pairs, to avoid possibility of an element pairing to itself and satisfying the condition, we check for that and reduce answer by one.

    For example , a = [1,2,3,4,5,6] , l = 5 , r = 10

    Suppose we are at a[4]=5. Now here, lower bound will take us to 0th index and upper bound will take us to 5th index.. Giving us total of 5 pairs for a[4].But, correct number of pairs would be 4.

»
3 дня назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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.

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.com/contest/1538/submission/119194346

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Very fast one line O(n log n) solution to problem C in Dyalog APL.

⎕IO←0 ⋄ {n l r←⎕ ⋄ ⎕←(r,l-1) -.{+/0⌈(⍳≢⍵)-⍨⍵⍸⍺-⍵} ⊂{⍵[⍋⍵]}⎕}¨⍳⎕

Try it online

This would be a great language to add.

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I solved problem C using a data structure called ordered set in c++. It is like the normal set but has 2 more functions. one of its functions is a function called order_of_key() which returns the number of elements strictly less than a certain number in log(n) time so I used this function to calculate the number of elements less than 1 or (l — ai) in case ai is more than l and the number of elements less than (r — ai + 1) and then subtract these two numbers and add it to the answer.

I saw other solutions which are faster than mine but I thought that this approach is cool to share

submission: https://codeforces.com/contest/1538/submission/119195153 more about ordered set: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/#:~:text=Ordered%20set%20is%20a%20policy,in%20log(n)%20complexity%20.

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here's a slightly different way to do G. Let's say we make $$$l$$$ gift boxes first by removing $$$la$$$ red and $$$lb$$$ blue candies from the piles. (Each of these boxes contains $$$a$$$ red and $$$b$$$ blue candies.) Then, of the remaining $$$x-la$$$ and $$$y-lb$$$ candies, we can make $$$\min \left( \lfloor \frac{x-la}{b} \rfloor , \lfloor \frac{y-lb}{a} \rfloor \right)$$$ more boxes each containing $$$b$$$ red and $$$a$$$ blue candies.

So in total, we have made $$$l + \min \left( \lfloor \frac{x-la}{b} \rfloor , \lfloor \frac{y-lb}{a} \rfloor \right)$$$ boxes. We want to maximize this, under the conditions $$$l \geq 0, x - la \geq 0, y - lb \geq 0.$$$

It's not hard to show that this function (on the integers) is non-decreasing and then non-increasing, and that no three consecutive integer inputs of $$$l$$$ yield the same value. So, it's easy to binary search on to maximize this function.

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem G: Gift Set. My solution is wrong for testcase 2.1103 It says it should be 0, but my solution gives 1. Could you, please, provide me with a testcase when my code gives a wrong answer? Thanks in advance.

ll k = min(x,y)/min(a,b); ll v = (x+y)/(a+b);

if (v < k) { cout << v << endl; } else { if (max(x,y)/max(a,b) >= k) { cout << k << endl; } else { cout << 0 << endl; } }

»
2 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

//my soln for c void solve(){ int n,l,r; cin>>n>>l>>r; vi a(n); for(int i=0;i<n;i++) cin>>a[i]; sort(all(a)); int ans=0; for(int i=0;i<n;i++){ int x=a[i]; if(x>r) continue; if(x<l){ int lb=lower_bound(a.begin()+i+1,a.end(),l-x)-a.begin(); int ub=upper_bound(a.begin()+i+1,a.end(),r-x)-a.begin(); // cout<<ub<<" "<<lb<<endl; ans+=ub-lb;
} else if(x>=l){ int ub=upper_bound(a.begin()+i+1,a.end(),r-x)-a.begin(); ans+=ub-i-1; } } cout<<ans<<endl; }

»
2 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help me with task C: I'm stuck in understanding the problem of next code (just a brute force) as a central part of the solution:

long long s = 0;
for(int i = 0; i < n; i++){
    for(int j = i + 1; j < n; j++){
        if(l <= A[i] + A[j] && A[i] + A[j] <= r){
            s++;
        }
    }
}
cout << s;

it fails on test #2 with WA: wrong answer 1491st numbers differ — expected: '10', found: '0'

I stress-tested this solution against the cononical solution and didn't find wrong example.

  • »
    »
    2 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I found a mistake :-)

    before this code there was a construction:

    cin >> n >> l >> r;

    if(n == 1){ cout << "0\n"; } else{ for(int j = 0; j < n; j++){ cin >> A[j]; } // solution code }

    so it didn't read input if n == 1 and therefore input for previous test was considered as input for next test.

»
2 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

thanks for quick editorial

»
2 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.com/contest/1538/submission/119120664

»
2 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    2 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      47 часов назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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!

»
2 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How can we sort the array in problem C, as we are distorting the given array indexes? Generally we don't sort in such pair of indexes problem right?

»
47 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.com/contest/1538/submission/119263670

  • »
    »
    46 часов назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      46 часов назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      so how could i make improvement to same program and is it possible this was the approach which first came to my mind .Now after posting this comment i saw the editorial and it is using some different approach which i am not able to understand that well .

      One thing which i am thinking about is counting substring after every iteration in the string and keep adding the substring which will be added after every iteration.

»
34 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
34 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    32 часа назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      28 часов назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
32 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please explain the logic behind the solution for F.

»
25 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A far simpler solution for Problem D:
Simply count the total no. of prime factor and how many times they are repeating for example.
48 = 2 * 2 * 2 * 2 * 3 => 2 ^ 4 * 3 ^ 1 => solve(48) => 5 (remember I added the power which is 4 and 1)
36 = 2 * 2 * 3 * 3 => 2 ^ 2 * 3 ^ 2 => solve(36) => 4
Maximum time we can divide both no. to make them equal (maxStep) => 4 + 5 = 9

The minimum times we can divide both no. to make them equal is calculated by below condition:-
if both no are not divisible by themselves and are not equal then the minimum step required to divided them and make them equal is 1;
else minimum steps are 2.
below is the code for this particular logic:-
int minStep = 2;
if ((a % b == 0 || b % a == 0) && a != b) minStep = 1;

Now, if the value of k lies between minStep and maxStep then print "YES" else print "NO";
Here's the code.

include <bits/stdc++.h>
using namespace std;

int solve(int n) {
  map<int, int> numbers;
  int max = 0;
  for (int i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ++numbers[i];
      n = n / i;
    }
  }
  if (n > 1) {
    ++numbers[n];
  }
  for (auto i : numbers) {
    max += i.second;
  }
  return max;
}
 
int main() {
  int tc;
  cin >> tc;
  while (tc--) {
    int a, b, k, minStep = 2, maxStep = 0;
    cin >> a >> b >> k;
    if ((a % b == 0 || b % a == 0) && a != b) minStep = 1;
    maxStep += solve(b);
    maxStep += solve(a);
    if (k >= minStep && k <= maxStep) {
      cout << "YES" << endl;
    } else
      cout << "NO" << endl;
  }
  return 0;
}
»
25 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can problem C be solved by (set.upper_bound(r-*it)-set.begin())-(set.lower_bound(l-*it) — set.begin())+1? Ik that set.upper_bound(r-*it)-set.begin() generally gives the index but here its giving me a compilation error.can someone help?

»
24 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone please explain in problem C this: if (l <= 2 * v[i] && 2 * v[i] <= r) { ans--; }

»
23 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone explain problem G please, I'm having hard time with it. I do understand that the solution is binary search on answer, but couldn't understand how do we know if some value x can be an answer or not.

»
3 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
114 минут назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone give some hint on how to approach the Number of pairs by two pointer method?