Hi,

How can I find the sum of digits in a factorial of a number N, where N can be in range [1, 2000]? Can it be done without resorting to BigNum libraries?

http://www.bytehood.com/codeforces-round-186-the-one-that-got-rated/439/

Can someone please help me understand how to approach this problem?

I tried coding a dfs for cycle detection, but I think a cycle in the maze in this problem isn't the same as a cycle in a graph?

Any thoughts very appreciated.

So CR 177 (DIV2) had a general case of the problem where you have to make all the elements in a sequence same, using minimum number of steps. Where each step is incrementing or decrementing an element by constant integer d.

Can anyone shed some light on this problem. How to approach such a problem.

I think codeforces should add rankings (overall plus country) to participants' profiles. No?

Here are two of my posts that got -6 on vote downs, and got pulled off from "Recent Action" section. This, and this. 

The book "Programming Challenges" has some very annoying selection of problems from UVa. In the chapter "Dynamic Programming", the second problem is "Distinct subsequences". The problem is simple DP, but the upper limit on possible result is 10^100. How on earth am I suppose to hold such a value in any of the builtin types in C++. I don't think the UVa judge will let me use any external libraries, would it? If not, the problem isn't only DP, it also requires an implementation of some form of BigInt within the solution.

Can someone please spot a problem with my solution to this UVa problem Is Bigger Smarter.

All the tests I've performed gives me correct result but I keep on getting WA on the judge.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <stack>
 
using namespace std;
bool cmp(pair<pair<int, int>, int> p1, pair<pair<int, int>, int> p2)
{
    if(p1.first.first<p2.first.first)
        return true;
    return false;
}
int main()
{
    int w, iq;
    vector<pair<pair<int, int>, int> > v; // to hold ((weight, iq), index_in_input)
    int i=1;
    while(cin>>w>>iq)
    {
        v.push_back(make_pair(make_pair(w, iq), i));
        i++;
    }
    sort(v.begin(), v.end(), cmp); //sort by weight
    vector<int> dp(v.size(), 1);
    vector<int> s(v.size());
    for(int i=0;i<s.size();i++)
        s[i] = i;
    int max = 1;
    int maxi=0;
    int lmaxi = 0;
    /*
     * In the following loop, find the longest decreasing subsequence on IQ,
     * such that for each successive member, weight is more then the previous
     * one. Also storing index of maximum length found thus far, and the choice
     * made to get till there.
     */
    for(int i=0;i<v.size();i++)
    {
        for(int j=0;j<i;j++)
        {
            if(v[i].first.first>v[j].first.first && v[i].first.second<v[j].first.second)
            {
                dp[i] = dp[j]+1;
                s[i] = j;
                if(dp[i]>max)
                {
                    max = dp[i];
                    maxi = i;
                }
            }
        }
    }
    cout<<max<<endl;
    stack<int> st;
    /*
     * Push choices made to get to the largest subsquence in a stack. And print
     * them in reverse.
     */
    for(int i=0;i<max;i++)
    {
       st.push(v[maxi].second);
       maxi = s[maxi];
    }
    for(int i=0;i<max;i++)
    {
        cout<<st.top()<<endl;
        st.pop();
    }
    return 0;
}

I just realized I do not make much use of this blog. It is my "blog" on codeforces, not a forum. So I can write whatever I feel like (keeping it as close to programming as possible). ;)

It is a bit unfortunate that a solution to problem D in round-85 (div2) implemented in C++ passes system tests, but same solution implemented in Python times out on test case 40. Does that mean Python isn't a good pick for such time constrained problems?

int main()

{

    int n; cin>>n;

    int f[100001]; for(int i=0;i<100001;i++) f[i] = -100000;

    for(int i=0;i<n;i++)

    {

        int x, y;

        cin>>x>>y;

        int r = 0;

        for(int j=1;j*j<=x;j++)

        {

            if(x%j==0)

            {

                int p = x/j;

                int q = j;

                if(f[p]<i-y)

                    r++;

                f[p] = i;

                if(f[q]<i-y)

                    r++;

                f[q] = i;

            }

        }

        cout<<r<<endl;

    }

    return 0;

}

import math

n = int(raw_input())

f = [-100000 for i in range(0, 100001)]

for j in range(0, n):

    x, y  = tuple(int(i) for i in raw_input().strip().split(" "))

    c = 0

    for i in xrange(1, int(math.sqrt(x)+1)):

        if x%i==0:

            q = x/i

            p = i

            if(f[p]<j-y):

                c+=1

            f[p] = j 

            if(f[q]<j-y):

                c+=1

            f[q] = j

    print c