ivplay's blog

By ivplay, history, 2 months ago, In English,

What is the proof that from any index idx , idx + (idx&-idx) is the next closest index that covers idx? I mean how can I prove that no other index in range ( idx,idx+(idx&-idx) ) actually covers idx? '(' means exclusive and covers idx means contains information of idx ??

Thanks in advance.

Read more »

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

By ivplay, history, 23 months ago, In English,

Original Statement https://community.topcoder.com/stat?c=problem_statement&pm=13268&rd=16187
Problem Summary : Given an array of 1<=N<=47 integers. All the integers are in range [1,47]. Given two number low,high(1<=low<=high<=47). We have pick a sub sequence of the given array in minimum move that contains only the numbers in range [low,high] and all the numbers in range[low,high]. In a single move we can pick a continuous sequence of numbers from the given array. We need to find number of ways to pick such sub sequence in minimum move.
Examples
First line contains the integers. Second and third line contains value of low and high respectively.
(Case 0)
{2, 1, 3}
1
3
Returns: 1
The only way to choose the subset is to choose all animals.
(Case 1)
{3, 4, 1, 3, 4, 2}
1
3
Returns: 2
In the optimal solution we send away animals #2, #3, and #5 (0-based indices). Animals #2 and #3 form one group, animal #5 forms the other.
(Case 2)
{3, 4, 3, 1, 6, 2, 5, 7, 5, 2}
2
6
Returns: 2
(Case 3)
{3, 1, 4}
2
4
Returns: -1
(Case 4)
{2, 1, 3, 1, 4}
1
4
Returns: 1
Note that we are not required to minimize the number of animals we send. Here, we could select just four of these five animals but that would create two groups. A better solution is to select all five animals, then they all form a single group.
(Case 5)
{7, 12, 2, 12, 10, 13, 6, 5, 3, 3, 4, 11, 12, 4, 3, 1, 8, 11, 4, 7, 6, 5, 47}
2
7
Returns: 3 I couldn't figure out the DP idea. Can anyone show me a direction in the problem? Thanks in advance.

Read more »

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

By ivplay, history, 3 years ago, In English,

Problem Link I can think about a n^2 DP approach, But I don't know how to optimize it further :( . Any hints,plz??? Thanks in advance.

EDIT: NICE PROBLEM. SOLVED IT. WROTE A TUTORIAL ON IT. https://www.linkedin.com/pulse/beautiful-composition-data-structure-algorithm-najim-ahmed?published=t

Read more »

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

By ivplay, history, 3 years ago, In English,
  • I am getting hard time with this problem-lightoj 1296 — Again Stone GameThere are N-piles,each pile contains max 2^31 stones. you must have to pick at least one and you can pick at most half of the stones. I have seen solutions of this problem but I still don't understand how it works :(. I will be using term SGN as Sprague-Grundy Number. If a pile has 3 stones what should be its SGN? my analysis says it should be like-
    • SGN(1)=0,
    • SGN(2)= mex(1) = 1, since we must have to take 1 stone, we have only one choice
    • SGN(3)= mex(1) = 1, since we must have to take 1 stone, we have only one choice
    • Now the solution to this problem I have seen says SGN(3) is 0 which unfortunately, I don't understand how :(
  • I have just started to learn Sprague-Grundy Number. I am looking for help to make me understanding how the calculation of SGN is defined for this problem. May be I have misunderstood the meaning of MEX defined in SGN.

Read more »

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

By ivplay, history, 4 years ago, In English,

Given N points. I want to find convex hull keeping collinear points. How should I prepare my initial sort function so that I don't have to make a right turn for points who are collinear? Example: 6 1 1 3 0 2 0 4 1 2 2 0 0  Here is the image for those points. Now I want point F(2,2) comes before point C(1,1) also point B(2,0) comes before point D(3,0) I mean I want following order after sorting A,B,D,E,F,C. what should be my sorting criteria?

Read more »

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

By ivplay, history, 4 years ago, In English,

Read more »

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

By ivplay, history, 4 years ago, In English,

I failed to manage any good resource on 2-SAT that illustrates printing solution for the value of each variable.Basically, I am stuck with this problem: lighoj — 1251 — Forming the Council http://www.lightoj.com/volume_showproblem.php?problem=1251

  • What I did: for each (a v b) I connected -a ->b and -b ->a. Then I run SCC and check if a and -a exist in same component.

But how can I decide value of each variable?

Thanks in advance ...

Read more »

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

