I wrote a very straight forward BFS code for SRM 646 Div2 Medium and It kept giving wrong answer on my laptop (case 2, Expected 1000 returning 999).

And I then changed my approach and used DFS with std::map. But it took ~26.3 seconds on my laptop to pass case 2. Having no clue what's going on, I ended up solving only the easiest problem.

However after the contest, I recalled similar incident happened on SRM645(the previous contest). I was getting wrong values while running my code locally on my laptop, but after the contest I coded the same Idea again and got it passed on both my laptop and TopCoder system test. This time I took a step further. I submitted my locally wrong code on TopCoder and wallah, it passed. This makes me both happy and sad at the same time.

Can you suggest what may going wrong? And please suggest your TopCoder Plugin.

This code gives Wa on my laptop but got ac on TopCoder.

• I am using CodeBlocks 13.12 for than 6 months.

• I use TopCoder AutoGen.exe for generating my code.

• My Os is Windows 8.1 Pro

Problem Link

My Solution

Spacial Thanks:

• Prajogo Tio his blog has some nice explanations of some problems and he helped me a lot. (anybody knows his CodeForces User Id??)

• Hasan0540 (I analyzed his code and he helped me understanding his logic, Also my code was motivated by his code)

MY THOUGHTS

Let dp[i][j] is the expected value for guessing i-th song at j-th second. Then, say we want to guess the i th song at 4th second like this,

(a) guess the i th song at 4 th second. and already have guessed the i-1 th song at 3 dh second dp[i][4] = ( dp[i-1][3] +1) X P[i]

+

(b) guess the i th song at 4 th second, and already have guessed the i-1 th song at 2 nd second dp[i][4] = ( dp[i-1][2] +1) X (1- P[i] )X P[i]

+

(c) guess the i th song at 4 th second, and already have guessed the i-1 th song at 1 st second dp[i][4] = ( dp[i-1][1] +1) X (1- P[i] )^2 X P[i]

Now,let's find the idea how The States are compressed by observing another scenario Let we now want to calculate the expected value of guessing the i th song at time 5th second. So what would be the states?

(w) guess the i th song at 5 th second. and already have guessed the i-1 th song at 4 th second dp[i][5] = ( dp[i-1][4] +1) X P[i].

+

(x) guess the i th song at 5 th second, and already have guessed the i-1 th song at 3 rd second dp[i][5] = ( dp[i-1][3] +1) X (1- P[i] )X P[i].

+

(y) guess the i th song at 5 th second, and already have guessed the i-1 th song at 2 nd second dp[i][5] = ( dp[i-1][2] +1) X (1- P[i] )^2 X P[i].

+

(z) guess the i th song at 5 th second, and already have guessed the i-1 th song at 1 st second dp[i][5] = ( dp[i-1][1] +1) X (1- P[i] )^3 X P[i].

Now Observe, if we take (1- P[i] ) out from x + y + z it becomes dp[i][4] So finally we can write, dp[i][5] = w + (1-p[i])*( dp[i][4] ) or dp[i][5] = ( dp[i-1][4] +1) X P[i] + (1-p[i]) X ( dp[i][4] )

So in general :: dp[i][j] = dp[i-1][j-1] X p[i] + dp[i][j-1] X (1-P[i])

Ok the basic part is Over, But there is yet another thing

It was said in the problem that, if we listen to a song for t[i] seconds we can be 100% sure of it's name. If I interpret this in my own way, "when we are at time tx all we calculate is previous t[i] steps from tx, Saying in general, if we are at dp[i][time_x] state , we may want to remove the states that started t[i] second previously than time_x and we may want to add the expected value of the state that represent the 100% guaranty case.

I tried to solve CF Round #261 D. Pashmak and Parmida's problem. But after some attempt I failed to figure out a solution. Then I read the Tutorial and tried to analysis author's Solution .. Still I have no clue how the author's solution is working.

Clearly I am not able to catch the idea. Please someone explain the solution (author's / your own) and help me understand the strategy.

Thanks in advance :)

Hi everyone, Please help me finding out the mistake I did in Greg and Array. I am using Binary Indexed Tree to solve this problem and Implemented the idea of this site (main idea is given below, however, please visit the site for complete documentation of the algorithm)..

My complete code is Available In Pastebin

Algorithm that I tried to Implement:

update(ft, p, v):
    for (; p <= N; p += p&(-p))
        ft[p] += v 	 
 
# Add v to A[a...b] 
update(a, b, v): 	
    update(B1, a, v) 	
    update(B1, b + 1, -v) 	
    update(B2, a, v * (a-1)) 	
    update(B2, b + 1, -v * b) 	 
 
query(ft, b): 	
    sum = 0 	
    for(; b > 0; b -= b&(-b))
        sum += ft[b]
    return sum
 
# Return sum A[1...b]
query(b):
    return query(B1, b) * b - query(B2, b)
 
# Return sum A[a...b]
query(a, b):
    return query(b) - query(a-1)

How can I solve this problem UVA Problem 11297 — Census using Binary Indexed Tree ?

Problem Description in Short : Given a 2D grid (500x500 at most), I need to process 2 types of query.

