Shuaib's blog

By Shuaib, history, 9 years ago, In English

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?

Full text and comments »

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

By Shuaib, 11 years ago, In English
  • Vote: I like it
  • +1
  • Vote: I do not like it

By Shuaib, 12 years ago, In English

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.

Full text and comments »

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

By Shuaib, 12 years ago, In English

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.

Full text and comments »

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

By Shuaib, 12 years ago, In English

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

Full text and comments »

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

By Shuaib, 13 years ago, In English

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


I don't think any of the two had any objectionable material to be deemed unsuitable for the front page. The first one was specially a call for help with a problem, that would have eventually got response from someone (I hope). Coz I also pasted it to Topcoder, and after a few days I indeed got help. The second one was just a suggestion to keep the contest timings well distributed so that not a single party gets affected of bad timezone all the time. Even though disagreeable, but nothing objectionable in it.

So I suggest that blog posts get a new attribute. "Flag!". And it should be the combination of downvotes and flagged numbers that should decide whether or not a post should be pulled from main page. Flag would suggest something objectionable not suitable for front page. That way the posts that a few of the members do not agree with, but could be of interest to others, could still stay on the front page in spite of the downvotes.

How is that?

Regards.

Full text and comments »

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

By Shuaib, 13 years ago, In English
Wow, a 12 hours change from the norm. Most probably I won't be able to participate.

I hope we do not iterate between +/- 12 hours for ever. A more uniformly distributed timings would suit all parties.

Full text and comments »

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

By Shuaib, 13 years ago, In English

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.


Any ideas how to handle such a situation?

The problem in question is this: Distinct Subsequences

Full text and comments »

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

By Shuaib, 13 years ago, In English

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;
}

Full text and comments »

Tags dp, uva
  • Vote: I like it
  • -10
  • Vote: I do not like it

By Shuaib, 13 years ago, In English

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). ;)


I have been reading about Dynamic Programming (DP) lately. I think I've finally got the gist of it. DP isn't an algorithm that you can apply to a certain types of problems. It is essentially just a technique, an optimization technique to be exact. And it can be applied to problems having the following two properties:

  1. Optimal Substructure: What this means is that the solution to larger problem, depends on similar smaller problems. This is essentially the same as a divide and conquer technique, where we divide the problem into smaller sub problems, and solve those to get solution to our bigger problem. But, there is a significant difference between DP and divide and conquer problems, which is...
  2. Overlapping Subproblems: Unlike divide and conquer, DP is applied to problems where sub problems are solved more then once. For example the recursive (which is essentially divide and conquer) solution to merge sort problem divides an array into two distinct arrays, and sorts them independently to get an overall solution. Thus you can't apply DP in this case. But in cases where a certain subproblem might appear more times than once, DP is the way to go. An example of this is the fibonacci series, where to get a certain number in fib series, you have to solve the same sub problem more then once.
When a problem exhibits the above two properties, you can apply DP. Meaning, keep record of subproblems solved, so that the next time you solve a subproblem, you first look it up and see if it has already been solved, avoiding solving it again. Or you can follow a bottom up approach, solving the smaller problems first, before solving the larger problem, iteratively.This can reduce an exponential complexity algorithm to polynomial complexity one.

While it is easy to get the gist of DP, it isn't always that easy to apply in competition, and requires a lot of practice. For example in the recent SRM (520) on Topcoder, I was able to identify that the hard problem in DIV-2 (medium in DIV-1) was a DP problem, but I wasn't able to come up with a proper recursion.

Looking forward to solving a good number of DP problems in coming days... 

Cheers!


Full text and comments »

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

By Shuaib, 13 years ago, In English

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?


C++:

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;
}

Python:

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

Full text and comments »

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

By Shuaib, 13 years ago, In English
It would be awesome to have a Codeforces Events Calendar, marking events for at least up to a month. Possible?

Full text and comments »

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

By Shuaib, 14 years ago, In English
Phew! I am just glad I am still blue, after beta round #66.

