hackerbaba's blog

By hackerbaba, history, 18 months ago,

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 ?

• 0

By hackerbaba, history, 18 months ago,

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?

• +3

By hackerbaba, history, 18 months ago,

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.

• 0

By hackerbaba, history, 19 months ago,

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.

• +5

By hackerbaba, history, 19 months ago,

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.

• +4

By hackerbaba, history, 19 months ago,

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.

• +3

By hackerbaba, 19 months ago,

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:

I could solve the first one. But wasn't quite able to understand the 2nd one. 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.

• +4

By hackerbaba, history, 20 months ago,

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))



• +5