### sanket407's blog

By sanket407, history, 4 years ago,

I am sure most of you must be familiar with union find data structure and the recursive findParent() in it. I usually use array par[] for it. But today i couldnt use array due to large range of values. So i used HashMaps instead. So foll. code was malfunctioning :

return par.get(x) < 0 ? x : (par.put(x, root(par.get(x)))); it was returning x even if par.get(x) > 0.

So i converted it to :

if(par.get(x) < 0)
{
return x;
}
else
{
int p  = root(par.get(x));
par.put(x, p);
return p;
}

And it worked fine . So what why did the first code fail ?? any inputs ??

• -5

By sanket407, history, 5 years ago,

Hey all, Google Code Jam Round 2017 Round 2 will start at MAY 13 14:00 UTC

Just a reminder !!

Top 500 will advance to round 3 !!

Top 1000 will get a T shirt !!

Good luck to all !!

Don't forget to discuss the problems here after the contest !!

GL ! HF !!

UPDATE :: 30 mins to goo !!

• +39

By sanket407, history, 5 years ago,

Hey all .

Getting RE(NZEC) after test 10 on spoj problem COT2. Tried a lot but couldnt get the bug. Even made it as similar to a passed solution.

My solution :

http://ideone.com/PQUMR6

AC Code :

http://ideone.com/qc3GLS

• -13

By sanket407, history, 5 years ago,

Equation is ax — by = k Find non negative integers a,b such that above eq is satisfied and (a+b) is minimum possible. x,y,k are given non negative integers. Problem for reference :: https://www.codechef.com/problems/FLASH Also give a general method for solving such equations . Note: I know the gcd logic which checks the soln exists. I bruteforced values of a but got TLE

• +3

By sanket407, history, 5 years ago,

• +6

By sanket407, history, 5 years ago,

In TCS codevita-2016 round 2 there was a question in which we need to calculate sum of even binomial coefficients like ((nC0)+(nC2)+(nC4)+(nC6)+...+(nCk)) mod 10^9+7 where n and k can be upto 10^14 and k<=n

How do i solve it ?? ( im not sure about the time constraint , It might be greater than the normal 1s)

• +3

By sanket407, history, 6 years ago,

Hey

Used seg trees to store all posters from position 1 to max of queries.

Then Lazy propogation is used and after all poster queries did a last passing of lazy values till bottom.

Then after all poster queries counted values at bottom nodes (stored in wall[])

Can anyone come up with test cases where my code getting WA?

• 0

By sanket407, history, 6 years ago,

Getting tle in java prob: http://www.spoj.com/problems/DQUERY/ Tight time constraints Passed similar GSS1 and GSS3 using fast io sol: http://pastebin.com/9JGxVeFV

Is any optimization possible ?

Thank You

• 0

By sanket407, history, 6 years ago,

Hey guys, Learning 2 sat problem algos.Understood how to solve the normal OR AND expression and find satisfiability. http://codeforces.com/contest/568/problem/C

In the above problem, take ex. rules: 1 V 3 C 3 C 5 C 1 V 5 V

if i understood it right , the boolean expression will be F= (1 XOR 3 ) AND (3 X-NOR 5) AND (1 X-NOR 5) If i am right how do i solve xor clauses? Specifically what will be corr. implications of the xors and xnors to add to implication graph ?