By ivplay, history, 4 years ago, In English,
  • I fell into a very interesting situation today , while solving CF — 599D.
  • say long long a = 1000000000000000363,b= 91
  • I wrote long long c = ceil(a*1.0/b) thinking (long * double) / double should be perfect double and ceil(double) — should work out.
  • I was expecting correct answer, c = 10989010989010993, but it produced c= 10989010989010994 , 1 more than the actual — result!!!! Damn to the precision issue.
  • Lesson :

    • Option 1 : Study lot lot and lot about your compiler and how it manages precision while both implicit and explicit cast.
    • Option 2 : Use your own ceil function like this
  • template inline T ceil(T numerator ,T denominator)
  • {
    • return (numerator+denominator-1)/denominator;
  • }
  • Moral : Avoid fraction as much as you can.

Read more »

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

By ivplay, 4 years ago, In English,

Given a tree, you have to remove exactly k edges.Now you get k+1 subtrees. Each has a diameter. You have to say x = maximum of all the diameters. Now you have to minimize x removing exactly k edges.he tree has 50,000 nodes. Can anybody help me with some idea so that I can find a way to solve it? T

Read more »

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

By ivplay, history, 4 years ago, In English,

I just found that topcoder problem archive can not be filtered by probability category. But it has some good practice problems with tutorials for mastering probabilities. Here is the list of some basic and intermediate level problems(div2 500+div1 250) + (div2 1000). Problems are in ascending order of points, so you can attempt them in the order they appear in the list.

Read more »

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

By ivplay, 5 years ago, In English,

It happened to me many times that I submitted my solution without commenting out freopen and got compilation error! How virtual judges determines that I am using freopen/fopen? Interesting part is, I use - #define filein(x) freopen(x,"r",stdin) - #define fileout(x) freopen(x,"w",stdout)

it compiles when I do not call them. but it gets compilation error when I use filein("input.txt"); My question is, is it should be compilation error even though I use it! How they detect it!

Read more »

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

By ivplay, 5 years ago, In English,
 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

By ivplay, 5 years ago, In English,

Please suggest some practice problem for me that needs KMP + DP . I means such problem where the DP states depend on KMP failure function. Thanks in advance.

Read more »

Tags dp, kmp
 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By ivplay, 5 years ago, In English,

Today I found a very interesting fact. int gcc, If you write cout << 5/0 << endl; it will cause a division by zero exception and get RTE. if you write cout << 5.0/0.0 << endl; it will output nan!!!!!!!! cout << atan(5/0) causes RTE while atan(5.0/0.0) causes correct output!

Read more »

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

By ivplay, 5 years ago, In English,

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2767

I am stuck on this problem. I can't formulate the recurrence relation exactly. Can anybody help me to formulate the recurrence relation,please? I can think of three state recurrence f(n,k,largest) = how many was we can express n as sum of k distinct integers where none of the integers is greater than largest. If somehow I could compress the last state(largest) by a and k , I could use matrix exponentiation. But how can I eliminate this state?

Read more »

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

By ivplay, 5 years ago, In English,

This post is only for newbies. A very common trick with Cumulative Sum + BIT is discussed with some examples and problems. Here is the link Thanks for reading.

Read more »

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

By ivplay, 5 years ago, In English,
  • I have some integers 6 , 7 , 9. I want to map them (something like grid compression). Then it should be like :-
  • 6 — > 1
  • 7 — > 2
  • 9 — > 3
  • I tried STL map for(i=1..3) M[arr[i]]=0; then for_each(it,map) (*it).second=++hashValue;
  • Unfortunately I got TLE !
  • Then I used a temporary array (The order of my original array is needed) , sorted it and used a binary search to map them and stored them in another array.
  • But it seems like :-
  • 2 extra array + O(n) to Copy main array into temporary array + O(nlg(n)) to sorting this temporary array + O(nlg(n)) to binary search is faster than simple mapping I mentioned first !!!
  • Is it really true or SPOJ's the great ancient Cluster: Pyramid (Intel Pentium III 733 MHz) machine just fooled me !!! I just can't believe it because my IO method is another great SPOJ template used for IO operation which I believe is faster than scanf/printf.

Read more »

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

By ivplay, 5 years ago, In English,

problem link: http://www.lightoj.com/volume_showproblem.php?problem=1390 my code: http://pastebin.com/gZmFux20 verdict : WA My idea: did a topo sort to find an order then ran a dfs and marked cross edges and removed them. What did i miss !!!

Read more »

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

By ivplay, 5 years ago, In English,

I am trying to learn 2-SAT. All I found is a google translated e-maxx.ru and a wekipedia page. But I could not understand all of them. I understand the graph construction and the impossible case, why and when it does not have solution. its clear to me . But I can not understand the topo sort / start time finish time part inside it. What else information can we extract form 2-SAT besides satisfiable/not?

  • http://codeforces.com/problemset/problem/228/E
  • I found this problem as an exercise of 2-SAT. As i mentioned I understand the graph construction and decision part but I can not understand the topo sort part for path printing (the order that ons all bits).

Read more »

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

By ivplay, 5 years ago, In English,

