RANKLIST - editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Chandan Boruah
Tester: Pushkar Mishra
Editorialist: Florin Chirica

PROBLEM

Let’s define a ranklist as a sequence of numbers between 1 and x of length n, such as ALL numbers between 1 and x must appear in the sequence at least once. An operation can change one element in what value you want. Your goal is to create a sequence containing all numbers between 1 and n exactly once by using minimal number of operations.

QUICK EXPLANATION

Let’s iterate a number x meaning that all numbers between 1 and x appear in the ranklist. The cost of any ranklist with values between 1 and x is n - x. We need to determine if numbers between 1 and x are enough to create a sum s. Let’s note that a ranklist defined by x can create all sums between minSum and maxSum, where minSum = x * (x + 1) / 2 + (n - x) and maxSum = x * (x + 1) / 2 + (n - x) * x.

EXPLANATION

To solve this problem, we need to make two observations. They seem pretty easy and intuitive, but after we make them, the problem is solved.

Observation 1

A ranklist containing elements between 1 and x (no element greater than x) will need n - x operations to be transformed into a sequence of numbers between 1 and n, no matter how sequence looks like.

We already have all elements between 1 and x (from the definition of a ranklist). However, we need to also have elements x + 1, x + 2, …, n - 1, n. Those do not appear (since all are greater than x), so we have to make some operations to get them. We can keep exactly one position which contains a value i, for each i between 1 and x. Rest of n - x positions must be modified. We’ll put in the remaining n - x positions values x + 1, x + 2, …, n - 1 and n. So cost of a ranklist containing elements between 1 and x becomes n - x.

Observation 2

A ranklist containing elements between 1 and x (no element greater than x) can generate all sums s, such as minSum <= s <= maxSum. More, all sums that can be generated by this ranklist are the ones that are between minSum and maxSum.

Let’s find out who is minSum. We are forced to place x elements: 1 2 … x. The rest of them we can complete them with 1s. So minSum = (1 + 2 + … + x) + (n - x) = x * (x + 1) / 2 + (n - x). maxSum can be obtained by completing the first x elements 1 2 … x and the rest of them with x value (the maximum we’re allowed to use). So we get maxSum = (1 + 2 + … + x) + (n - x) * x = x * (x + 1) / 2 + (n - x) * x.

Obviously, no sum s can be less than minSum or greater than maxSum (because those values are the minimum/maximum one can get). Let’s proof now that each sum s which has minSum <= s <= maxSum can be obtained. The idea is to see how those n - x terms can vary: they can be from 1 1 1 … 1 1 1 to x x x … x x x. Suppose we obtained a configuration corresponding to a sum s. Unless s is equal to maxSum, we can always obtain s + 1 as well. If s equal to maxSum, then all terms are equal to x. Otherwise, at least one term isn’t x. Since it isn’t x, we can increment it. Now, the obtained sum is s + 1 and it’s obtained assuming that s is different from maxSum.

Putting the observations together

In fact, those 2 observations are enough to solve the problem. The key that puts them together is that we can iterate x from 1 to n. Let’s see for a fixed x if a sum s can be obtained. For the given x, we can calculate minSum and maxSum and if minSum <= x <= maxSum, then sum s can be obtained and a ranklist containing only values between 1 and x is valid. The cost to transform this ranklist into 1 2 … n is n - x. So, for all valid ranklists (those who can give sum s), we keep minimum of n - x and we’re done.

Time Complexity

Since we iterate the x variable from 1 to n, the complexity is O(n).

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester’s solution

Setter’s solution

2 Likes
2

Hi,

Funny approach…

I just used the fact that I could find out the number of elements a sequence would need to have to have sum S, and then, by filling all the remaining elements with value 1 and knowing the number of elements I could simply try to “decrement” the number of values used in the arithmetic progression 1,2,3… etc until I managed to reach a sum of value S.

Here is the code:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <string>
#include <vector>
#include <map>
using namespace std;

long long int max (long long int a, long long int b)
{
	if(a >= b)
		return a;
	else
		return b;
	}
	
