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.
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…
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
@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.
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?
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.
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…
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.
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
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]…
