GUZAC - EDITORIAL

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

Tricky case :
1
10 3 49
1 43 44

Output:
415

Solution link : CodeChef: Practical coding for everyone

My approach :

  1. find the maximum P a = Smallest + x = 50
  2. find the required no of positions to be filled = k - n = 7
  3. 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.
  4. That is , for remaining 7 elements , you needed sum of
    A[0…2] + 50 + 49+ 48 + 47 + 46 + 45 + 44.
  5. 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.
  6. now we can find tot = Sum(A[k]s) + Sum(a…b)
2 Likes

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.