In REDCGAME : “Case 2: (a1+a2+…+am−2)≥am−1. In this case, we will first keep pairing up some two elements from the first m−2 elements, till their total sum becomes equal to am−1.”
What if the m=5 and the numbers were 2,3,5,8,10.The parity of sum of m-2 elements is same as that of am-1 but how can it be reduced to zero ??
After 1st step (The sequence would look like this)
0,1,5,8,10
After 2nd step
0,0,3,8,10
After 3rd step
0,0,0,5,10
And that would not result into the optimum answer. I thought of some other choices like first pair 5 and 8 which will reduce 8 to 3 and after that we pair two remaining 3s but this will result into answer = 8
How can I pair these m-2 elements such that we get correct answer ??
Can you please explain with a case of 2,3,4,6,39,40 (m=6) because in this case even though the parity of sum of m-2 elements is same as that of (m-1)th element but we won’t be able to keep mth element untouched.
k=0
m=[]
m.extend(x)
for j in range(int(y)-1,int(z)):
l=int(z)-1-k
m[l][0],m[l][1]=m[l][1],m[l][0]
x[j]=m[l]
k+=1
return x
def a():
a,b=raw_input().split(" ")
a=int(a)
b=int(b)
c=raw_input().split(" ")
d=raw_input().split(" ")
f=[]
g=[]
for e in range(a):
f.append([int(c[e]),int(d[e])])
g.append([1,-1])
for h in range(b):
i=raw_input().split(" ")
if len(i)==3:
f=become(f,i[1],i[2])
if len(i)==2:
g=become(g,1,i[1])
if len(i)==5:
on=int(i[1])
tw=int(i[2])
th=int(i[3])
fo=int(i[4])
count=0
sums=0
while (th-1+count)<=(fo-1):
sums+=g[th-1+count][0]*f[on-1+count][0]
count+=1
print sums
a()
how to solve the TLE error in this problem(if possible)?
A proof for Case 2 in REDCGAME.
Suppose the sum of the first g-2 elements is greater than/equal to g-1’st element. Therefore, there have to be at least 2 elements, both smaller than g-1’st element in the g-2 elements(If this was not the case and we only had one element, it would be the g-1’st element instead). Let the element at g-1 be x and the sum of the first g-2 elements be y. Since there are at least two elements in the first g-2, we can pair some of them up (y-x)/2 times to make the sum of them just smaller than x. Then we can conveniently pair all the remaining elements with the g-1’st element. If in turn, the sum was originally less than x, the optimal way is to pair everything with g-1’st element, as not utilizing the g-1’st element for pairing would lead to it being used to decrease the largest element in a non-optimal way.
Total up the occurrence of each different letter in the word set. Then halve these counts, rounding up (e.g. (count+1)//2). The minimum number of squares required will be the sum of these values - if it’s more than 16, the word set is not feasible.
Justification: every letter in the grid can only belong to at most two words. Note that any list of more than 8 words will fail this test.
In this case it is not possible to pair up the elements fully due to different parity of 9 and 8. One element will always be left, which in turn will be paired up with a_m. It is written how to deal with this case a bit ahead in the paragraph.
Yes I had read that earlier. I had mistaken the “their” in the statement I have quoted above for the pair of elements instead of the first m - 2 elements.
The m = 5 case: The sum of the first three elements is 10, which is greater than the second largest element, 8. So we have to first reduce the sum of the first 3 elements to 8. That can be done by subtracting 1 from both 2 and 3. The sequence now is 1, 2, 5, 8, 10.
Now, we’ve to pair the first three elements with the 4th one, one by one. So the sequence changes like this:
For the m = 6 case, the sum of the first four elements is 15, which is less than the fifth element. So you’re right, we’ll have to reduce the last element also.
Apologies. I totally missed the 50 testcases, and posted it without getting it verified by the setter or tester. It’s been fixed now. Still not sure if this is the analysis which the setter had in mind, but this should work. A better analysis will probably come up in the actual editorial.
We are subtracting K from each of those elements which are > K at the beginning. So a_m in the final formula actually refers to (a_m - K), which I believe is what you’re referring to.
ok i removed that , bcoz earlier i didnt marked for zero movement robot, but getting wrong answer still after marking zero move for above code(21337330).I will not sleep untill i get AC