mansisinha16's blog

By mansisinha16, history, 4 years ago, In English

Hi,

In a recent contest, I came across a problem in which the basic idea was:

"There are x coins of value a and y coins of value b, they must be distributed among N children in such a way that each child gets amount= number_of_coins_of_type_A*a+ number_of_coins_of_typeB*b , number of coins of each type>=0

Find the maximum amount of money that the child with minimum amount among the N can get? "

Any leads or hints regarding the approach would be very helpful.

Thanks in advance.

Full text and comments »

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

By mansisinha16, history, 4 years ago, In English

Hi,

I have just started with learning graphs and was doing a question which involved basic dfs. While doing it, I was getting TLE when I was using iterative dfs and when I only changed the dfs from iterative to recursive, the solution got accepted. Since the time complexity of both the methods are same, the only reason I could think of is the time taken to push and pop in the stack, but I didn't think the difference would be this huge.

These are the links:

Problem: https://mirror.codeforces.com/contest/771/problem/A

iterative solution: https://mirror.codeforces.com/contest/771/submission/87812642

recursive solution: https://mirror.codeforces.com/contest/771/submission/87812583

I am baffled by the difference in the runtime of the 2 solutions. If anyone knows a reason for this, please help me :)

Full text and comments »

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