this is my solution for 5 ques…
plz tell why it gives tle …
and its exact time complexity as well…i want to know where it went wrong…
DONT FORWARD LINK OF EDITORIAL OR ANY VIDEO…DONT
Codechef long aug
plz reply atleast…
Why is no ta able to reply to this question…is it very difficult for u all??
Plz reply…at the earliest… plz
@S19LPPP0202 here is simple maths regarding your code!
for every testcase you do memset for dp and arr having 5005x5005 elements each, for 100 testcases its 2x100x5005x5005 = 5x10^9 operations only for initializing!(not counting the actual work complexity), hence it is bound to give TLE!!
Also I did this question with 1D DP!
Tell me clearly how do we… calculate the time complexity…
Dowe have to multiply the testcases as well…???or we simply look at n ??..
How do we do it??
since n<1000 couldnt we have used a n*n soln that is what i did…
plz clear this doubt…
it depends upon both n and t, that’s why in the question it’s mentioned that sum of n over all tests is <=5000, also a n*n algorithm will work!, avoid doing memset, initialize only required states with -1 iteratively (as I said earlier it’s a 1D DP problem so think that way).
Since u say that n*n will work therefore I should just iterate instead of memeset and then also this soln should work right???
Suppose there are 1000 test cases and n<=100000 so what time complexity is allowed??is it nlogn or n??
1.but according to u we have nt which becomes 10^8 and hence n should work and not nlogn …
2.also in my code i have used memset 2 times then its time complexity should be added …it should be (2510^8+25*10^8+function time complexity) which should be fine …then why is it giving wrong??
3.what is time complexity of my function code …
plz tell these 3 points…
@S19LPPP0202 please dry run your code, think bit yourself and then ask questions!
answers:
- nt is 10^7, (nlogn)t is 10^8 so both works!!
- your remaining code complexity is N^2 which is fine.
n*t is 10^8 fir the example that i have asked above where n<=100000 and testcases 1000
in this case can we use nlogn???i am sorry i missed one zero …plz clear this doubt…
i am willing to solve this problem using 2d dp only…how to do that since time complexity allowed is n*n…what change should i do in my code then…whether i use memset or mark states -1 iteratively of 2d array…it will take same time only,
see all you should know is that online judges can perform about 10^8 to 10^9 iterations per second, so multiply and judge yourself what will work!
do it this way:
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dp[i][j]=arr[i][j]=-1;
this will take less time as N<=1000
this one is now giving wrong ans …instead of tle…
plz check
my logic is correct for tricky cases as well.
basically i am taking prev means starting point of table and i is current index and i have already precomputed the count of element in every possible start and ending index using array named arr…
so i start from 0 as prev index and count the occurences of a[i] in the range from prev to i
if count ==2 i can have 2 ways either start a new table (this means prev changes to currrent index) or i add the cost (which will be 2) to current table and continue on this table and this way i store the minimum of these 2 options …and store it in dp array…
if count==1 then i simply continue forward in the same table (means prev remains same)
and if count>2 i add 1 to the table cost(this time 1 will be added only to the current tables cost ) and continue or i start a new table(this means prev changes to current index) and find min of these 2 options and store it in dp array…
every time i start a new table i add k to cost.
lets consider a tricky case …
7 3
1 2 3 1 2 2 3
ans should be 8 and my code also gives that
9 3
1 2 3 2 2 2 1 2 3
ans =10 and that is given by my code as well…
plz reply to this logic…
I am computing arr in the following way…
I have used a 2 d array …
remember that value of input will vary from 1 to n…
so first part in 2d array arr represents the no (1 to n) and second part of 2d array represents the index (0 to n-1) and in this way i have stored the total occurences of that particular element starting from 0 index till that index(inclusive) in arr…
so that in my function i can count the total occurenes of element in the range from prev to current index in 0(1) time just by subtracting …which helps to reduce time complexity…
u can also print the arr for any input …u will understand on ur own…
plz now tell me why am i getting wa i am stuck at this for more than 1 week…