Confused101's blog

By Confused101, history, 7 years ago, In English

Can someone suggest me what are good practices to write more readable codes? Indentation, variable naming, spaces, alignment etc.. also some users who write good looking codes?

thanks,

Full text and comments »

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

By Confused101, history, 8 years ago, In English

I recently saw a problem in some online judge where I was given a tree and was asked the value of Σ f(u, v) for all pair of u, v where f is some function that takes two nodes u, v of a graph. for example f(u, v) can be any of these.

1) f(u, v) = distance between u, v in a weighted tree.
2) If every nodes have number written, f(u, v) can be median / mode / average/ sum of all numbers in path from u to v.
3) if every nodes have colors assigned f(u, v) can be number of distinct colors between path from u to v.

Any Ideas how to solve these kinds of problems?

Full text and comments »

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

By Confused101, history, 8 years ago, In English

For any three integers is N / (x * y) same as N / x / y?

I tried to check for many random values, It comes out to be same. Is it true for any 3 integers N, x, y. How to prove it. Sorry if the question is silly.

Thanks!

Full text and comments »

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

By Confused101, history, 8 years ago, In English

Codechef January long challenge ended recently. I would like to know approches of problem TUPLES and SEACIR [Challenge problem]

Discussions of others problem are also welcome. Thanks!

Full text and comments »

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

By Confused101, history, 8 years ago, In English

Why does Codeforces profile do not contain space for coder's Motto. I like that feature in most of site. Its fun to read Bio and Motto of other coders, Is it possible to introduce it on Codeforces?

Full text and comments »

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

By Confused101, history, 8 years ago, In English
Given an Array A of n elements, (n < 200000), At each step I can transform whole array such that  for every i <= 0 < n, A[i] = A[i - 1] xor A[i + 1]. Is it possible to convert whole array to 000....0 (all zeros) after infinite steps. for example if A = [ 0, 1, 0, 0, 0, 1, 0 ], 
Initial: A = [ 0, 1, 0, 0, 0, 1, 0 ] 
Step 1 : A = [ 1, 0, 1, 0, 1, 0, 1 ] 
Step 2 : A = [ 0, 0, 0, 0, 0, 0, 0 ]

So A can be transferred to zeros after 2 steps.

PS. Consider A[-1] = A[n] = 0, always

I would be highly thankful if someone helps me to solve this task. I saw this problem few days back, will post its link if I found it.

Full text and comments »

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

By Confused101, history, 8 years ago, In English

Can someone help me how to solve this problem. Link Thanks.

Full text and comments »

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

By Confused101, history, 8 years ago, In English

Given N points in one set(S1) and M points in another set(S2), Choose some edges between points from Set S1 to set S2 such that sum of edges(distances) is minimum and every vertex is chosen atleast once.

Can someone help me solving this problem. Thanks!

Full text and comments »

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

By Confused101, history, 8 years ago, In English

Given a function that generates random natural number in range [1, 100], How can I verify if it is truly generating random numbers?

Thanks!

Full text and comments »

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

By Confused101, history, 8 years ago, In English

Given N rectangles which may or may not intersect. Report a random point Inside any rectangle. (probability of every point chosen must be equal). How to solve this problem?

Full text and comments »

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

By Confused101, history, 8 years ago, In English

I was learning suffix array. I want to know what is the need of n*(log n) suffix array construction, are there problems in which n*(log^2n) construction not sufficient. If so, Can someone please provide links to problems.

Thanks!

Full text and comments »

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

By Confused101, history, 8 years ago, In English

Most of the codes used by anta are very generic and uses class template. Can he share his library with codeforces community. It would be very interesting to see his library somewhere in opensource. you can see his submissions here Link

Hoping some reply from anta :D Thanks!

Full text and comments »

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

By Confused101, history, 8 years ago, In English

What are some of the best problemsets in competitive programming contests? (ICPC or IOI practice)

My views: I find USACO Contest problemsets very intersting. Reason: Short and interesting problem statements, nice editorial with nice readable codes.

Which problemset do you find most interesting/challenging?

Full text and comments »

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

By Confused101, history, 8 years ago, In English

Numbers 1....N are written in table (3 <= N <= 1000), at each step one player choose some number and mark it as visited, player wins if he can make 3 consecutive numbers visited in his turn. Who will win the game if both play optimally? game is 2-player game with alternating turns.

Full text and comments »

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

By Confused101, history, 8 years ago, In English

Given string s, find minimum number of operations to convert it into Palindromic string. Operations are: 1) Insert a new character anywhere into the string (including its beginning and end). 2) Remove a single character. 3) Replace a single character by another character.

Full text and comments »

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

By Confused101, history, 8 years ago, In English

Who according to you write most readable(clean & elegant) code here at codeforces. or whose solution do you refer after solving any problem!?

Full text and comments »

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

By Confused101, history, 8 years ago, In English
An ordered triple (a, b, c) is called a triangle triple if a, b, c are positive integers such that there is a triangle with side lengths a, b, c and a positive area.
find number of ordered triplet (a, b, c) such that a <= A, b <= B and c <= C

Input: A, B, C (all between 1 to 10^9)
Output: Number of triplets Mod 10^9 + 7

Problem: [Link] Can someone please help me solving this problem?

Full text and comments »

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

By Confused101, history, 8 years ago, In English
Given a 2D matrix of size nxm (n, m <= 400), Calculate maximum submatrix such that all of its elements are distinct? [maximum submatrix is submatrix whose area is maximum] 
P.S.

Full text and comments »

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

By Confused101, history, 9 years ago, In English

I am looking for some nice implementation of Max-flow & Maximum Bipartite Matching problems, With worst and average case time complexity of Algorithms. Also I want some suggestion about how to start solving problems of these categories.Till now I have solved problem using implementation of Algorithms as black box, which is not good in longer run. So I request CF community to suggest me some good ways to understand implementation and complexities of these algorithms.

Thanks !

Full text and comments »

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

By Confused101, history, 9 years ago, In English

Can anyone help me with this problem:

Problem: Number of Solution of equation x_1 + x_2 + x_3 + ... x_k = N
for all i: x_i>=0 and x_i<=x_(i+1) constraints:[N<= 10^9 k<=10]

[basically non-decreasing solutions]

Full text and comments »

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

By Confused101, history, 9 years ago, In English

I am solving LCS problem from spoj, which is

input: 2 strings of length atmax 250000 characters (S1 & S2) Output: length of the longest common substring of them.

my approach:

   n1 = S1.length() , n2 = S2.length();
   S = S1 + '#' + S2;

   build Suffix_Array (SA[]) and LCP_Array (LCP[]) of string S;
   Ans = 0;
   for(i = 1 to n1+n2 ):
      if( (SA[i-1] < n1 && SA[i] > n1) or (SA[i-1] > n1 && SA[i] < n1))
         if(LCP[i] > Ans)
            Ans = LCP[i];
   return Ans;

Which is giving TLE as time limit for the problem is too strict (0.294s). Can someone please help me with this. Thanks !

Full text and comments »

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

By Confused101, 9 years ago, In English

Since Russian coders does much better in competitive programming I want to know Some sites in russian(Apart from e-maxx) Which are good for learning algorithms and data structures and if possible any code library in C++ like this(Which is mostly in Java). P.S.:: This site is quite good for translation of webpages to english Yandex translate .

Full text and comments »

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