In the question it was mentioned that Pi is <=10^9 for all valid i. Now by “valid i”,I thought that i is in the range of 1 to N, but it seems that it was only for first K elements and remaining numbers could be greater than 10^9. My solution got rejected just because of this ambiguity
Tricky case :
1
10 3 49
1 43 44
Output:
415
Solution link : CodeChef: Practical coding for everyone
My approach :
- find the maximum P a = Smallest + x = 50
- find the required no of positions to be filled = k - n = 7
- find the smallest b of the continuous integers you need to find in the formula. b = 50 - (n-1-k) = 50 - (10 - 1 - 3) = 50 - 6 = 45.
- That is , for remaining 7 elements , you needed sum of
A[0…2] + 50 + 49+ 48 + 47 + 46 + 45 + 44. - now since , this (44) was already present in A[k]s , instead of 44 , you can take 43…but is 43 is also present…take 42.
- now we can find tot = Sum(A[k]s) + Sum(a…b)
What is the formula for summation over a range?
can anyone give me a test case in which my solution is not working ?
It’s passing in all the test cases given here and sample test cases.
here’s my solution getting WA.
https://www.codechef.com/viewsolution/19811696
Please explain how to process multiple elements in a range simultaneously. I am not getting.
Can anyone help me to rectify where my program is failing
Solution Link-CodeChef: Practical coding for everyone
[24, 146] N=371 k=2 x=237
what should be output ?
There is a mistake in constraints x must be greater than N otherwise There won’t be any case possible where all are distinct and still difference between maximum and minimum does not exceed.
( I strongly believe the tester has added that cases otherwise my codes is giving correct for every valid input).
Here is the code :- CodeChef: Practical coding for everyone
hey i did it with same strategy but it is running out of time(TLE), i have checked it thoroughly, please somebody look into it Coding Blocks IDE (commented code) , https://www.codechef.com/viewsolution/19797503(submission)… if have any test cases please give them
what if the test case is …
4 2 4
1e9-2,1e9-2
in that case number might be greater than 1e9 which is the contradiction of the given constraints ??
i dont know why i am getting wrong answer ,i checked with all test cases help me @taran_1407
link text
Entertain the possibility that the minimum number can be some number less than minimum of the pi’s;
Test Case -
1
13 4 10
4 5 9 13
Please anyone take a look at my code and tell me where am I doing it wrong?
ll t;scanf("%lld",&t);
while(t--)
{
ll n,k,x;scanf("%lld %lld %lld",&n,&k,&x);
ll a[k+1];
ll s=0,cou=k;
f(k)
{
scanf("%lld",&a[i]);
s+=a[i];
}
sort(a,a+k);
a[k]=a[0]+x+1;
repb(i,k,1)
{
if(a[i]-a[i-1]>1)
{
if((cou+a[i]-1-a[i-1])<=n)
{
s+=(a[i]*(a[i]-1))/2;
s-=(a[i-1]*(a[i-1]+1))/2;
cou+=a[i]-a[i-1]-1;
}
else
{
s+=(a[i]*(a[i]-1))/2;
ll need=n-cou;
need=a[i]-1-need;
s-=(need*(need+1))/2;
}
}
}
printf("%lld\n",s);
}
The aim og adding fictitious element depend upon the implementation.
Yes min+X can also be used.
See editorialist solution. I first add all K elements. That’s why i use exclusive bounds in my solution. See editorialist solution.
Corrected.
Aim is simple. We have K elements. Select N-K more elements such that sum is maximized. But cannot select elements such that absolute difference is greater than X. So, we start from min+x, the maximum element which can be included, and check each number smaller tham it in reverse order, till we find N-K elements. Since n is upto 1e9 , we need to process multiple elements in a range simultaneously, as explained above.
@tarzan_1407 can you please tell why my solution is getting RUNTIME ERROR(sigsegv).
Inconvenience is regretted.
There was a confusion.
We intended the constraint on pi to apply only on first K elements, which are given in input. Remaining elements can be greater than 1e9.
Let Function f(N) be Sum of first N natural numbers is given by (N+1)*N/2. For a range [L, R] (Both L and R inclusive), sum of range is f® - f(L-1).
Consider test case
9 3 10
1 5 10
In this, first add (1+5+10) to answer. Then, add an element min+x+1 = 12 to array and sort it.
Array looks like 1 5 10 12. This means that we can include N-k = 6 elements {11}, {9,8,7,6}, {4,3,2}. Now, see that ideal strategy is to include largest numbers.
After adding 11 to sum, since we know that (5, 10) contains 4 elements while we need 5 elements, we add whole range. 6+7+8+9 = f(9) - f(5), f(n) denotes sum of first n natural numbers.