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?

# | User | Rating |
---|---|---|

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 211 |

2 | awoo | 188 |

3 | Errichto | 186 |

3 | rng_58 | 186 |

5 | SecondThread | 183 |

6 | Um_nik | 176 |

6 | Ashishgup | 176 |

8 | maroonrk | 174 |

9 | antontrygubO_o | 171 |

10 | -is-this-fft- | 169 |

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?

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.

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.

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

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

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>usingnamespacestd;boolcmp(pair<pair<int, int>, int> p1, pair<pair<int, int>, int> p2) {if(p1.first.first<p2.first.first)returntrue;returnfalse; }intmain() {intw, iq; vector<pair<pair<int, int>, int> > v; // to hold ((weight, iq), index_in_input)inti=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(inti=0;i<s.size();i++) s[i] = i;intmax = 1;intmaxi=0;intlmaxi = 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(inti=0;i<v.size();i++) {for(intj=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(inti=0;i<max;i++) { st.push(v[maxi].second); maxi = s[maxi]; }for(inti=0;i<max;i++) { cout<<st.top()<<endl; st.pop(); }return0; }

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:

**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...**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!

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 mathn = 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 = 0for i in xrange(1, int(math.sqrt(x)+1)):if x%i==0:q = x/ip = iif(f[p]<j-y):c+=1f[p] = jif(f[q]<j-y):c+=1f[q] = jprint c

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!

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.

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;

}

Will Donald Knuth beat us all if he was put in an algorithms contest (TC SRM/CF Beta Round)?

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/10/2021 02:47:25 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|