Mr_No_One's blog

By Mr_No_One, history, 5 months ago, In English

I have gone through the following materials to learn all the prerequisits to understand the algorithm but still this specific implementation(e-maxx) is difficult to understand. So if anyone can give its explaination then it will be helpful not only to me but to lot more people who will see it in the future as the problem hungarian algorithm for solving assignment problem looks common.

Main algorithm, whose implementation i am finding a bit difficult to understand (use google translator if necessary) The best part of this implementation is that its code is only 30 lines long and it runs in O(n*n*n)

http://e-maxx.ru/algo/assignment_hungary



Good lectures on hungarian algorithm

*.) https://www.youtube.com/watch?v=Wq2tkITYYHE - part 1 of hungarian algorithm ( full lecture)

*.) https://www.youtube.com/watch?v=jZbbayUurSw - part 2 of hungarian algorithm ( till 36:13).



The resources I have gone through to understand prerequisits

*.) https://www.youtube.com/watch?v=HWHjQdNC-7Y - to understand bipartite graph and what is maximum matching

*.) https://www.youtube.com/watch?v=chdr2aj4FUc - matching in general

*.) https://www.youtube.com/watch?v=IQZEURSSr30 - augmented path and how does matching algorithms works in general(i.e. start with 0 cardanility and keeps on increasing cardanality till it reaches M)

*.) https://www.youtube.com/watch?v=opchRZO2YkE - berge's lemma, a matching in a graph is maximum iff there is no augmented path in the graph.

*.) http://e-maxx.ru/algo/kuhn_matching - kuhn's algorithm

Read more »

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

By Mr_No_One, history, 11 months ago, In English

I am solving a question from CSES sum of four values. I found out the time complexity to be O(n^3) and n is 1000. But most of the solutions are within 0.12 seconds. Where I am going wrong with the calculation of time complexity.

Question is :: You are given an array of n integers, and your task is to find four values (at distinct positions) whose sum is x. CSES question link

The approach i am using is to store index of each element in unordered_map and then traverse the array using three loops to find three elements a1 , a2 , a3 and then check if sum-(a1+a2+a3) exists in map. It seems to be O(n^3) or O(n^3 *log n) with map , but it is getting passed within .12 or max .4 seconds. Shouldn't it get TLE verdict when n is 1000. Making O(1000000000).

I would like to know where I am wrong with the calculations.

Read more »

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

By Mr_No_One, history, 12 months ago, In English

I am using the following code to generate TC for hacks for question E of round 640 but the hacking verdict is generator crashed. What does it mean and where I am going wrong.

Link of the crash log https://imgur.com/alUVkUY

from random import randint as rd
print(10)
for i in range(10):
	print(800)
	for j in range(799):
		print(rd(700,799),end=' ')
	print(rd(700,799))
			

Read more »

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

By Mr_No_One, history, 13 months ago, In English

During the last contest (Codeforces Round #634 div3) for the solution of ques D, I submitted multiple solutions which differ from each other very slightly (in order to micro -optimize code to reduce execution time). Now I recieved an email from codeforces that I have cheated. This feels very wrong as I never cheat. Please look into the matter @MikeMirzayanov

https://imgur.com/R9Wed5I

Read more »

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

By Mr_No_One, history, 22 months ago, In English

I am just seeing HACKED in verdict . How to see whether it was a TLE or WA or some other reason?

Read more »

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