Way to go guys. Problems on Codeforces are usually tougher then those on TopCoder. And I love the fact that so many beta rounds happen within a month, compared to low rate of SRMs on TopCoder.

Having said that, CF guys, you really need to hire someone exceptional for checking the problem statements, I guess both for Russian and English versions, to avoid any kind of statements confusion during a round.

Thumbs up!

Full text and comments »

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

By Shuaib, 14 years ago, In English
I realize that CodeForces team would have come up with the codeforces format after giving in a lot of thought, and getting good feedback from their friends. And that they would have also got more feedback now from codeforces community here. But... to make it count, here is a negative feedback.

Guys, the format, simply put, is very boring. After you solve a question or two, you keep on wondering whether to go ahead trying the next problem, or to lock your previous ones and go on a hacking spree. And you wonder what others would be doing. It would be much better to have one work flow for all. Instead of half the participants solving problems, other half hacking them.

I thought you guys had a chat app around here. Is that still here or was that removed? It is always fun to talk to others about the problem set after the round is over.

Having said that... Excellent work guys. Loving it that CodeForces is progressing so quick, and getting quite a bit of focus from big Internet players, and getting sponsorships. Please keep good problem sets rolling in. 

Full text and comments »

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

By Shuaib, 14 years ago, In English
Problem C:

I find the first two consecutive non equal integers, and check whether they are increase or decreasing. Then I look for the next integer that is in the opposite order. (Gives wrong answer on test 18)

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>

using namespace std;

int main()
{
long long n;
vector<long long> v;
cin>>n;
long long x;
for(long long i=0;i<n;i++)
{
cin>>x;
v.push_back(x);
}

if(v.size()<3)
{
cout<<0;
return 0;
}
else
{
int ind=0;
for(long long i=0;i<v.size();i++)
{
if(v[i+1]-v[i]!=0)
{
ind=i;
break;
}
}

for(long long i=ind+2;i<v.size();i++)
{
if((v[ind+1]-v[ind]>0 && v[i]-v[i-1]<0) || (v[ind+1]-v[ind]<0 && v[i]-v[i-1]>0))
{
cout<<"3"<<endl;
cout<<ind+1<<" "<<ind+2<<" "<<i+1;
return 0;
}

}
}
cout<<0;

return 0;
}


Problem D:

I maintain two adjacency matrices, one for connection outside the circle, and one for inside. When a new road is to be build, I check whether there is a road crossing inside/outside between the two cities. (Wrong answer on test 23) 

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>

using namespace std;

bool check(int x, int y, vector<vector<int> > & v)
{
if(x>y)
swap(x, y);
x=x-1;
y=y-1;
for(int i=x+1;i<y;i++)
{
for(int j=0;j<x;j++)
{
if(v[j][i]==1)
return false;
}
for(int j=y+1;j<v[0].size();j++)
{
if(v[j][i]==1)
return false;
}
}
v[x][y]=1;
v[y][x]=1;
return true;
}


int main()
{

int n, m;

cin>>n>>m;
vector<vector<int> > in(n, vector<int>(n, 0));
vector<vector<int> > out(n, vector<int>(n, 0));

int x, y;
vector<char> cv;
for(int i=0;i<m;i++)
{


cin>>x>>y;
if(check(x, y, in))
{
cv.push_back('i');
}
else if(check(x, y, out))
{
cv.push_back('o');
}
else {
cout<<"Impossible";
return 0;
}
}

for(int i=0;i<cv.size();i++)
{
cout<<cv[i];
}
return 0;
}

Full text and comments »

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

By Shuaib, 14 years ago, In English
What's the deal with registering for a round but not being able to participate for some reason... is it going to affect one's rating? 

Full text and comments »

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

By Shuaib, 14 years ago, In English
Will Donald Knuth beat us all if he was put in an algorithms contest (TC SRM/CF Beta Round)?

Full text and comments »

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

By Shuaib, 14 years ago, In English
I think Codeforces needs to put the actual date (plus time in UTC) along with that ticking clock for a competition start time.

Full text and comments »

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