TMSLT - Editorial

PROBLEM LINK:

Practice
Contest

Author: Shiplu
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang

DIFFICULTY:

Simple

PREREQUISITES:

Sort

PROBLEM:

Given a random sequence of N numbers, a[0…N-1], sort them in order and report the difference between the sum of numbers in odd positions and the sum of numbers in even position.

EXPLANATION:

If a quick sort is directly applied, the time complexity is O(N logN). But the range of numbers is small, within 1,000,000. Therefore, we can use the counting sort, that is,

count[0 .. 999999] = 0
for i = 0 to N-1 do
    count[a[i]] ++;
end

Go through the count array again, we can get the order. With this algorithm, we can solve this problem in O(X) time, where X is the range of all numbers.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

1 Like

I’d like to ask the community here if questions like

are cheating or not?

I understand that asking a questions is part of learning process, but here (and I’m not telling this is the first case), it’s related to ongoing contest and even such question is kind of hint I think…

2 Likes

Let me tell you another optimization in the problem, As mod is 10^6, It is sure that you will get a cycle in atmost 10^6 iterations, Hence find that cycle and use that to calculate the answer =D

1 Like

I was able to identify the formation of cycles somewhere within 10^6 iterations, but I still got TLE. I used the STL sort function. Shouldn’t that have done the job?

@pardeep_gill:

int now = 0;
for(int i=0;i<1000000;i++){
    if(now%2==0)
        sum+=(co[i]%2)*i;
    else
        sum-=(co[i]%2)*i;

    now+=co[i];
}

I assume you understood the “sorting” part…

So, now for input

1 2 2 2 4 6

we have in co array values

0 1 3 0 1 0 1

the if(now%2==0) handles, that we are alternating addition of strength to team, you can simply change the algorithm with

    if(now%2==0)
        sum1 += (co[i]%2)*i;
    else
        sum2 -= (co[i]%2)*i;

where sum1 is for first team and sum2 is for second, but while we are interested only in difference, we can use one variable and use + for first team an - for second…

2 Likes

In Python, for same logic I am getting TLE :frowning:

t = int(raw_input())
while t>0:
    t -= 1
    
    n, a, b, c, d = map(int, raw_input().split())
    h = [0] * 1000000
    h[d] = 1
    for i in range(n-1):
        d = ( ((d * d * a) % 1000000) + (b*d) + c) % 1000000
        h[d] += 1
    
    ans = 0
    is_x = True
    for i in range(999999, -1, -1):
        temp = h[i]
        if temp % 2 == 1:
            if is_x:
                ans += i
                is_x = False
            else:
                ans -= i
                is_x = True
    print ans

Any idea why is this not working?

It would have been a cakewalk if there was no MOD thingy :stuck_out_tongue:

1 Like

Can anyone explain me why we must use the bool array as in this example.?

Blockquote

s=d;
has[s]=1;//boolean has[1000001] 
arr[0]=s;
k=1;
for(i=1;i<n;++i)
{
   s = (((((a*(s*s)%m)%m)+((b*s)%m))%m)+(c%m))%m;
    if(has[s])
    {
        break;
    }
    else
    {
        arr[k++]=s;
        has[s]=1;
    }
}

if(i==n)flag=1;

for(i=0;i<k;++i)
{
    if(arr[i]==s)break;
}

pos=i;

Guys, I am getting SIGSEGV, please help.

Since the strength can’t be greater than 1000000, I used a boolean array s[1000000] of this size, true means the strength is taken by a person, if two persons are there with same strength then they would be in different teams and cancel out the difference of strengths, so for every strength temp that comes during iteration, I have used s[temp]=~s[temp] . Finally, I just add and subtract alternatively for every s[i]==true. Giving me SIGSEGV… please help.

#include<bits/stdc++.h>
using namespace std;

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
    long n,a,b,c,d,i,diff=0,last;
    scanf("%ld%ld%ld%ld%ld",&n,&a,&b,&c,&d);
    bool s[1000000]={false};
    s[d]=true;
    last=d;
    for(i=1;i<n;i++)
    {
        long temp=(last*(a*last+b)+c)%1000000;
        s[temp]=(~(s[temp]));
        last=temp;
    }
    i=0;
    while(i<1000000)
    {
        if(s[i])
        {
            diff+=i;
            i++;
            while(i<1000000 && s[i]==false)
                i++;
            if(i<1000000)
            {
                diff-=i;
                i++;
            }
        }
        else i++;
    }
    if(diff>=0) printf("%ld\n",diff);
    else printf("%ld\n",diff-2*diff);
}
return 0;

}

I did the same way as suggested by @dpraveen. Guess what, 0.26 secs !

1 Like

@betlista I wouldn’t consider them as cheating. Sorting and searching are commonly known algorithms and these questions are mostly asked by beginners who want to learn. If you look at my answer and other answers they are general answers and not specific to any question. This info is easily available on others sites also. However asking question specific details is certainly unwelcome.

2 Likes

actually i also used the stl sort function . but here we were supposed to use bucket sort as range of numbers was very less.Hence we got TLE

1 Like

Oww. Thanks. :slight_smile:

can someone explain this portion ?

	for(int i=0;i<1000000;i++){

		if(now%2==0)
			sum+=(co[i]%2)*i;

		else

			sum-=(co[i]%2)*i;

		now+=co[i];
	}
1 Like

Me too, fastest java implementation of all. Cycles are very likely to occur much faster than 10^6. Certainly with a MODULO that is not a prime. Which is very good for average complexity.

1 Like

why following statement are used ?
(co[i]%2)*i and now+=co[i]; ??
where as to alternate the addition and subtraction we could have just toggle a boolean variable or just checked if i%2==0 or not that could have done the job as well?

rest of the part is very clear friend
just not able to understand the use of these two statements.

Thanks in advance and for above explanation . :slight_smile:

1 Like

Can anyone please explain this concept of cycle ?

Same Approach used

it’s because when you have 2 2 2 in input above, you do not need to add first 2 to first team, second to second team and last to first team… as you can see, if number of elements is even you do not need to add it (because one half belong to one team and another one to another team) and that’s exactly what (co[i]%2)*i is doing…

now is a index for team members, so when you added co[i] members, you need to increment it by co[i]

1 Like

got it brother thanks a lot …

1 Like