There is a question Chef and Numbers. According to Editorial it is purely based on FFT having overall time complexity O(n * log(n)). But after crawling other solution i found one of the solution which is Based on Dynamic programming. So the doubt is about it’s time complexity which seems to be O(n^2).
Can anyone tell me the full explanation about it’s real complexity of that AC solution?
I am not sure what you mean by ‘full explanation about real complexity’, but here goes:
for(int i=1; i<=N; ++i){
int val = A[i];
if(is[val]) continue;
for(int j = 0; j + val < MAX; ++j) if(is[j]) is[j + val] = 1;
}
The MAX variable is set to the maximum value of N.
Given the for loop runs exactly N times, and the nested one runs for N times as well in the worst case,
the worst case complexity should be O(n^2).
But given the variable val is non-zero and so the actual average run time should be less than O(n^2).
I think in the above code many of the computations will not be performed as this condition “if(is[j]) is[j + val] = 1;” is marked various elements as true and by doing so many of the computations are getting skipped and loop will not run for those cases.
Hey @bansal1232, you are right, the worst case runtime is theoretically \mathcal{O}(n^2), but a clever optimization and the constraints make it fast enough to pass the time limit.
The standard coin change dp algorithm would be something like
for(int i=1; i<=N; ++i){
int val = A[i];
for(int j = 0; j + val < MAX; ++j) if(is[j]) is[j + val] = 1;
}
See the last section on this page.
As you can see there are 2 differences. The first is "sort(A+1, A+1+N);". The second is "if(is[val]) continue;". What do these do together?
The sorting makes sure that the smaller coins are handled first and all values you can make with smaller coins are marked 1. Now it is possible that a larger coin can be made with some combination of smaller coins. Hence this larger coin is effectively redundant. Every sum that can be made using this coin can also be made using some combination of smaller coins. So the values at those sums will already be marked 1 and we do not need to think further about it. Now since the constraints specify that the value of each coin will be within 200000 (which is quite low), this occurs very frequently. We can detect this because is[val] will be marked 1 for that coin. And whenever this happens the inner loop is skipped, hence it is fast enough to pass the time limit.
Hope the explanation is clear. On a personal note, I cursed myself after the contest because I hadn’t thought of this trick 
91 9521737788 [[ 100% free solution no fees get free 101% garunted
online free solution by Rk.sharma +91 9521737788 jaipur
only one call+91 9521737788can solve your
all problem solution with in 24 hour 100% garunted one call change your
life FAMOUS ASTROLOGER R.K Sharma india +91 9521737788 astrologer
R.K Sharma famous in world and india all city con… no +91 9521737788
online black magic vashikaran specialist baba ji
love vashikaran black magic specialist babaji
online black magic specialist astrologer
black magic spells Specialist Baba Ji
get lost love back baba ji
Spell Baba Ji
Protection Spell Baba ji
vashikaran specialist
vashikaran specialist
love marriage specialist
love marriage specialist
love marriage specialist in mumbai
How To Get An Ex Back Baba Ji
get love problem solutions
vashikaran bmagic specialist babaji in uk
tantra mantra black magic Specialist Baba Ji
black magic for love Specialist Baba Ji
kala jadu specialist Specialist Baba Ji
online love problem solution baba ji
black magic aba ji
black magic spells
kala jadu specialist in uk
kala jadu specialist in orissa
black to get love back specialist baba ji
love vashikaran specialist aghori baba ji love
mohini vashikaran specialist baba ji in canada
Mohini Mantra Specialist Baba Ji
Sammohan Sadhnas Specialist Baba Ji
Black magic and many Vaastu Specialist Baba Ji ‘
permanent resolution Specialist Baba Ji
·Love Marriage Astrology
· Love Marriage Spells
· Love Problem Specialist
· Love Marriage Specialist
· Vashikaran
· Vashikaran Specialist
· Online Vashikaran Specialist
· Vashikaran Yantra For Love
· Vashikaran For Marriage
· Vashikaran For
· Love Spell Expert
· Powerfull Mantras For Love S
Reply
Reply
Related Topics
!! BLACK MAGIC SPECIALIST !! +91-9521737788 !! LOVE PROBLEM SOLUTION BABA JI
!! BLACK MAGIC SPECIALIST !! +91-9521737788 !! LOVE PROBLEM SOLUTION BABA JI
~!@# love problem solution +91-9521737788 all problem solution BABA JI
~!@# love problem solution +91-9521737788 all problem solution BABA JI
love problem solution baba ji +919521737788 baba ji
Reply
Reply
Related Topics
~!@# love problem solution +91-9521737788 all problem solution
!! BLACK MAGIC SPECIALIST !! +91-9521737788 !! LOVE PROBLEM SOLUTION BABA JI
~!@# love problem solution +91-9521737788 all problem solution BABA JI
~!@# love problem solution +91-9521737788 all problem solution BABA JI
love problem solution baba ji +919521737788
But how O(n^2) complexity can pass in 1 second?
Its 1.5 seconds. O(n^2) Solution should work fine I guess, the range is upto 200000, quiete reachable with O(n^2) I guess.
Approx 4*10^10 computation that will never work.not even in 5 sec 
its 4 x 10^10 in worst case. He has very cleverly skipped the second loop for cases that variable (and hence its multiples) are already done. We cannot comment anything about 4 x 10^10, until we find what was the worst case tested for that problem.
It’s about the test cases really. Plus the computation in the loop is fairly simple, meaning that it can be performed relatively quickly.
Of course @meooow, but please give the light on amortized time complexity. Since large prime numbers will also be there that can’t be redundant.
I’m afraid it will take a smarter person than me to give the specifics of a worst case performance. However large primes are not really significant here, because we are dealing with sums and not products. A large prime valued coin might be made up using coins of smaller value just like any other coin.
You’re welcome 
I hope someone else can provide better details about the worst case.
Dude, is this a dream or someone really posted such s*** here?
One heck of a spammer
I strongly feel the need that codechef should only allow posting (even answers) for only those users who have solved at least one problem (like codeforces).
Black magic specialist…WEW.