hackerbaba's blog

By hackerbaba, history, 18 months ago, In English

I have just started to solve some game theory problems, and I encountered this, could you please explain as to how in the sample test provided, the result is a draw(0) and not the following?

M: Mouse , C : Cat , -> : goes to node

M -> 3

C -> 4

M -> 5

C -> 3

M -> 0

hence mouse wins.?

What did I understand wrong ?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By hackerbaba, history, 18 months ago, In English

Currently I am solving the Atcoder dp contest. Being new in DP, I am already having a hard time coming up with a valid solution. It gets more tough when most test cases pass. That means my logic is correct. But I am really clueless as to what is to be done when some tests fail.

What do you suggest should be done in this?

Read more »

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

By hackerbaba, history, 18 months ago, In English

I have recently understood handling float and doubles.

Could you please help me understand why this is passing some test cases for the problem whereas failing for some? I probably have created some language error which I am unable to understand.

Any other inputs are appreciated.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By hackerbaba, history, 19 months ago, In English

Could someone please help me with Deque. I tried watching Errichto's explanation and couldn't quite understand it. I was struck on this problem and quite gave up no the whole DP as I found it so tough.

Read more »

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

By hackerbaba, history, 19 months ago, In English

Hello again. Just understood graphs. in this, the author gave a solution of dfs.

I was wondering, as to couldn't it be solved with Breadth First Search? Marking each level as one colour, and the other level as the second colour?

I gave a solution with BFS, but it's giving a wrong output.

Could you please help me out?

Read more »

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

By hackerbaba, history, 19 months ago, In English

Hello again. I am newbie learning graphs, currently doing it in c++ and there are multiple opinions everywhere as to what should be used to implement the (min heap) structure(currently looking into Dijkstra's algo). 1. Should it be PRIORITY QUEUE or MULTISET or SET.? 2. How should the weighted graph be represented in the adjacency list? Currently I started doing a vector<pair<int, int> > with the node as the first element and the weight as the second. Is it right or something else has to be added?

Any other good practices for graphs are appreciated.

Read more »

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

By hackerbaba, 19 months ago, In English

I have just started understanding Dynamic programming. And so after some reading, and understanding some basic sums (knapsack, common sub-sequence, etc ), I went to solve these:

Knapsack 1 and Knapsack 2

I could solve the first one. But wasn't quite able to understand the 2nd one. Errichto's video got me somewhere. could you please solve these few doubts of mine?

  1. Was a different approach used just because of the space complexity of the DP matrix?
  2. These sums gave two definitions of dp table for knapsack. i.) max profit possible till that perfect weight. ii.) min weight required to get that much profit. so for sums NOT lying in the extremities, both of these solutions will give a correct answer? Any other input is appreciated. It's a bit complicated to get my head around DP.

Read more »

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

By hackerbaba, history, 20 months ago, In English

The submission link I tried uploading the following code for a problem statement. And got a runtime error for a large input of 400000 numbers. Could someone please help me understand. I am a bit new and hence am making these kind of mistakes.


no = int(raw_input()) nos = map(int, raw_input().split()) minNo = 10**13 for i in nos: if i < minNo: minNo = i div= [] # print(minNo) for i in range(1, (minNo)/2+2): if minNo % i == 0: div.append(i) div.append(minNo) # print(div) div=set(div) arrToRemove = [] for j in range(len(nos)): for i in div: if nos[j] % i != 0: arrToRemove.append(i) for t in arrToRemove: div.remove(t) print(len(div))

Read more »

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