Thank u sir for enlightening us with such a good method!! Hats oFf!!

Can you explain your dp states for Problem C ?

what is the D&C approach?

why did this DC solution 27820818 get MLE? could you explain it to me please?

D problem D&C aprroach link

This implementation is same as of Kerim.K , just some comments added for ease of understanding.

Thanks to Kerim.K for sharing the approach...

#include <bits/stdc++.h>

define ll long long int

using namespace std;

int main() {

ll n,s;
cin>>n>>s;
float y=log10(s);

int k=ceil(y);
if(s==1)
{
    k=1;
}
//cout<<k<<endl;
if(n<=s)
{
    cout<<0;
    return 0;
}
ll ans=n-s-(9*k);
ll l=0;
ans=max(ans,l);
ll p=(9*k)+s;
for(ll i=s;i<=p;i++)
{
    if(i>n)
    {
        break;
    }
    else
    {
        ll h=i;
        ll sum=0;
        while(h!=0)
        {
            sum+=h%10;
            h=h/10;
        }

        if((i-sum)>=s)
        {
            ans++;
        }
    }
}
cout<<ans;
return 0;

}

Amazing observation :D

It's usually like a standard div2 round + one task slightly harder than div2e.

A very simple approach to problem B: Sort the array containing the numbers. Pick the first three. Now, we can prove that the minimum product will always contain only these three elements and nothing else. Thus, we next count occurrences of these first three letters in the whole sequence. Let the first, second and third numbers be a, b and c. And their repetition in the whole sequence be countA, countB, countC, and let they all be different. Then, ans is countA*countB*countC. But, if b repeats, then b is equal to c (sorted order). Then ans is countA* (ways of choosing 2 elements from countB elements). Similarily if a is repeated two times. Ans is countB only(any other repetition of a will cause it to be equal to c). If all three are same. Then ans is (no. of ways of choosing 3 elements out of countA elements). Here, the no. of ways of choosing 3 elements out of n elements = n*(n-1)*(n-2)/6 Here, the no. of ways of choosing 2 elements out of n elements = n*(n-1)/2

it works but you also have to check if it's possible to reach the point doing movements in L. like a horse on chess. It will be reachable if the number of moves performed in the x axis + the number of moves performed in the y axis is even. This happens because when you move, you always do a move in both axis.

Hmm. I don't really know :) I used the approach from the editorial in couple of other problems, though I can't remember any in particular. I guess that if this one doesn't seem intuitive then you can always try the other one. Where you just check some cases on the amount of the elements less than the third minimum of the array. Most people implemented this solution.

UPD: the author of this task told me that the similar approach is used here

I solved it differently. First sort array a. Then take three smallest values, let them be a,b,c in this order. Also, while doing input of array, keep array cnt[x], which tells how many times x appeared in input.

1. case a!=b!=c Then number of ways is cnt[a] * cnt[b] * cnt[c] (simple combinatorics)
2. case a == b but b!= c (if b!=c then a!=c as well, because a,b,c are sorted) then there are cnt[a] * (cnt[b] — 1) /2 ways to choose pair (a,a) and cnt[c] to choose c, so to get total multiply these two.
3. case a != b, b == c Similar to 2. case 4.case a == b == c then answer is cnt[a] * (cnt[b] — 1) * ( cnt[c] — 2) / 6 (again simple combinatorics)

That covers all cases.

I guess integer overflow in the last for loop

0 -4, -2 -3, -4 -2, -6 -1, -8 0, -8 1, -8 2, .. .. .., -8 8

(-2,+1) (-2,+1) (-2,+1) (-2,+1) (-2,+1) (+2,+1) (-2,+1) (+2,+1) (-2,+1) (+2,+1) (-2,+1) (+2,+1) (-2,+1)

I also have the same problem...

Here is my code.

NlogN solutions were supposed to pass but in your solution the constant factor is large (around 5).

In your code the complexity is :

1. Sort — NlogN
2. First loop — 2*NlogN
3. Second loop — 2*NlogN

Overall Complexity — 5*NlogN (Worst Case) = 5*(10^6)*(20) = 10^8.

And only those O(10^8) solutions pass in 2 sec which are highly optimised. In your case the hidden constant factor of set insertion also affects your code complexity.

Other NlogN solution which passed : 27810683 by Kerim.K

Your approach is absolutely correct since you have used binary_search.

As you can observe from the value of num-sumD(num), it is always increasing.

