SUPINC - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: wasd2401
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given N, K, X, does there exist a superincreasing array of N positive integers whose K-th element is X?

EXPLANATION:

It’s not hard to observe that indices after K don’t matter at all - if it’s possible to place A_K = X, further indices can always be filled by choosing some sufficiently large values (one simple way is to use 2K, 4K, 8K, \ldots at those indices).

So, all we need to do is decide whether there’s a way to make a superincreasing array of length K-1, whose sum is \lt X - if we can do this, X can be appended to it as the K-th element.

Since we want the sum to be \lt X, it makes sense to try and attain the smallest possible sum as well; since we can always increase it to obtain X after that.
To that end,

  • The first element might as well be 1, the minimum possible value.
  • The second element, A_2, can’t be 1, so let’s make it 2.
  • A_3 now has to be greater than 1+2 = 3, so let’s make it 4.
  • A_4 has to be greater than 1+2+4=7, so let’s make it 8.
    \vdots
  • A_i will equal 2^{i-1}.

The smallest value that can occur at index K is thus 2^{K-1}.

A more formal proof

The statement can be proved using induction.

Our claim is that the sum of the first i values of a superincreasing array is at least 2^{i-1} - 1.
For i = 1 this is trivially true: the sum of everything before it is 0 (there’s nothing there), which is 2^0 - 1.

Now, suppose the statement is true for i \geq 1.
Then, since A_{i+1} \gt A_1 + A_2 + \ldots + A_i, and by the inductive hypothesis the latter summation is at least 2^{i-1} - 1, we have A_{i+1} \gt 2^{i-1} - 1.
So,

A_1 + A_2 + \ldots + A_{i+1} \gt 2\cdot (2^{i-1} - 1) = 2^i - 2

The sum of the first i+1 elements is strictly greater than 2^{i} - 2, meaning it’s at least 2^i - 1 (since we’re working with integers) as claimed; and induction completes the proof.

In other words, the answer is Yes if X \geq 2^{K-1} and No otherwise.

Note that K can be quite large, so checking this by directly computing 2^{K-1} might not work.
Instead, you can observe that since X \leq 10^9 \lt 2^{30}, if K \geq 31 the answer is always No.
For K \leq 30, X can be directly compared against 2^{K-1} since everything fits in a 32-bit integer.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, k, x = map(int, input().split())
    if k >= 32: print('No')
    else: print('Yes' if x >= 2**(k-1) else 'No')
2

why this gives wrong answer
void yes(){
cout<<“YES”<<endl;
}

void no(){
cout<<“NO”<<endl;
}

void solve(){
ll n,k,x;
cin>>n>>k>>x;

**ll sum = pow(2,k-1);**

** if(sum<=x) yes();**
** else no();**

}
But this one gives correct answer
void yes(){
cout<<“YES”<<endl;
}

void no(){
cout<<“NO”<<endl;
}

void solve(){
ll n,k,x;
cin>>n>>k>>x;

**if(pow(2,k-1)<=x) yes();**

** else no();**

}
it’s too much frustrating can anyone please help

3

Avoid using the pow function in c++, especially when you are using integers.

In this case you could just multiply by 2 k-1 times in a for loop or use 1<<(k-1). This way you don’t have to deal with imprecision

2 Likes
4

Actually, your problem here wasn’t the pow function itself, but that you’re not checking the cases where K is very big.

I didn’t knew this, but the pow function doesn’t really overflow it’ll just start to give values like 3.96140812571322e+28

So if you try to convert this enormous number to an integer it’ll overflow and your code will not work properly.

But if you don’t convert it and just compare with X the if condition will work properly.

PSA: What I said is still true, it’s best practice to avoid using function like pow when you are dealing only with integers.

1 Like
6

I too first tried using pow function, and then realized it might be incorrect results for very large values.

So I ended up dividing x repeated to get the 2th power that equals x and compared it with k. This way we don’t have to deal with large values or imprecision.

https://www.codechef.com/viewsolution/1053029743

1 Like
8

thanks for the editorial! :smiley:
during the contest I almost took 40-50m to solve this problem
but still couldn’t come up with a correct solution

10

because pow(a,b) return type is double and if you are storing it first in data type lower than double then it will give WA but if you store it in double float or any data type that is greater than double then it will not turnicate the pow() value and as you can notice that constraint k<2*(10^5) but x<1e9 so as in editorial k > 1e9 will fail and for safety purpose we will take float at min as it is> 10^10 which will be sufficient to store around 10^9 values and compare pow with k

use float double etc.

IF YOU FIND THIS HELPFUL PLEASE REPLY
AND IF I AM WRONG THEN ALSO POINT OUT

11

I mean, it works, but just to clarify what the comparison pow(2,20000) <= X is actually doing.

Let’s remember that double type can only store values between -(2^1023) to +(2^1023).
The thing with the double type is that they don’t overflow, they mark it as inf when the value is bigger than that. So, when people used pow(2, 20000) it actually threw an “inf” value.

The max value of X is 10^9, for which, the code was doing this

pow(2,1500) = Inf
Inf <= 10^9
False

pow(2,2000) = Inf
Inf <= 10^9
False

pow(2,10000) = Inf
Inf <= 10^9
False

I mark this just to not think pow was throwing an actual value, and to not encourage people to think pows and doubles are always a salvation if you don’t want to overflow. Like @dekatin said, it’s a risky approach.

1 Like
12

Nice, learned something new