int main()
{
	int tc;
	cin >> tc;
	while(tc--)
	{
		long long int n,s;
		cin >> n >> s;
		if(n==1 and s > 1)
			cout << 1 << endl;
		else
		{
		long long aux = floorl( (sqrtl(8.0*s + 1.0) - 1.0 ) / 2.0); //floor of num of elements needed for a seq to have sum S
		//cout << "aux " << aux << endl;
		long long auxsum = ((aux)*(aux+1))/2; //sum of the floor of these num of elements
		//cout << "auxsum " << auxsum << endl;
		long long remnums = n-aux; //we fill remaining elements with value 1
		//cout << "remnums " << remnums << endl;
		while(auxsum+remnums > s) //we decrement num of elements until we reach S
		{
			//cout << "stuck" << endl;
			aux--;
			auxsum = ((aux)*(aux+1))/2;
		}
			
		cout <<n-aux<< endl;
	}
	}
	return 0;
}
2 Likes
3

It is as Simple As This…

S = S-N;

sq = ((double)1 + sqrt ((1+8*S)))/2;

printf ("%lld\n",N-sq);

Link To My Solution : http://www.codechef.com/viewsolution/6136467

1 Like
4

![alt text][1]

The easiest approach .
[1]: http://discuss.codechef.com/upfiles/Capture_21.PNG

5

I did using binary-search. Here is my solution
http://www.codechef.com/viewsolution/6176994

1 Like
6

Well I had derived a formula for this question…

and it goes like this : N - (sqrt( 8*(S-N)+1 ) + 1)/2

Link to my solution: http://www.codechef.com/viewsolution/6126061

7

@adityakhanna1999, sum>=n is for what?

8

Well @sharad07,
I appreaciate your formula.

But, what is the logic behind it. Can you explain ?

How did you arrive at this : (sqrt( 8*(S-N)+1 ) + 1)/2

1 Like
9

@jeffrycopps_2
As we know that sum of n natural number is given by n*(n+1)/2 = s

simplifying this we get n^2+n-2s = 0

Using Quadratic Formula we get
(sqrt( 8*s+1 ) + 1)/2

1 Like
10

I have a doubt…

As mentioned We are forced to place x elements: 1 2 … x.

What is x over here?

is x a number such that x*(x+1)/2 < sumOfRanks ?

11

@jeffrycopps_2 @rohithr31

Can you please explain your logic behind the formula
(sqrt(8*(S-N)+1)+1)/2 ?

1 Like
12

Hi @jeffrycopps_2 and @matrixneo18 …

My first thought was on the largest possible rank(magnitude wise) that would fit in a rank list of given length & sum. eg: for a Rank list of len=7 and SUM=8

From above data, our invalid rank list looks something like this -> { 1,1,1,1,1,1,2 }

Now, a valid rank list of len=7 looks like this -> { 1,2,3,4,5,6,7 } with its sum=(7*(7+1))/2=28

But as you can see given sum is 7 which is much less than 28, indicating there are sum repetitions in the rank list.

Now, let us suppose that the largest rank is ‘n’, hence our invalid rank list would contain ranks from 1 upto n and some other repeating ranks.( clearly,in our invalid rank list, n=2 and there are 5 repeating 1’s ).

We subtract the sum of ‘1 to n’ from SUM & this is equal to len-n (notice 1,2 in bold below)

ie, sum of {1,1,1,1,1,1,2} - sum of {1,2} = len-n ( ie, 5 repeating 1s )

The whole thing boils down to a quadratic equation, SUM - (n*(n+1))/2 = len - n

On solving this you get n=(sqrt( 8*(S-len)+1 ) + 1)/2 , ie number of valid ranks that need not be changed.
Finally, the number of ranks to be changed is len-n.

1 Like
13

can someone please help what is he problem with this code in java?
http://www.codechef.com/viewsolution/6231580

14

Your program gives wrong answer for the case 10 38. The correct answer is 2 but your answer is 5.

For test case 10 38 the sequence would be {1,1,1,2,3,4,5,6,7,8}, so you need to change 1->9 & 1->10.
So you need to modify your program.

15

What is meant by the cost of rank list?