At first tried brute force so I was able to pass the first task but then for tle I used maps to store my answers I tried every test case which I was able to think with both brute force and this recursive method .
But still, they were giving same answers. Then why I am getting wrong answers?
In 2nd solution which i had designed for avoiding tle I am calculating required answer by two sub methods.
for e.g for 1 2 query, i would first calculate sum of squares of 4,8,12,16,…so on and I am storing each result of func(4), func(8),… as well as func(2) in maps so that I can use it later then why I am getting wrong ans ? PS I had updated my maps after query 2. please look at my solution and tell me whats wrong in that! I had thought about it for hours still was not able to find my mistake
Link for brute force approach:-https://www.codechef.com/viewsolution/15117844
link for the wrong answer approach:-https://www.codechef.com/viewsolution/15134001
Hello
Same problem here , I can’t find out what is wrong.
My code here : https://www.codechef.com/viewsolution/15155600
func is doing normal calculation but funccont is calculating remaining terms …
for e.g first if i will call for func(2) then what i want a[2]*a[2] + a[4]*a[4]+…a[8]*a[8]----
what i am doing is checking first if(value is present in map or not)… if not present then i would calculate it by calculating first a[4]*a[4] + a[8]*a[8]+… so on and then adding a[2]*a[2]+a[6]*a[6]+a[10]*a[10]…so on … ! i had used ‘s’ in funcont for
for incrementing by 2.x like i want in this in a[2] and then a[6] … so i had used funccont (funct continue :P) i hope now its clear .help me plz !
1 Like
it->second=it->second-A[x-1]A[x-1]%1000000007+yy%1000000007;
This line make your answer negative
But we required only positive answer so you have to Add MOD(1000000007) in your it-> second whenever it-> second < 0
i.e while( it-> second < 0 ) it->second += MOD
https://www.codechef.com/viewsolution/15158824
dude see i had added that line my program but still its showing me WA
your point is correct but what about subtask 1 ? it is way less than MOD then why its showing WA
Hey @cis_pie,
Please don’t consider this as an answer to your question, just few thing which I observed.
- Use of long instead of long long as A[i] can be as large as possible up to 10^9 than its square would be around 10^18 and this won’t fit in long int.
- Your approach seems a bit wrong, because if all the queries are of type 2 and of the order of 10^5 than it won’t pass in specified time-limit. As it will be traversing the whole map
- it->second=it->second-A[x-1]A[x-1]%1000000007+yy%1000000007; can be negative as well.
- And what if some value that is not queried(1) but has been changed, in that case also your program will not give the value. as that value will not be stored in the map.
Hope any of this helps!
Possible solution is the first store every value in map, intead of calculating again and again when query of type 1 occurs this way you get your query 1 answer in O(1) and for a query of type 2 do the same thing which you are doing.