• For num = 1 to 9 : num-sumd(num) = 0
• For num = 10 to 19 : num-sumD(num) = 9
• For num = 20 to 29 : num-sumD(num) = 18
• .
• .
• .
• For num = 999999999999999990 to 999999999999999999(18 times) : num-sumd(num) = 999999999999999872

And since the value of num — sumD(num) is strictly non-decreasing, take the lower limit to be 1, higher to be n + 1 and search for the appropriate num such that for values less than num (num — sumd(num)) is less than s and for values greater than or equal to num (num — sumd(num)) is greater than or equal to s.

So your approach is alright. For more clarification you can see my code : 27802867

This is for itachi_2016's approach.

Try the following test case and you will realize your mistake. 109 91

It's not much different from the segment tree one. Numbers are also compressed and the queries are the same.

You process assigning on a segment and xor of the segment by dividing original array into sqrt blocks, for each block you maintain its sum. Lazy propagation is used too. Just every query works in instead of .

We decided not to force participants to use solutions.

your code is giving wrong answer because suppose you are standing on a node where xbit=1 and ybit=0 then there xor is 1 and you are adding all the numbers that have that bit zero. but this is wrong because this does not gaurantee all the number in this group to be smaller then your leadership(l).this group till now are only equal, not became less. so you can't add them. if xbit=0 and ybit=1 then your case is correct. there may be case some of these number can latter become equal to or greater than leadership(l). link this is my code you can see . this might help you visualising what i am saying.

hi

we don't calculate product of three numbers

and question is "how many ways are there to choosing three minimal numbers"

because minimal numbers give us minimal product

can you explain your approach . it is diificult to understand from code

Considering finding the sum of minimum values for all subsegments, the solution tries to know for each index i how many times a[i] will be the answer. If x is the number of subsegments that contain index i and a[i] is the minimum value, then ans[i] = x·a[i]. The final answer will be .

For the correctness of the algorithm, if a subsegment have more than one cell with the same value, we will consider the answer to be the leftmost cell.

For index i, Let:

• L[i] be the rightmost index j < i and a[j] ≤ a[i]
• R[i] be the leftmost index j > i and a[j] < a[i]

Clearly, All cells in the range [L[i] + 1, i - 1] have values greater than a[i] and all cells in the range [i, R[i] - 1] have values greater than or equal to a[i]. Now, we can say that index i can be the answer to any subsegment whose startpoint is in the range [L[i] + 1, i] and endpoint is in the range [i, R[i] - 1]. So, ans[i] = (i - L[i])·(R[i] - i)

How to compute the array L? Keep a stack with you and go from left to right. The stack is initially empty and will contain indices. Now, we are at index i:

• If the stack is empty, L[i] =  - 1.
• If top of the stack is j and a[j] ≤ a[i], then L[i] = j
• If top of the stack is j and a[j] > a[i], then pop this element and do the same check for the new stack top.

If j is popped from the stack, then for k > i, can L[k] = j? The answer is no, because a[j] > a[i] and i is closer to k from j, so if a[i] ≤ a[k], then L[k] = i. Otherwise, a[j] > a[i] > a[k]. That's why we remove j from the stack because it will never be used again.

After finding L[i], push i onto the stack.

You can compute the array R in a similar way from right to left.

hi

it is difficult to explain but

if there modes in 2 aren't equal then we can't arrive from x1 to x2 and y1 to y2 in the same time

and if there modes in 2 are equal then imagine that:

x2 > x1 and y2 > y1 and (abs(x2 — x1)/a) > (abs(y2 — y1)/b)

then you can simply do x1 + a, y1 + b and x1 — a, y1 + b k times and you will have

(abs(x2 — x1)/a) and (abs(y2 — y1) + b*2k)/b

and you can chose correct k to get (abs(x2 — x1)/a == abs(y2 — y1)/b + 2*k) because their modes in 2 are equals.

for another cases you can do like this.

if mod 2 is 1, then we can reach target with odd number of moves. Otherwise, we can reach target with even number of moves. So, the parity (odd/even) must be the same for both horizontal and vertical moves.

Check this comment

You can use Dynamic Segment Tree.

I've tried to do it, but got Memory Limit Exceeded. I think my implementation is still not good enough. If you want some idea on how to code, this is my code: 27989735

I think that I would receive Accepted if memory limit was higher.

hi

you can save 3 smallest numbers in 3 Variable and save their count

even it isn't necessary to store all numbers.

There was overflow in some operations (maybe l * r), here is your code without overflow: 28011406

I'm not sure but this can probably be Java anti-sort test. Arrays.sort over an array of primitive types uses quicksort and may work in O(n²). Try replacing it either with Collections.sort or with array if Integer values.