I have learned suffix array from this pdf:- Suffix arrays – a programming contest approach Adrian Vladu and Cosmin Negruşeri (appearedin GInfo 15/7, November2005)

Whatever there are some very good problems discussed in the pdf , and I want to practice them,test them with my code. Unfortunately I don't find those problems in any OJ or somewhere else to test them. Because some of the descriptions look like "training camp 2003" , i don't know which training camp or where to go. If somebody knows the source of the problems used in this article , please let me know. Sorry for such a large post.

If you are just learnt suffix array, try those problems discussed in this article. those are really awesome.

Read more »

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

By ivplay, 5 years ago, In English,
  • https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2014
  • Short Description:
  • You are given a sequence of N integers (each within the range [0, 2^16 — 1] ) along with P operations and in order to solve this problem you need to process the operations instructed as follows.
  • There are two kinds of operations that you will be instructed to perform:

  • 1) Modification Given a non-negative number T , you need to increase the value of every number in the sequence by T . If the value of any number in the sequence is larger than 2^16 — 1 after the operation, you should divide its value by 2^16 and take the remainder as its value;
  • 2) Query Given a non-negative number T , query how many numbers in the sequence satisfies the condition that its bitwise and result with 2^T is greater than zero.
  • For simplicity, all you need to do here is to output the sum ( sum < 10, 000, 000, 000 ) of the answers to all queries.
  • Can anybody give me some idea to think this problem?

Read more »

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

By ivplay, 5 years ago, In English,

Is there any site where someone can arrange practice contest in IOI style(partial point, special judge)?

Read more »

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

By ivplay, 5 years ago, In English,
  • This post is for those beginners who want to learn and practice matrix exponentiation. I am just here to share my idea on a very basic problem form lightoj(1142).

  • Task is simple A + A^2 + A^3 + ... + A^k =? where A is a n*n matrix.

  • First time I thought ans will progress as geometric sum = (A*((A^k)-1))/A-1. or we can say... (A^(k+1) — A)/(A-1) where one is an Identity matrix. I was stuck in the matrix division portion for a long time. I don't know whether my geometric sum idea is right or wrong but i have another idea that can avoid that division.
  • say A + A^2 + A^3 + ... + A^k = f(k)
  • if(k is even,say k= 2x) we can write
  • f(k=2x) = [A + A^2 + A^3 + ... + A^x ] + [A^(x+1) + A^(x+2) + .... + A^(x+x)]
  • = [A + A^2 + A^3 + ... + A^x ] + [A^x(A + A^2 + A^3 + ... + A^x)]
  • = [A + A^2 + A^3 + ... + A^x ] * (A^x + 1)
  • = f(k/2) * (A^(k/2) + 1)
  • else if K is odd we can write
  • f(K)= [A + A^2 + A^3 + ... A^(k-1)] + A^k = f(k-1)+A^k
  • very good problem for beginners. You can try if you have just started to learn matrix exponentiation.

Read more »

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

By ivplay, 6 years ago, In English,

Mr. 'Jotishi' is a superstitious man. Before doing anything he usually draws some strange figures, and decides what to do next.

One day he declared that the names that contain a string S as substring is unlucky. For example, let S be 'ab', then 'abc', 'cabe', 'pqqab', 'ab' etc are unlucky but 'ba', 'baa' etc are not.

So, he gives you the string S and asks you to find the number of names of length n, which are lucky, that means you have to find the number of strings that don't contain S as substring.

Input Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 109). The next line contains the allowed characters for a name. This non-empty line contains lowercase characters only and in ascending order. The next line contains a string S (1 ≤ length(S) ≤ 50), and S contains characters from the allowed characters only.

Output For each case, print the case number and the total number of names that don't contain S as substring. As the number can be very large, print the number modulo 232.

Sample Input Output for Sample Input 3 3 ab ab 4 acd ca 5 ab aaa Case 1: 4 Case 2: 55 Case 3: 24 //http://www.lightoj.com/volume_showproblem.php?problem=1268

Read more »

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

By ivplay, 6 years ago, In English,

Given 50 integers.Their sum will be less than 5*10^5. We have pick a subset from those numbers and distribute then into two arrays.The sum of integers in both array should be equal.If there are multiple solution we have to maximize the sum.If not possible report that.

Sample: 3 3 4 7 Case 1: 7 3 10 9 2 Case 2: impossible 2 21 21 Case 3: 21 9 15 15 14 24 14 3 20 23 15 Case 4: 64

Constraints: Time Limit: 4 second test cases: 100.memory limit: 32MB

Original Problem:

http://lightoj.com/volume_showproblem.php?problem=1126

I came up with a recursive idea with two states (current_position,current_absolute difference) and three choices,(I will skip number at current position,I will take it in set A,i will take it in set B). I also tried to convert it in iterative but couldn't really do it. Can anybody help me with an idea to this problem.

Read more »

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