• Change the value of grid[x][y] by Val
• Output the maximum and minimum number of a sub rectangle of grid (x1,y1) to (x2,y2)

( considering every input is valid ) How can I solve this problem using Binary Indexed Tree? Also it will be a great hand if you help me to understand how Range Minimum or Maximum Query can be done by BIT.

Thanks in Advance :)

Hi, this link refers to a Nice Dynamic Programming Problem . I am thinking how to solve this problem but haven't found any good one. Any suggestion on this problem will be a great hand.

And for future references, I ask you to provide link of this kind of problems. And also if you provide some tutorial of this kind of problems that would be great. :)

Thank you all.. Have a nice day :)

alternate link for this problem

Please Ignore This Post , I have an wrong approach And My Code Misses many cases .

But thank you for visiting my blog

Hello , I am getting Run Time Error in a Nice Dynamic Programming Problem Tile(3) from LightOj.

If you do not have a account in LightOj here is an alternate link.

It will be a great hand if someone help me finding my bug. My code is here

Have a nice day .. Thank You, :)

Hi, I posted some comments on each of the following problem's tutorial blogs, but maybe those comments were not noticed ( As I understand maybe people normally not go to blogs of those problems which they already have solved ). So this is my attempt to get some help from you guys :) . I will posts my problems in comment section on this blog, so that I can get some help in reply section .

Thank you all. Have a nice day :)

The problems I am seeking help is

• 368C - Sereja and Algorithm

• 372C - Watching Fireworks is Fun

(This blog will be edited frequently )

Hi.

This is a Link of a Dynamic programming problem which was published in 2010 Asia Regional Harbin .

I am seeking some help finding the idea to attack this kind of problems. Any kind of suggestion or advice will be a great hand. You can also provide some problems of same category for future references.

The problem statement is given below.

Have a nice day :) .

Problem Description

Given a permutation a1, a2, … aN of {1, 2, …, N}, we define its E-value as the amount of elements where ai > i. For example, the E-value of permutation {1, 3, 2, 4} is 1, while the E-value of {4, 3, 2, 1} is 2. You are requested to find how many permutations of {1, 2, …, N} whose E-value is exactly k.

Input

There are several test cases, and one line for each case, which contains two integers, N and k. (1 <= N <= 1000, 0 <= k <= N).

Output

Output one line for each case. For the answer may be quite huge, you need to output the answer module 1,000,000,007.

Sample Input

3 0

3 1

Sample Output

1

4

Hint There is only one permutation with E-value 0: {1,2,3}, and there are four permutations with E-value 1: {1,3,2}, {2,1,3}, {3,1,2}, {3,2,1}

Source

2010 Asia Regional Harbin

Hi,

I read these articles about Chinese Remainder Theorem on Wolfarm and Wiki but I cannot understand it properly :/ ..

So, I am wondering can any one here help me figuring out what Chinese Remainder Theorem is.. How does it work.. How to use this theorem.. You can also help by giving links of articles and blog posts about this topics ..

Thank You All... Have a Nice Day :)

(P.S. I searched in CodeForces .. But maybe my search id was not good enough to find what I am seeking )

Hello ..

As I am new at this site and I have a question.. When I try to see other's code some times it says Program source is not available. ... I am not sure how I see other's code.. Do I need to participate in several contests to get permission to see other's code?? Or there is other rule except clicking on Submission ID??

Any suggestions will be a great hand, and excepted cordially :)

Thanks to all

Hello everyone .. Welcome to my Blog :)

Some Days ago I coded a solution of this problem .. And my code was

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<iostream>

using namespace std;

int row,col,arr[9][9],sum[9],mask[270];

int rec(int mask)
{
    int cur=__builtin_popcount(mask);
    if(cur==col)
    {
        int MAX=-9;
        int MIN=999999999;

        for(int i=0;i<row;i++)
        {
            MAX=max(MAX,sum[i]);
            MIN=min(MIN,sum[i]);
        }

        return (int) MAX-MIN;
    }

    int ans=999999999;

    for(int i=0;i<col;i++)
    {
        if( (mask & (1<<i)) == 0)
        {
            int POW=pow(10,(cur));

            for(int rr=0;rr<row;rr++)
                sum[rr]+=(POW*arr[rr][i]);

            ans=min(ans,rec(mask|(1<<i)));

            for(int rr=0;rr<row;rr++)
                sum[rr]-=(POW*arr[rr][i]);
        }
    }
    return ans;
}

int main()
{
    scanf(" %d %d",&row,&col);

    for(int i=0;i<row;i++)
        for(int j=0;j<col;j++)
        {
            char tmp;
            scanf(" %c",&tmp);
            arr[i][j]=tmp-'0';
        }

     int ans=(rec(0));
     printf("%d\n",ans);
    return 0;
}

But the funny fact is when I submitted the code if fails to pass first system test .. Then I went to other peoples Accepted codes and tried sample inputs and my code provides correct output for each and every input.. I am freaked out : ) .. And looking forward to have your's ideas about this.. Is this a surver error .. or there a GHOST sitting in CodeForces :)