You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

This question is marked "community wiki".

asked 18 Mar '14, 20:33

shangjingbo's gravatar image

3★shangjingbo ♦♦
161446375
accept rate: 0%

edited 18 Mar '14, 21:10

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) pardeep_gill2★

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) build3r2★

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...

link

answered 18 Mar '14, 21:14

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
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★

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

link

answered 18 Mar '14, 22:10

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k52136170
accept rate: 20%

edited 18 Mar '14, 22:10

1

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

(19 Mar '14, 17:08) beethoven4★
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) siddhartha44443★

Same Approach used

(20 Mar '14, 20:58) suresh3011903★

@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...

link

answered 20 Mar '14, 13:51

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
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) pardeep_gill2★
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) betlista ♦♦3★
1

got it brother thanks a lot ..

(21 Mar '14, 09:18) pardeep_gill2★
1

No problem, keep interested, keep asking, that's the proper way to learn things, good luck ;-)

(21 Mar '14, 17:01) betlista ♦♦3★

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

link

answered 08 Apr '14, 15:16

abcdexter24's gravatar image

2★abcdexter24
309212
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<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:38) build3r2★

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?

link

answered 19 Mar '14, 22:11

ayushj10's gravatar image

3★ayushj10
163
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) rishabh19942★

Oww. Thanks. :)

(19 Mar '14, 22:52) ayushj103★

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?

link

answered 20 Mar '14, 20:18

Gaurav%20Rai's gravatar image

3★Gaurav Rai
12
accept rate: 0%

edited 21 Mar '14, 12:31

Because it is Python :D

(21 Mar '14, 16:51) bhambya2★

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;
link

answered 14 Apr '14, 01:36

build3r's gravatar image

2★build3r
1
accept rate: 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<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;

}

link

answered 27 Dec '14, 16:59

rahul1995's gravatar image

3★rahul1995
23114
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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