arman_ferdous's blog

By arman_ferdous, history, 5 years ago, In English

The problem link : 833B - The Bakery My TLE solution : 29511490

Definition of dp state: dp[s][p] means the maximum total value we can get from the p-th part by putting some amount of boxes starting from s.

And to calculate the number of distinct integers in a range I used a persistent segment tree. First I stored the previous occurance for each number. Then for any interval i to j I only need to see how many numbers in previous[i...j] are less than i. And that is where the persistent seg tree helped me.

So if I am not wrong then at the worst case the dp table will be fully filled so the complexity for the solve() function would be O(n*k*distinct_int_query) in this case it is O(n*k*log n). Building the segment tree at first will take O(n*log n). Afterwards updating for each element will take a total of O(n*log n)

So total complexity would be O(n*k*log n) right? Then why doesn't it pass? Why TLE???

P.S: Most likely I am wrong. So plz tell how to do the wrong thing right.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By arman_ferdous, history, 6 years ago, In English

Recently I wrote this code to find the sum of all the digits of the number until the number turns into a one digit number. For example: number 567, we add all the digits and we get 5+6+7 = 18, now we add all the digits of 18 and we get 1+8 = 9. We can't add anymore digits because there is only one left and thus the result is 9.

Now I am having trouble figuring out the time complexity of this recursive code. Can anyone help?

int digSum(int n)
    if(n < 10) return n;
    return digSum(digSum(n/10) + n%10);

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it

By arman_ferdous, history, 6 years ago, In English

You can easily tell by my rating that I am not a serious type of programmer like most of you are, but I want to become one of you guys too. I am a school boy of class 9. And I know/learnt these things-

  1. I have finished learning C. I code in C++ but actually inside it is C.
  2. Have some basic knowledge about C++ STL library like: queue,stack,map,string,set.
  3. I know what is Dynamic Programming and CAN solve easy DP problems.
  4. Also know a little bit of Graph Theory.
  5. I am good at math and improving everyday.

I couldn't take part in many contests before because of my exams in school. But I can most of the time (like 90%) solve problem A and B in DIV-2 Codeforces Rounds.

Now I am like lost in a lot of things in this programming world, so many things, many many interesting stuff but can't understand most (it is awful). So please tell me what can be my best step from here. Should I practice at some OJ or like learn something new etc. Also I know that there are many people out there who are like me. So your answer could be some help to them as well

P.S: I know my English is not good, sorry about that.

Full text and comments »

  • Vote: I like it
  • -12
  • Vote: I do not like it