×

# TMSLT - Editorial

Author: Shiplu
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang

Simple

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.

This question is marked "community wiki".

161446375
accept rate: 0%

1

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];
}

(20 Mar '14, 05:21)

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;

(14 Apr '14, 01:39) 2★

 2 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... answered 18 Mar '14, 21:14 16.9k●49●115●225 accept rate: 11% 2 @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. (19 Mar '14, 18:31) kcahdog3★
 1 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 answered 18 Mar '14, 22:10 2.5k●52●136●170 accept rate: 20% 1 I did the same way as suggested by @dpraveen. Guess what, 0.26 secs ! (19 Mar '14, 17:08) 1 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. (20 Mar '14, 06:00) samjay5★ Can anyone please explain this concept of cycle ? (20 Mar '14, 19:31) Same Approach used (20 Mar '14, 20:58)
 1 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... answered 20 Mar '14, 13:51 16.9k●49●115●225 accept rate: 11% 1 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 . :) (20 Mar '14, 18:41) 1 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]... (20 Mar '14, 21:49) 1 got it brother thanks a lot .. (21 Mar '14, 09:18) 1 No problem, keep interested, keep asking, that's the proper way to learn things, good luck ;-) (21 Mar '14, 17:01)
 1 It would have been a cakewalk if there was no MOD thingy :-P answered 08 Apr '14, 15:16 309●2●12 accept rate: 3% 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
 0 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? answered 19 Mar '14, 22:11 3★ayushj10 16●3 accept rate: 0% 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 (19 Mar '14, 22:26) Oww. Thanks. :) (19 Mar '14, 22:52) ayushj103★
 0 In Python, for same logic I am getting TLE :( 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? answered 20 Mar '14, 20:18 1●2 accept rate: 0% Because it is Python :D (21 Mar '14, 16:51) bhambya2★
 0 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
 0 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 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=0) printf("%ld\n",diff); else printf("%ld\n",diff-2*diff); } return 0;  } answered 27 Dec '14, 16:59 23●1●1●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,482
×1,155
×775
×20

question asked: 18 Mar '14, 20:33

question was seen: 7,885 times

last updated: 27 Dec '14, 16:59