JacobianDet's blog

By JacobianDet, history, 2 years ago, In English

In the recently concluded Codechef September Lunchtime, I faced a strange behaviour in the Div1 3rd problem. When I wrote the comparator for sorting based on inversions in this way I got SIGSEGV verdict on almost all testcases:

bool cmpx(int A, int B) { if((zz[A] * (sze[B] - zz[B])) < (zz[B] * (sze[A] - zz[A]))) return 0; else return 1; }

But, when I just reversed the condition for A and B in this, all testcases passed:

bool cmpx(int A, int B) { if((zz[B] * (sze[A] - zz[A])) < (zz[A] * (sze[B] - zz[B]))) return 1; else return 0; }

Can anyone explain this strange behaviour as I'm unable to understand this?

Problem Link: https://www.codechef.com/problems/TREEVERS

SIGSEGV Solution: https://www.codechef.com/viewsolution/26846332

AC Solution: https://www.codechef.com/viewsolution/26847767

Read more »

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

By JacobianDet, history, 2 years ago, In English

How to reconstruct all possible solutions of a particular DP problem? I'm not able to get a generalized technique for this and only results for LCS are shown regarding an example of this topic.

Read more »

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

By JacobianDet, history, 3 years ago, In English

Recently in a contest there was a DP problem which used a prefix-sum concept. I tried to implement it in bottom-up as well as in top-down. The bottom-up one got AC'ed but the top-down got a TLE on Test 3. I understand the reason for TLE but I am not able to implement that bottom-up prefix idea for this. Any ideas on how to solve the problem using top-down approach?

Problem link = http://codeforces.com/contest/1068/problem/D

Top-Down solution = https://pastebin.com/VYsA7cXj

Bottom-up solution = https://pastebin.com/5RryJeh5

Read more »

Tags dp
 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

By JacobianDet, history, 3 years ago, In English

Problem Link: https://www.spoj.com/problems/ADAPANEL

The above problem is a mix of SCC and combinatorics. I get that first we need to get the condensed components of the graph, but I am not able to get the idea for the combinatorics part. I know that number of ways to distribute n panel-blocks to n cities has to be calculated in a way like the Integer partition problem, but the constraints are of the order of 2*10^5 and the usual O(n^2) dp method for partition fails to solve this. Any help on this will be very useful to me for solving this problem.

Read more »

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

By JacobianDet, history, 3 years ago, In English

I tried this problem using segment tree but it's getting TLE. Can anybody explain how to remove TLE from this code?

Solution : https://pastebin.com/8iuk4mQp

Problem : http://www.spoj.com/problems/PATULJCI/

Read more »

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

By JacobianDet, history, 3 years ago, In English

I am getting tle in SPOJ GCDEX despite following 'A Dance with mobius function' blog. Please help.

My Solution: https://pastebin.com/TyQzd9Aw

Read more »

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