sanket407's blog

By sanket407, history, 7 years ago, In English

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

Full text and comments »

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

By sanket407, history, 8 years ago, In English

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

Full text and comments »

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

By sanket407, history, 8 years ago, In English

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

Full text and comments »

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

By sanket407, history, 8 years ago, In English

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

Full text and comments »

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

By sanket407, history, 8 years ago, In English
  • Vote: I like it
  • +6
  • Vote: I do not like it

By sanket407, history, 8 years ago, In English

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)

Full text and comments »

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

By sanket407, history, 9 years ago, In English

Hey

problem: http://www.spoj.com/problems/POSTERS/

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?

sol: http://pastebin.com/KYcUvpku

Full text and comments »

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

By sanket407, history, 9 years ago, In English

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

Full text and comments »

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

By sanket407, history, 9 years ago, In English

Hey guys, Learning 2 sat problem algos.Understood how to solve the normal OR AND expression and find satisfiability. http://codeforces.me/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 ?

Full text and comments »

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