tag:blogger.com,1999:blog-86769562882821658182024-03-06T02:30:28.869+06:00One Problem A DaySabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.comBlogger31125tag:blogger.com,1999:blog-8676956288282165818.post-16650869353212081502012-02-16T13:53:00.002+06:002012-02-19T16:53:20.040+06:00LightOJ 1071 - Baker VaiProblem Link: <a href="http://lightoj.com/volume_showproblem.php?problem=1071">http://lightoj.com/volume_showproblem.php?problem=1071</a><br />
<br />
Problem in short -<br />
<blockquote class="tr_bq">Given an <b>m </b>x<i> </i><b>n</b> grid of numbers, you have move from top-left cell to the bottom-right cell and then get back to top-left cell without stepping on any cell twice and maximizing the sum of the numbers on the path.</blockquote><a name='more'></a><br />
Now, we can think of this problem as finding 2 separate paths (that doesn't cross each other) from top-left to bottom-right while moving only to east or south. My dp solution proceeds row by row and keeps track of 4 states -<br />
<br />
<ol><li>Current row</li>
<li>Current column of left path</li>
<li>Current column of right path</li>
<li>Current move</li>
</ol><div>Here move can be of 3 types - </div><div><ol><li>Moving the left path one cell to the east</li>
<li>Moving the right path once cell to the east</li>
<li>Moving both the path once cell to the south</li>
</ol><div>Here's the source code -</div></div><div><pre class="prettyprint">#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define rep(i,n) for(i=0;i<(n);i++)
#define max(a,b) (((a)>(b))?(a):(b))
#define MAXN 105
int n, m;
int a[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][3];
int go(int row, int c1, int c2, int nextMove) {
if(row == n-1 && c2 == m-1 && c1 == m-2 && nextMove == 0) return 0;
if(dp[row][c1][c2][nextMove] != -1) return dp[row][c1][c2][nextMove];
int &res = dp[row][c1][c2][nextMove];
res = 0;
if(nextMove == 0) { //move the left one to the right
if(c1+1 < c2) res = max(res, go(row, c1+1, c2, 0) + a[row][c1+1]);
res = max(res, go(row, c1, c2, 1)); //finished moving
}
else if(nextMove == 1) { //move the right one to the right
if(c2+1 < m) res = max(res, go(row, c1, c2+1, 1) + a[row][c2+1]);
if(c2 > c1) res = max(res, go(row, c1, c2, 2)); //finished moving
}
else { //move both to the immediate bottom row
if(c1 < c2 && row+1 < n) res = max(res, go(row+1, c1, c2, 0) + a[row+1][c1] + a[row+1][c2]);
}
return res;
}
int main() {
int T, kase=1, i, j;
int res;
scanf(" %d",&T);
while(T--) {
scanf(" %d %d",&n,&m);
rep(i,n) rep(j,m) scanf(" %d",&a[i][j]);
printf("Case %d: ",kase++);
memset(dp, -1, sizeof(dp));
res = go(0, 0, 0, 1) + a[0][0];
printf("%d\n",res);
}
return 0;
}</pre></div><div><br />
</div>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com5tag:blogger.com,1999:blog-8676956288282165818.post-7691317457787664752011-08-21T02:08:00.002+06:002012-02-19T16:58:55.824+06:00UVa 11300 - Spreading the WealthProblem link: <a href="http://uva.onlinejudge.org/external/113/11300.html">http://uva.onlinejudge.org/external/113/11300.html</a><br />
<br />
Problem in short -<br />
<blockquote>Given <b>n</b> people sitting on a circular table, each with some number of coins, you have to redistribute the coins in a manner so that everyone has equal number of coins. Any person can only pass coins to his left or right. Calculate the minimum number of coins that need to be transferred.</blockquote><a name='more'></a><br />
For example, if there were 4 people with 1, 2, 5 and 4 coins respectively, then we'll need to make sure everyone has (1+2+5+4)/4 = 3 coins finally. So, what we can do is, pass 1 coin from the last person to the first person and then third person will give 2 coins to second person who will pass 1 coin to first person. So, in total we'll need 4 transfers.<br />
<br />
Lets define a variable <b>x(p, p+1)</b> = no. of coins that will be transferred from person <b>p</b> to person <b>p+1</b>. Here <b>p+1 = (p+1) mod n</b>. This variable can positive, negative or zero depending on which way the transfer is happening.<br />
<br />
Now, for each person, the difference between transfers from adjacent 2 persons equals difference between his current coins and avg number of coins he should finally get [lets define it <b>per</b>]. Mathematically,<br />
<br />
x(0,1) - x(1,2) = per - a[1]<br />
<br />
Lets define, per - a[i] as <b>A[i]</b>. So, for n persons, we'll get -<br />
<br />
x(0,1) = A[1] + x(1,2)<br />
x(1,2) = A[2] + x(2,3)<br />
.............<br />
x(n-2, n-1) = A[n-1] + x(n-1, 0)<br />
x(n-1, 0) = A[0] + x(0, 1)<br />
<br />
Now, we can rewrite these n linear equations in such a way that there is always a single (and same) variable on the right hand side of the equations -<br />
<br />
x(n-1, 0) = 0 + x(n-1, 0)<br />
x(n-2, n-1) = A[n-1] + x(n-1, 0)<br />
x(n-3, n-2) = A[n-2] + x(n-2, n-1) = A[n-2] + A[n-1] + x(n-1, 0)<br />
..............<br />
x(1,2) = A[2] + A[3] + ... + A[n-1] + x(n-1, 0)<br />
x(0,1) = A[1] + A[2] + A[3] + ... + A[n-1] + x(n-1, 0)<br />
<br />
As the equations tell us, we have to assign a value to <b>x(n-1, 0)</b> such that <b>|x(0,1)| + |x(1,2)| + .... |x(n-1,0)|</b> is minimized. The required value would be the median of the constants in the n equations above.<br />
<br />
Now, to get the median, we can either sort the array first using any O(nlogn) sorting algorithm and then pick the middle element from it. Or we can use a O(n) average time, O(n^2) worst case time algorithm that is similar to randomized quick sort. You can read it further about it on Chapter 7 and 9 of Introduction to Algorithms by CLRS.<br />
<br />
Here's the source code -<br />
<br />
<pre class="prettyprint">#include <stdio.h>
#include <assert.h>
#include <vector>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define MAXN 1000001
#define u64 unsigned long long
#define i64 long long
#define rep(i,n) for(i=0;i<(n);i++)
#define min(a,b) (((a)<(b))?(a):(b))
#define mabs(x) (((x)<0)?(-x):(x))
int n;
u64 a[MAXN];
i64 A[MAXN];
u64 sum, per;
int get_random(int a, int b) { //returns a random number between a & b
int x = rand();
int y = b - a;
x = (int)((x / (double)RAND_MAX) * y) + a;
if(x < a) x = a;
if(x > b) x = b;
return x;
}
// partition the array A[p], A[p+1] ... A[r] in such a way so that
// all the elements left to the pivot element are smaller than it and all the elements right to it are larger than it
// return the pivot element's index
int partition(int p, int r) {
int x = A[r];
int i,j;
i = p-1;
for(j = p; j < r; j++) {
if(A[j] <= x) {
i++;
swap(A[i], A[j]);
}
}
swap(A[i+1], A[r]);
return i+1;
}
// same functionality as partition(), but selects the pivot element randomly so that no particular input can always expose the O(n^2) worst case behaviour
int randomized_partition(int p, int r) {
int i = get_random(p, r);
swap(A[r], A[i]);
return partition(p, r);
}
// select the i-th element largest from the array A[p], A[p+1] ... A[r]
i64 randomized_select(int p, int r, int i) {
if(p == r) return A[p];
int q = randomized_partition(p, r);
int k = q - p + 1;
if(i == k) return A[q];
else if(i < k) return randomized_select(p, q-1, i);
else return randomized_select(q+1, r, i-k);
}
int main() {
int i;
u64 res;
i64 mid;
srand(time(NULL));
while(scanf(" %d",&n) == 1) {
sum = 0;
rep(i,n) {
scanf(" %llu",&a[i]);
sum += a[i];
}
per = sum / n;
rep(i,n) A[i] = (i64)per - (i64)a[i];
for(i=n-2;i>0;i--) A[i] = A[i+1] + A[i];
A[0] = 0;
//sort(A, A+n);
//mid = ( A[n/2] + A[(n-1)/2] ) / 2;
mid = randomized_select(0, n-1, n/2 + 1);
mid += randomized_select(0, n-1, (n-1)/2 + 1);
mid /= 2;
res = 0;
rep(i,n) {
A[i] -= mid;
res += mabs(A[i]);
}
printf("%llu\n",res);
}
return 0;
}
</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com3tag:blogger.com,1999:blog-8676956288282165818.post-40206592592093173952011-07-31T17:57:00.001+06:002012-02-19T16:30:54.070+06:00UVa 11813 - ShoppingProblem Link: <a href="http://uva.onlinejudge.org/external/118/11813.html">http://uva.onlinejudge.org/external/118/11813.html</a><br />
<br />
Problem in short -<br />
<blockquote>Given a weighted undirected graph with around 10^5 nodes and edges and at most 10 store nodes which you must visit, create the minimum distance route starting from a particular node that visits all other nodes and returns to that node.</blockquote><br />
<a name='more'></a><br />
To solve the problem, we'll need the shortest path between each pair of store nodes. To get that we'll run a dijkstra from each possible store node and store the distances to all other nodes. When we know distance between each pair of nodes, we can easily find the optimal route using a bitmask dp where state would be current node we're visiting and set of nodes we've already visited.<br />
<br />
Source code -<br />
<br />
<br />
<pre class="prettyprint">#pragma warning(disable:4786)
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cstdlib>
#include <cstring>
using namespace std;
#define min(a,b) (((a)<(b))?(a):(b))
#define rep(i,n) for(i=0;i<(n);i++)
#define i64 long long
//#define i64 __int64
#define MAXN 100005
#define MAXS 11
typedef pair<int,int> ii;
typedef vector<ii> vii;
i64 INF;
int n,m;
int ns;
int s[MAXS];
vector< pair<int,int> > adj[MAXN];
priority_queue< ii, vii, greater<ii> > pq;
i64 d[MAXS][MAXN];
i64 dp[MAXS][(1<<MAXS)];
void dijkstra(int st, int dex) {
int i;
pair<int, int> t;
rep(i, n) d[dex][i] = INF;
d[dex][st] = 0;
while(!pq.empty()) pq.pop();
pq.push( make_pair(st, 0) );
while(!pq.empty()) {
t = pq.top();
pq.pop();
if(d[dex][t.first] >= t.second) {
rep(i,adj[t.first].size()) {
if(d[dex][t.first] + adj[t.first][i].second < d[dex][adj[t.first][i].first]) {
d[dex][adj[t.first][i].first] = d[dex][t.first] + adj[t.first][i].second;
pq.push( make_pair(adj[t.first][i].first, d[dex][adj[t.first][i].first]) );
}
}
}
}
}
i64 go(int cur, int state) {
if(state == 0) return d[cur][ s[ns-1] ];
if(dp[cur][state] != -1) return dp[cur][state];
i64 &ret = dp[cur][state];
int i;
ret = INF;
rep(i,ns) if( state & (1<<i) ) {
ret = min(ret, go(i, state - (1<<i)) + d[cur][ s[i] ] );
}
return ret;
}
int main() {
int T;
int u,v,d,i;
scanf(" %d",&T);
INF = (1<<30); INF*=INF;
while(T--) {
scanf(" %d %d",&n,&m);
rep(i,n) adj[i].clear();
rep(i,m) {
scanf(" %d %d %d",&u, &v, &d);
adj[u].push_back( make_pair(v,d) );
adj[v].push_back( make_pair(u,d) );
}
scanf(" %d",&ns);
rep(i,ns) scanf(" %d",&s[i]);
s[ns++] = 0;
rep(i,ns) {
dijkstra(s[i], i);
}
memset(dp, -1, sizeof(dp));
printf("%lld\n", go(ns-1, (1<<ns)-1) );
}
return 0;
}</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com3tag:blogger.com,1999:blog-8676956288282165818.post-59787396429146636392011-07-11T19:15:00.003+06:002012-02-19T16:59:52.299+06:00UVa 315 - NetworkProblem Link: <a href="http://uva.onlinejudge.org/external/3/315.html">http://uva.onlinejudge.org/external/3/315.html</a><br />
<br />
Problem in short -<br />
<blockquote>Given an undirected graph with N nodes, we'll need to find no. of articulation points in that graph.</blockquote> I've used the Tarjan's algorithm described in Wikipedia (<a href="http://en.wikipedia.org/wiki/Biconnected_component">http://en.wikipedia.org/wiki/Biconnected_component</a>). There's also an algorithm described here - <a href="http://www.ibluemojo.com/school/articul_algorithm.html">http://www.ibluemojo.com/school/articul_algorithm.html</a> , but this one is probably overly complicated with many variables.<br />
<br />
<a name='more'></a><br />
<br />
For a non-root node to be a <i>non-articulation</i> point, at least one of the nodes lower than that node in the depth first tree need to have a back edge to any node upper in the tree. So, we'll keep track of each node's <i>level</i> (or <i>depth</i>) with root's depth being 0. We'll also define a variable <i>low</i> for each node. <i>low</i> is the lowest depth of neighbours of all descendants of a particular node in the depth-first tree. A node <i>x</i> will be articulation point, if one of its child <i>y</i> has a <i>low</i> value that is greater than or equal depth of node x.<br />
<br />
For a root node to be an <i>articulation</i> point, it has to have more than one child.<br />
<br />
C++ source code follows -<br />
<pre class="prettyprint">#pragma warning(disable:4786)
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <string>
#include <vector>
using namespace std;
#define rep(i,n) for(i=0;i<(n);i++)
#define min(a,b) (((a)<(b))?(a):(b))
#define MAXN 105
int n;
char s[5000];
struct Node {
int level;
int low;
int noChildren;
vector<int> adj;
}nd[MAXN];
int res;
bool isArtic[MAXN];
vector<string> parse(const string& s,const string& delim=" ") {
vector<string>res;
string t;
for(int i=0;i!=s.size();i++) {
if(delim.find(s[i]) != string::npos) {
if(!t.empty()) {
res.push_back(t);
t="";
}
}
else t+=s[i];
}
if(!t.empty()) res.push_back(t);
return res;
}
void dfs(int x) {
nd[x].low = nd[x].level;
int i, y;
rep(i, nd[x].adj.size()) {
y = nd[x].adj[i];
if( nd[y].level == -1) { //unvisited
nd[y].level = nd[x].level + 1;
nd[x].noChildren++;
dfs(y);
nd[x].low = min(nd[x].low, nd[y].low);
if(nd[x].level > 0 && nd[y].low >= nd[x].level) { // x is a non-root node and there's no way from y to any upper level of x
isArtic[x] = 1;
}
}
else if (nd[y].level < nd[x].level - 1) { //y's depth is lower than x's parent....so its a back edge
nd[x].low = min(nd[x].low, nd[y].level);
}
}
if(nd[x].level == 0) { //root node
if(nd[x].noChildren >= 2) isArtic[x] = 1;
}
}
int main() {
vector<string> vs;
int i;
int u,v;
while(scanf(" %d",&n)==1) {
if(n == 0) break;
gets(s); //garbage
rep(i,n) nd[i].adj.clear(), nd[i].noChildren = 0, nd[i].low = nd[i].level = -1;
while(gets(s)) {
vs = parse(s);
if(vs.size() == 1 && vs[0] == "0") break;
u = atoi(vs[0].c_str()) - 1;
for(i=1;i<vs.size();i++) {
v = atoi(vs[i].c_str()) - 1;
nd[u].adj.push_back(v);
nd[v].adj.push_back(u);
}
}
memset(isArtic, 0, sizeof(isArtic));
nd[0].level = 0;
dfs(0);
res = 0;
rep(i,n) if(isArtic[i]) res++;
printf("%d\n",res);
}
return 0;
}</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com5tag:blogger.com,1999:blog-8676956288282165818.post-91732290481188608122011-07-11T01:56:00.002+06:002012-02-19T17:00:10.670+06:00UVa 10158 - WarProblem Link: <a href="http://uva.onlinejudge.org/external/101/10158.html">http://uva.onlinejudge.org/external/101/10158.html</a><br />
<br />
This is a disjoint set data structure problem, but with a twist. In this problem, there are around 10000 people and 4 types of operations on them -<br />
<blockquote>setFriends(x, y) shows that x and y are from the same country<br />
setEnemies(x, y) shows that x and y are from different countries<br />
areFriends(x, y) returns true if you are sure that x and y are friends<br />
areEnemies(x, y) returns true if you are sure that x and y are enemies</blockquote><blockquote><br />
<a name='more'></a><br />
The first two operations should signal an error if they contradict with your former knowledge. The two relations ‘friends’ (denoted by ~) and ‘enemies’ (denoted by *) have the following properties: </blockquote><blockquote>~ is an equivalence relation, i.e.<br />
1. If x ~ y and y ~ z then x ~ z (The friends of my friends are my friends as well.)<br />
2. If x ~ y then y ~ x (Friendship is mutual.)<br />
3. x ~ x (Everyone is a friend of himself.) </blockquote><blockquote>* is symmetric and irreflexive<br />
4. If x * y then y * x (Hatred is mutual.)<br />
5. Not x * x (Nobody is an enemy of himself.) </blockquote><blockquote>Also<br />
6. If x * y and y * z then x ~ z (A common enemy makes two people friends.)<br />
7. If x ~ y and y * z then x * z (An enemy of a friend is an enemy.) </blockquote><blockquote>Operations setFriends(x, y) and setEnemies(x, y) must preserve these properties.</blockquote><br />
Now, to keep track of the friends, we'll need the usual union find data structure. And to keep track of the enemies, I have used a list from each of the root nodes of different sets. Whenever we join two sets, we need to update the lists properly.<br />
<br />
I've designed my solution so that these two properties are always true at any point of execution -<br />
<br />
<ol><li>If two people are friends, they must be on the same set (even if they are not defined as friends, rather they are the common enemies of someone)</li>
<li>If two people are enemies, that must be indicated on both peoples adjacency list.</li>
</ol><div>I've attached the code that should explain the details of the algorithm. Check the comments - </div><div><pre class="prettyprint">#include <stdio.h>
#include <vector>
using namespace std;
#define MAXN 10005
#define rep(i,n) for(i=0;i<(n);i++)
struct Node {
int parent, rank;
vector< int > enemyList;
} nd[MAXN];
int n;
int findSet(int x) { //returns the root of node x
if(nd[x].parent == x) return x;
return nd[x].parent = findSet(nd[x].parent);
}
void setFriends(int x, int y) {
x = findSet(x);
y = findSet(y);
if(x == y) return; //already friends
int i;
rep(i, nd[y].enemyList.size()) if(nd[y].enemyList[i] == x) { //already enemies
printf("-1\n");
return;
}
int j;
if(nd[x].rank < nd[y].rank) { //y will be parent of x
nd[x].parent = y;
//transfer x's enemyList to y's
rep(i, nd[x].enemyList.size()) {
nd[y].enemyList.push_back(nd[x].enemyList[i]);
//update the enemy's list - change x to y as y is the new root
rep(j, nd[nd[x].enemyList[i]].enemyList.size()) {
if(nd[nd[x].enemyList[i]].enemyList[j] == x) nd[nd[x].enemyList[i]].enemyList[j] = y;
}
}
nd[x].enemyList.clear();
}
else if(nd[x].rank > nd[y].rank) { //x will be parent of y
nd[y].parent = x;
rep(i, nd[y].enemyList.size()) {
nd[x].enemyList.push_back(nd[y].enemyList[i]);
rep(j, nd[nd[y].enemyList[i]].enemyList.size()) if(nd[nd[y].enemyList[i]].enemyList[j] == y) nd[nd[y].enemyList[i]].enemyList[j] = x;
}
nd[y].enemyList.clear();
}
else { //x & y same rank...so x will be parent of y with x's rank increasing by one
nd[y].parent = x;
rep(i, nd[y].enemyList.size()) {
nd[x].enemyList.push_back(nd[y].enemyList[i]);
rep(j, nd[nd[y].enemyList[i]].enemyList.size()) if(nd[nd[y].enemyList[i]].enemyList[j] == y) nd[nd[y].enemyList[i]].enemyList[j] = x;
}
nd[y].enemyList.clear();
nd[x].rank++;
}
}
void setEnemies(int x, int y) {
x = findSet(x);
y = findSet(y);
if(x == y) { //already friends
printf("-1\n");
return;
}
int i;
rep(i, nd[y].enemyList.size()) {
if(nd[y].enemyList[i] == x) { //already enemies
return;
}
}
int j;
//check if x & y both have a common enemy - that will be a contradiction
rep(i, nd[x].enemyList.size()) {
rep(j, nd[y].enemyList.size()) {
if(nd[x].enemyList[i] == nd[y].enemyList[j]) {
printf("-1\n");
return ;
}
}
}
//set all y's enemies as x's friends
rep(i, nd[y].enemyList.size()) {
setFriends(x, nd[y].enemyList[i]);
}
//set all x's enemies as y's friends
rep(i, nd[x].enemyList.size()) {
setFriends(nd[x].enemyList[i], y);
}
//do this as x & y's roots may have been changed
x = findSet(x);
y = findSet(y);
nd[x].enemyList.push_back(y);
nd[y].enemyList.push_back(x);
}
int main() {
int i;
int c,x,y;
while(scanf(" %d",&n) == 1) {
rep(i,n) nd[i].parent = i, nd[i].rank = 0, nd[i].enemyList.clear(); //make set
while(scanf(" %d %d %d",&c, &x, &y) == 3) {
if(c == 0) break;
if(c == 1) { //set friends
setFriends(x,y);
}
else if(c == 2) { //set enemies
setEnemies(x,y);
}
else if(c == 3) { //are friends
x = findSet(x);
y = findSet(y);
if(x == y) printf("1\n"); else printf("0\n");
}
else { //are enemies
x = findSet(x);
y = findSet(y);
rep(i, nd[x].enemyList.size()) if(nd[x].enemyList[i] == y) {
printf("1\n");
break;
}
if(i == nd[x].enemyList.size() ) printf("0\n");
}
}
//printf("\n");
}
return 0;
}</pre></div>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com6tag:blogger.com,1999:blog-8676956288282165818.post-52036800190107069552011-07-07T12:42:00.002+06:002012-02-19T17:00:26.513+06:00SPOJ IKEYB - I-KeyboardProblem Link: <a href="https://www.spoj.pl/NSUDP/problems/IKEYB/">https://www.spoj.pl/NSUDP/problems/IKEYB/</a><br />
<br />
Description for this problem is really long. In short -<br />
<blockquote>Given the set of keys on a keypad, a set of letters to assign on those keys sequentially and each letters' frequency on a dictionary, you have to design an optimal keypad layout (assign letters to keys) such that overall typing price is lowest. The price is determined as the sum of the prices of each letter. The price of a letter is a product of the letter frequency (Fi) and its position on the key.</blockquote><br />
<a name='more'></a><br />
<br />
Now we can construct a dynamic programming solution to calculate the best solution taking <b>k</b> keys and <b>l</b> letters. If we know the solution for (<i>k</i>,<i>l</i>) then we can build solutions for (<i>k+1</i>,<i>l+1</i>), (<i>k+1</i>, <i>l+2</i>) .... (<i>k+1</i>, <i>L-1</i>) by assigning <i>1, 2, ... L-1-l</i> letters respectively on key <i>k+1</i>. Initialization of this approach is trivial - we'll assign 1, 2, ... L letters on the first key.<br />
<br />
We'll also need to track which letter is assigned to which key. So for each (<i>key, end letter</i>) pair, we'll need to store the starting index of the letter for this particular key.<br />
<br />
Time complexity of this solution is <b>O(K*L^2)</b> and memory complexity <b>O(K*L)</b>. Do you know any better way to solve this problem?<br />
<br />
Source code -<br />
<br />
<pre class="prettyprint">#include <stdio.h>
#define rep(i,n) for(i=0;i<(n);i++)
#define MAXL 95
#define MAXK 95
#define INF 1023456789
int K,L, F[MAXL];
char keys[MAXK], letters[MAXL];
int dp[MAXK][MAXL];
int pi[MAXK][MAXL];
void solve() {
int i,j,k,cur;
rep(i,K) rep(j,L) dp[i][j] = INF;
rep(i, K) {
if(i == 0) { //initialize for first key
rep(j, L) {
if(j == 0) {
dp[i][j] = F[j];
pi[i][j] = 0;
}
else {
dp[i][j] = dp[i][j-1] + F[j] * (j+1);
pi[i][j] = 0;
}
}
continue;
}
rep(j,L) if(dp[i-1][j] < INF) {
cur = 0;
for(k=j+1;k<L;k++) {
cur += F[k] * (k-j);
if(dp[i-1][j] + cur < dp[i][k]) {
dp[i][k] = dp[i-1][j] + cur;
pi[i][k] = j+1;
}
}
}
}
}
void print(int k, int l) {
if(k < 0) return;
print(k-1, pi[k][l]-1);
printf("%c: ",keys[k]);
int i;
for(i=pi[k][l];i<=l;i++) printf("%c",letters[i]);
printf("\n");
}
int main() {
int T,kase=1;
int i;
scanf(" %d",&T);
while(T--) {
printf("Keypad #%d:\n",kase++);
scanf(" %d %d",&K,&L);
scanf(" %s",keys);
scanf(" %s",letters);
rep(i,L) scanf(" %d",&F[i]);
solve();
print(K-1,L-1);
printf("\n");
}
return 0;
}</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com5tag:blogger.com,1999:blog-8676956288282165818.post-34244532592033396532011-07-03T15:50:00.002+06:002012-02-19T17:00:41.034+06:00SPOJ PT07X - Vertex CoverProblem Link : <a href="https://www.spoj.pl/problems/PT07X/">https://www.spoj.pl/problems/PT07X/</a><br />
<br />
This is a classic dynamic programming problem. We'll need to find minimal vertex cover of an unweighted, undirected tree.<br />
<br />
<a name='more'></a><br />
<br />
We'll try to find the optimal solution for the subtree rooted at each node considering either its parent is covered (and as such the edge between it and its parent) or its parent is not covered. In the first case, we have the freedom to either cover the current node or not. But in the second case, we must cover the current node. Optimal solution is the one that uses least nodes.<br />
<br />
Source code follows -<br />
<br />
<pre class="prettyprint">#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define min(a,b) (((a)<(b))?(a):(b))
#define rep(i,n) for(i=0;i<(n);i++)
#define MAXN 100000
vector<int> adj[MAXN+2];
int n;
int dp[MAXN+2][2];
int go(int cur, int parent, bool isParentCovered) {
if(dp[cur][isParentCovered] != -1) return dp[cur][isParentCovered];
int &ret = dp[cur][isParentCovered];
ret = 0;
int i, r;
if(isParentCovered) {
rep(i, adj[cur].size()) if(adj[cur][i] != parent) {
ret += go(adj[cur][i], cur, false);
}
r = 1;
rep(i, adj[cur].size()) if(adj[cur][i] != parent) {
r += go(adj[cur][i], cur, true) ;
}
ret = min(ret, r);
}
else {
ret = 1;
rep(i, adj[cur].size()) if(adj[cur][i] != parent) {
ret += go(adj[cur][i], cur, true) ;
}
}
return ret;
}
int main() {
int i,u,v;
int r1,r2;
while(scanf(" %d",&n) == 1) {
for(i=1;i<=n;i++) adj[i].clear();
for(i=1;i<n;i++) {
scanf(" %d %d",&u,&v);
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(dp,-1,sizeof(dp));
r1 = 1;
rep(i,adj[1].size()) r1 += go(adj[1][i], 1, true);
r2 = 0;
rep(i, adj[1].size()) r2 += go(adj[1][i], 1, false);
printf("%d\n",min(r1,r2));
}
return 0;
}</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com8tag:blogger.com,1999:blog-8676956288282165818.post-75902489674925455382011-07-03T12:20:00.002+06:002012-02-19T17:01:04.333+06:00UVa 10820 - Send A TableProblem Link : <a href="http://uva.onlinejudge.org/external/108/10820.html">http://uva.onlinejudge.org/external/108/10820.html</a><br />
<br />
This is an straight forward <a href="http://mathworld.wolfram.com/TotientFunction.html">Euler Totient Function</a> problem. Given <b>N</b>, you have to find the sum of Totient Function of every number from <b>1</b> to <b>N</b>.<br />
<br />
Now calculating Totient Function or Phi Function on each test case would be too slow. We need to pre-calculate Totient Function of every integer upto 50000. To do this, we can modify the Sieve method and utilize the following properties - <br />
<br />
<a name='more'></a><br />
<br />
<i>phi(n) = n - 1</i>, if <b>n</b> is prime<br />
<i>phi(n) = n * (p1 - 1)/p1 * (p2 - 1)/p2 * (p3 - 1)/p3 * ...</i>, where <b>p1</b>, <b>p2</b>, <b>p3</b>, ... are the prime factors of <b>n</b><br />
<br />
We can initialize <i>phi(n)</i> to <b>n</b> for every number and during the Sieve, for each prime number, we adjust the Phi value of its multiples according to second formula above.<br />
<br />
After the Sieve is finished, we assign every prime number's Phi value to <b>n-1</b>.<br />
<br />
Source code follows - <br />
<br />
<pre class="prettyprint">#include <stdio.h>
#define MAXSIEVE 50000
char isPrime[MAXSIEVE+2];
int phi[MAXSIEVE+2];
int sum[MAXSIEVE+2];
void sieve() {
int i,j,k=MAXSIEVE/2;
for(i=1;i<=MAXSIEVE;i++) phi[i] = i;
phi[1] = 0;
for(i=2;i<=k;i++) if(!isPrime[i]) {
for(j=i+i;j<=MAXSIEVE;j+=i) {
isPrime[j] = 1;
phi[j] = (phi[j] / i) * (i-1);
}
}
for(i=2;i<=MAXSIEVE;i++) if(!isPrime[i]) phi[i] = i-1;
for(i=1;i<=MAXSIEVE;i++) sum[i] = sum[i-1] + phi[i];
}
int main() {
int n;
sieve();
while(scanf(" %d",&n)==1 && n) {
printf("%d\n",2*sum[n]+1);
}
return 0;
}
</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com1tag:blogger.com,1999:blog-8676956288282165818.post-14334443938645915072010-12-10T06:16:00.001+06:002012-02-19T16:33:10.487+06:00SPOJ QTREE2I'm back after a long <a href="http://one-problem-a-day.blogspot.com/2010/12/break.html">break</a>; longer than I anticipated. I was reading a <a href="http://www.topcoder.com/tc">Topcoder</a> <a href="http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor">tutorial</a> on Range Minimum Query (<a href="http://en.wikipedia.org/wiki/Range_Minimum_Query">RMQ</a>) and Lowest Common Ancestor (<a href="http://en.wikipedia.org/wiki/Lowest_common_ancestor">LCA</a>) problems. Here's a comparison table of the algorithms presented in the tutorial -<br />
<br />
<a name='more'></a><br />
<br />
<b><u>RMQ Algorithms</u></b><br />
<br />
<table border="1" style="text-align: center;"><tbody>
<tr><th>Algorithm</th><th>Time Complexity <br />
(pre-processing, per-query)</th><th>Memory Complexity</th><th>Compatibility with dynamic data</th></tr>
<tr><td>SQRT(N) Segment Algorithm</td><td>O(N), O(sqrt(N))</td><td>O(N)</td><td>Compatible</td></tr>
<tr><td>Sparse Table</td><td>O(NlogN), O(1)</td><td>O(NlogN)</td><td>Not compatible</td></tr>
<tr><td>Segment Tree</td><td>O(N), O(logN)</td><td>O(N)</td><td>Compatible</td></tr>
</tbody></table><br />
<b><u>LCA Algorithms</u></b><br />
<br />
<table border="1" style="text-align: center;"><tbody>
<tr><th>Algorithm</th><th>Time Complexity <br />
(pre-processing, per-query)</th><th>Memory Complexity</th></tr>
<tr><td>SQRT(H) Segment Algorithm</td><td>O(N), O(sqrt(N))</td><td>O(N)</td></tr>
<tr><td>Dynamic programming<br />
(similar to Sparse Table)</td><td>O(NlogN), O(logN)</td><td>O(NlogN)</td></tr>
</tbody></table><br />
LCA problems can be converted to restricted RMQ problems where consecutive elements differ by at most 1 in O(N) time. RMQ problems can also be converted to LCA problem using Cartesian tree in O(N) time. So, in turn, we can convert any RMQ problem to a restricted RMQ problem by first converting it to LCA and then to RMQ again. Restricted RMQ can be solved using a <O(N), O(1)> algorithm.<br />
<br />
<br />
This problem's <a href="https://www.spoj.pl/problems/QTREE2/">link</a> was given at the end of the tutorial as practice problem.<br />
<br />
In this problem<br />
<blockquote>you are given a weighted tree with <b>N</b> nodes (<b>N<=10000</b>) followed by some queries. Queries can be of 2 types - <b>DIST</b> and <b>KTH</b>. In a <b>DIST</b> query, you have to calculate the distance between 2 nodes and in a <b>KTH</b> query, we have to print the <b>k</b>-th node on the path from a particular node to another.</blockquote>Firstly, I have selected a random node as the root of the tree and then ran a DFS to calculate distance to each node from the root. Now, distance between 2 nodes can be easily calculated if we know their LCA.<br />
<blockquote><b>Dist(a,b) = Dist(root, a) + Dist(root,b) - 2 * Dist(root, LCA)</b></blockquote> I've used the dynamic programming solution similar to Sparse Table for finding the LCA. In this algorithm, we store the <b>2^j</b>-th ancestor of each node <b>i</b>. Read the <a href="http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor">tutorial</a> for details.<br />
<br />
Now, when finding the <b>k</b>-th node on the path from <b>a</b> to <b>b</b>, we need to first determine on which segment this <b>k</b>-th node appears<br />
<br />
<ul><li>a to LCA</li>
<li>LCA to b</li>
</ul><div>If it is on the 2nd segment, we can just swap the nodes and change the value of <b>k</b> accordingly. Then we're left with finding <b>k</b>-th ancestor of a particular node. This can be done utilizing the ancestor array that we pre-computed.</div><div><br />
</div><div>C++ source code below - </div><br />
<pre class="prettyprint">/*
Problem Name : QTREE2
Problem Number : SPOJ 913
Link : https://www.spoj.pl/problems/QTREE2/
Problem Type : Search, LCA
Difficulty : 7 / 10
Interest : 9 / 10
Complexity : O(NlogN), O(logN)
Date : December 10, 2010
*/
#include <stdio.h>
#include <vector>
#include <time.h>
#include <string>
#include <assert.h>
#include <algorithm>
using namespace std;
#define rep(i,n) for(i=0;i<(n);i++)
#define MAXN 10000
#define MAXLOGN 14
//#define i64 __int64
#define i64 long long
vector< pair<int,int> > adj[MAXN+1];
int n;
i64 d[MAXN+1];
char flag[MAXN+1];
int root;
int L[MAXN+1];
int father[MAXN+1];
int A[MAXN+1][MAXLOGN+1];
i64 INF = 10000000;
void dfs(int cur) {
flag[cur] = true;
int i;
rep(i,adj[cur].size()) {
if(!flag[adj[cur][i].first]) {
d[adj[cur][i].first] = d[cur] + adj[cur][i].second;
father[adj[cur][i].first] = cur;
L[adj[cur][i].first] = L[cur] + 1;
dfs(adj[cur][i].first);
}
}
}
vector<string> parse(const string& s,const string& delim=" ") {
vector<string>res;
string t;
for(int i=0;i!=s.size();i++) {
if(delim.find(s[i]) != string::npos) {
if(!t.empty()) {
res.push_back(t);
t="";
}
}
else t+=s[i];
}
if(!t.empty()) res.push_back(t);
return res;
}
void pre_process() {
int i,j;
for(i=1;i<=n;i++) for(j=0;(1<<j)<=n;j++) A[i][j] = -1;
for(i=1;i<=n;i++) A[i][0] = father[i];
for(j=1;(1<<j)<=n;j++) for(i=1;i<=n;i++) if(A[i][j-1] != -1) A[i][j] = A[A[i][j-1]][j-1];
}
int getLCA(int p, int q) {
int i,log;
if(L[p] < L[q]) swap(p,q);
for(log=1;(1<<log)<=L[p];log++);
log--;
for(i=log;i>=0;i--) if(L[p] - (1<<i) >= L[q]) p = A[p][i];
if(p == q) return p;
for(i=log;i>=0;i--) {
if(A[p][i] != -1 && A[p][i] != A[q][i]) {
p = A[p][i];
q = A[q][i];
}
}
return father[p];
}
int getKth(int p, int q, int k, int LCA) {
int d,log,i;
if(LCA == p) {
d = L[q] - L[p] + 1;
swap(p,q);
k = d - k + 1;
}
else if(LCA == q) ;
else {
if(L[p] - L[LCA] + 1 < k) {
d = L[p] + L[q] - 2 * L[LCA] + 1;
k = d - k + 1;
swap(p,q);
}
}
for(log=1;(1<<log)<=L[p];log++);
log--;
k--;
for(i=log;i>=0;i--) if((1<<i) <= k) {
p = A[p][i];
k -= (1<<i);
}
return p;
}
int main() {
int T;
int i,a,b,c,k;
i64 res;
char s[100];
int LCA;
INF *= INF;
vector<string> vs;
scanf(" %d",&T);
srand(time(NULL));
while(T--) {
scanf(" %d",&n);
for(i=1;i<=n;i++) adj[i].clear(), d[i] = INF, flag[i] = false;
for(i=1;i<n;i++) {
scanf(" %d %d %d",&a,&b,&c);
adj[a].push_back(make_pair(b,c));
adj[b].push_back(make_pair(a,c));
}
root = rand() % n + 1;
d[root] = 0;
father[root] = -1;
L[root] = 0;
dfs(root);
pre_process();
gets(s);
while(gets(s)) {
if(s[1] == 'O') break;
vs = parse(s);
a = atoi(vs[1].c_str());
b = atoi(vs[2].c_str());
LCA = getLCA(a,b);
assert(LCA >= 1 && LCA <= n);
if(vs[0] == "DIST") {
if(LCA == a || LCA == b) res = abs(d[a] - d[b]);
else res = d[a] + d[b] - 2 * d[LCA];
}
else if(vs[0] == "KTH") {
k = atoi(vs[3].c_str());
res = getKth(a,b,k,LCA);
}
else assert(0);
printf("%lld\n",res);
}
printf("\n");
}
return 0;
}</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com14tag:blogger.com,1999:blog-8676956288282165818.post-80304811503018894032010-12-03T23:46:00.000+06:002010-12-03T23:46:42.331+06:00BreakI'm taking another break for 3 days; currently overloaded with project works; need to reduce the workload to a maintainable amount.Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com0tag:blogger.com,1999:blog-8676956288282165818.post-12417459769670827192010-12-02T18:18:00.001+06:002012-02-19T16:33:40.062+06:00SPOJ MMOD29Problem Link : <a href="http://www.spoj.pl/problems/MMOD29/en/">http://www.spoj.pl/problems/MMOD29/en/</a><br />
<br />
I was searching some problems that would require <a href="http://en.wikipedia.org/wiki/Modular_multiplicative_inverse">modular inverse</a> / <a href="http://en.wikipedia.org/wiki/Chinese_remainder_theorem">Chinese remainder theorem</a> / <a href="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm">Extended Euclidean algorithm</a>. This problem requires the simplest case of modular inverse when the numbers in question are co-prime.<br />
<br />
The problem in short<br />
<blockquote>Find the sum of divisors of the number 2004^X mod 29 [1<=X<=10000000].</blockquote>So, first we need to find the sum of divisors of an arbitrary number N. Let prime factorization of N is -<br />
<a name='more'></a><br />
<blockquote>N = (p1^a1) * (p2^a2) * ...... * (pn^an)</blockquote>Then the sum of its divisors would be -<br />
<blockquote>S = (1 + p1 + ... + p1^a1) * (1 + p2 + ... + p2^a2) * ...... * (1 + pn + ... + pn^an)</blockquote> = (p1^(a1+1) - 1) / (p1 - 1) * (p2^(a2+1) - 1) / (p2 - 1) * ...... * (pn^(an+1) - 1) / (pn - 1)<br />
<br />
You need to calculate S mod 29. The problem is all the terms in S are of the form (x/y). To calculate (x/y) mod m, we need to find a z such that -<br />
<blockquote>(1/y) congruent to z (mod m)</blockquote>If y and m are co-prime, then it is very easy to find. Modular inverse z would be<br />
<blockquote>z = y ^ (phi(m) - 1) mod m</blockquote>As m is a prime number in this problem, it will be co-prime with the prime factors of 2004 (which are 2,3 and 167) and phi(m) = m -1.<br />
<br />
Combining all these equations, we can easily solve the problem.<br />
<br />
Source code below -<br />
<br />
<pre class="prettyprint">/*
Problem Name : MMOD29
Problem Number : SPOJ 3909
Link : http://www.spoj.pl/problems/MMOD29/en/
Problem Type : Math
Difficulty : 4.5 / 10
Interest : 6 / 10
Complexity : O(lgX)
Date : December 2, 2010
*/
#include <stdio.h>
#define rep(i,n) for(i=0;i<(n);i++)
int bigmod(int b, int p, int m) {
if(p == 0) return 1;
if(p == 1) return b%m;
if(p&1) return ((b%m) * bigmod(b,p-1,m)) % m;
else {
int sq = bigmod(b,p/2,m);
return (sq * sq) % m;
}
}
int main() {
int n,res,i,x;
int primes[] = {2,3,167};
int powers[] = {2,1,1};
int MOD = 29;
while(scanf(" %d",&n) == 1) {
if(n == 0) break;
res = 1;
rep(i,3) {
x = (bigmod(primes[i],powers[i]*n+1,MOD) - 1 + MOD) % MOD;
res = (res * x) % MOD;
x = bigmod(primes[i]-1,MOD-2,MOD);
res = (res * x) % MOD;
}
printf("%d\n",res);
}
return 0;
}</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com0tag:blogger.com,1999:blog-8676956288282165818.post-86437508664944255832010-12-01T05:30:00.002+06:002012-02-19T17:01:26.301+06:00TopCoder SRM 489 Div 1 Medium (Dice Rotation)Another bad SRM for me :( I couldn't even submit any problem although I was just 1 click away from solving the medium problem with 30 seconds to go when the network router decided to go offline. My only achievement in this SRM was one successful challenge.<br />
<br />
I'm going to explain how I approached the <a href="http://www.topcoder.com/stat?c=problem_statement&pm=11212">dice rotation problem</a>. In this problem you have to move a standard dice placed at <b>(0,0)</b> cell of an infinite Cartesian plane to <b>(goalx, goaly)</b> by rotating it to right or up. The top of the dice have to show '<b>1</b>' when it starts its journey at <b>(0,0)</b> and also when it ends its journey at <b>(goalx,goaly)</b> and it cannot be on top in any intermediate cell. <b>goalx</b> and <b>goaly</b> can be as high as <b>10^9</b>.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiR6Bvvf8WlT_BnANAMmz-FoOSAzz9CLN5QPpLY8Shc2_F6jvIhhuxLP9fV6pStpQt0y6Y7oArsQYclv25g6YUOBcoRUMoyovcLAocmilVIwOVJkBHpGaSYH5ikN9xrmIt36FzUgI4Ft20/s1600/DiceRotation2.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="156" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiR6Bvvf8WlT_BnANAMmz-FoOSAzz9CLN5QPpLY8Shc2_F6jvIhhuxLP9fV6pStpQt0y6Y7oArsQYclv25g6YUOBcoRUMoyovcLAocmilVIwOVJkBHpGaSYH5ikN9xrmIt36FzUgI4Ft20/s400/DiceRotation2.gif" width="500" /></a></div><br />
<a name='more'></a><br />
<br />
Firstly I observed that all the given sample inputs have output 2 and samples seemed pretty random too. So, there might not be too many ways it can reach the destination cell. It is clear if you move the dice to any direction 4 times consecutively '<b>1</b>' will appear on the top surface again. To move the dice a long distance in any direction, you have place the '<b>1</b>' face out of rotating axis. For example, when going up (moving in y-direction), you have to place the '<b>1</b>' face in right or left. When moving right again, you have to first move it to bottom (by going right) and then to front (by going up) and then you can continuously move to right until you reach one cell below your destination.<br />
<br />
So, I decided to write a solution for smaller cases to check if there's any pattern in it. It can be done using dynamic programming. We have to find number of ways we can reach a cell <b>(x,y)</b> with face <b>z</b> on top. After writing that brute force solution, its easy to find that the solution is always 2 unless one of the <b>goalx</b> or <b>goaly</b> is 4. In that case, it would be <b>3 plus the other number</b>. One special case is <b>(4,4)</b> for which input should be <b>12</b>. And also, if one of <b>goalx</b> or <b>goaly</b> is <b>1</b>, the answer will be <b>0</b> unless the other is <b>4</b>.<br />
<br />
<b><u>After match analysis:</u></b><br />
<br />
We can always reach the destination in <b>2</b> standard paths which are shown below -<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgHVxzORc96Xc5X3w32pCOv_rpqlUNV54zmSj6HvMty6h4lZglOqwrv3nihHXeBXhXsX0tkn1g-EBTSXLXm5mp3zDUbpAAR2jSGKjn_5aN3dkgUdUjEZdw5KfeftAACe2VWZXhP2GPIANQ/s1600/dice+path.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="274" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgHVxzORc96Xc5X3w32pCOv_rpqlUNV54zmSj6HvMty6h4lZglOqwrv3nihHXeBXhXsX0tkn1g-EBTSXLXm5mp3zDUbpAAR2jSGKjn_5aN3dkgUdUjEZdw5KfeftAACe2VWZXhP2GPIANQ/s320/dice+path.jpg" width="320" /></a></div><br />
The speciality with <b>4</b> is because of the fact that if we rotate dice in one direction 4 times, it will reach the original state. For example, lets say <b>goalx</b> = <b>4</b> and <b>goaly</b> = <b>6</b>. Starting with <b>(0,0)</b> we can take any of the following path -<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi8mD_zDNg6qhYDdNvhCbOIm5aZ_m1HVNt80hZxxaAsevf2_Y9f2RGu1hHmUPdFf4zCcml6mrKaAsX3VdLVye-4QE9iVB66LXKHBtbozipCdCan0stCKxz2SCBgQtsx1nu49_jYml7I3aA/s1600/dice+path+with+4.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi8mD_zDNg6qhYDdNvhCbOIm5aZ_m1HVNt80hZxxaAsevf2_Y9f2RGu1hHmUPdFf4zCcml6mrKaAsX3VdLVye-4QE9iVB66LXKHBtbozipCdCan0stCKxz2SCBgQtsx1nu49_jYml7I3aA/s320/dice+path+with+4.jpg" width="228" /></a></div><br />
There are <b>7</b> ways to reach <b>(4,6)</b>. Plus there will be <b>2</b> standard paths. So, the proper formulation of the solution would be<br />
<blockquote><b>npaths</b> = <b>2</b> + (<b>goalx</b>==<b>4</b>)?(<b>goaly+1</b>):<b>0</b> + (<b>goaly</b>==<b>4</b>)?(<b>goalx+1</b>):<b>0</b></blockquote><br />
Source code below -<br />
<br />
<pre class="prettyprint">/*
Problem Name : Dice Rotation
Problem Number : Topcoder SRM 489 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=11212
Problem Type : Math, Dynamic Programming
Difficulty : 6.5 / 10
Interest : 8.5 / 10
Complexity : O(1)
Date : December 1, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define rep(i,n) for(i=0;i<(n);i++)
int dp[50][50][6];
int final[50][50];
struct DiceRotation{
int rotate(int cur, int dir) {
if(dir == 0) { //right
if(cur == 0) return 4;
if(cur == 4) return 5;
if(cur == 5) return 1;
if(cur == 1) return 0;
return cur;
}
if(dir == 1) { //up
if(cur == 0) return 2;
if(cur == 2) return 5;
if(cur == 5) return 3;
if(cur == 3) return 0;
return cur;
}
}
void init() {
int i,j,k,x,y;
int r1,r2;
for(x=1;x<=40;x++) for(y=1;y<=40;y++) {
memset(dp,0,sizeof(dp));
dp[0][0][0] = 1;
rep(i,x+1) rep(j,y+1) rep(k,6) if(dp[i][j][k] > 0){
r1 = rotate(k,0);
r2 = rotate(k,1);
if(r1 == 0) {
if(i+1 == x && j == y) dp[i+1][j][r1] += dp[i][j][k];
}
else dp[i+1][j][r1] += dp[i][j][k];
if(r2 == 0) {
if(i == x && j+1 == y) dp[i][j+1][r2] += dp[i][j][k];
}
else dp[i][j+1][r2] += dp[i][j][k];
}
final[x][y] = dp[x][y][0];
printf("%d %d => %d\n",x,y,dp[x][y][0]);
}
}
int theCount(int goalx, int goaly) {
//init();
if(goaly < goalx) swap(goalx,goaly);
if(goalx == 1) {
if(goaly == 4) return 2;
return 0;
}
if(goalx == 4 && goaly == 4) return 12;
if(goalx == 4 || goaly == 4) return goalx+goaly-1;
return 2;
}
};</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com5tag:blogger.com,1999:blog-8676956288282165818.post-4589654120930387252010-11-30T23:59:00.003+06:002012-02-19T16:35:31.174+06:00SWERC 2010: Assembly Line [Solved]This is the <a href="http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4961">problem</a> I was getting Time Limit Exceeded as mentioned in the <a href="http://one-problem-a-day.blogspot.com/2010/11/unsolved-jumping-monkey-assembly-line.html">post</a>. Thanks to <a href="http://www.topcoder.com/tc?module=MemberProfile&cr=22637798">emotionalBlind</a> and <a href="http://problem-solving-notes.blogspot.com/">moshiur</a> for sharing their approaches. Previously I was trying to do a top down DP of finding optimal result within a start and end index which produces a certain character output. Now, I've switched my approach to bottom up. I am still storing results for the state [start index, end index, character i want to make]. But I'm also saving the characters I can make in a range of start and end index into a vector. So, when we split at different positions, instead of trying all characters, we only have to try the characters that we can make on the sub-range.<br />
<br />
<a name='more'></a><br />
<br />
Source code below -<br />
<pre class="prettyprint">/*
Problem Name : Assembly Line
Problem Number : Live Archive 4961
Link : http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4961
Problem Type : Dynamic Programming
Difficulty : 6 / 10
Interest : 6 / 10
Complexity : O((NK)^3)
Date : November 30, 2010
*/
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cassert>
using namespace std;
#define INF 302345678
#define min(a,b) (((a) < (b)) ? (a) : (b))
#define rep(i,n) for(i=0;i<(n);i++)
vector<string> parse(const string& s,const string& delim=" ") {
vector<string>res;
string t;
for(int i=0;i!=s.size();i++) {
if(delim.find(s[i]) != string::npos) {
if(!t.empty()) {
res.push_back(t);
t="";
}
}
else t+=s[i];
}
if(!t.empty()) res.push_back(t);
return res;
}
#define MAXK 26
#define MAXN 200
int n; //input character ordering sequence length
char ch[MAXK+3]; //input character ordering sequence
int pos[200]; //position of a lower case letter in the input sequence..like pos['e'] = 1 in the 2nd sample
char tran[MAXK+3][MAXK+3]; //character part of input matrix
int cost[MAXK+3][MAXK+3]; //number part of input matrix
int dp[MAXN+2][MAXN+2][MAXK+2]; //dp table
char s[MAXN+5]; //query string
int L; //query string length
//vector< char > result[MAXN+2][MAXN+2];
char result[MAXN+2][MAXN+2][MAXK+2];
int counter[MAXN+2][MAXN+2];
void process() {
int i,j,k,x,y;
char a,b,c;
int cst;
rep(i,L) rep(j,L) counter[i][j] = 0;
rep(i,L) {
dp[i][i][s[i]-'a'] = 0;
result[i][i][counter[i][i]++] = s[i];
}
for(i=2;i<=L;i++) {
rep(j,L-i+1) {
for(k=j;k<j+i-1;k++) {
rep(x,counter[j][k]) rep(y,counter[k+1][j+i-1]) {
a = result[j][k][x];
b = result[k+1][j+i-1][y];
c = tran[pos[a]][pos[b]];
cst = cost[pos[a]][pos[b]] + dp[j][k][a-'a'] + dp[k+1][j+i-1][b-'a'];
if(dp[j][j+i-1][c-'a'] == -1 || cst < dp[j][j+i-1][c-'a']) {
dp[j][j+i-1][c-'a'] = cst;
}
}
}
rep(k,n) if(dp[j][j+i-1][ch[k]-'a'] != -1) result[j][j+i-1][counter[j][j+i-1]++] = ch[k];
}
}
}
int main()
{
vector<string> t;
int i,j,k;
string res;
int q;
int cur, ret;
bool f = 0;
char temp[100];
while(scanf("%d",&n)==1) {
if(n == 0) break;
if(!f) f = 1;
else printf("\n");
//input processing
rep(i,n) { scanf(" %c",&ch[i]); pos[ch[i]] = i; }
rep(i,n) rep(j,n) {
scanf(" %s",s);
t = parse(s,"-");
cost[i][j] = atoi(t[0].c_str());
tran[i][j] = t[1][0];
}
//queries
scanf(" %d",&q);
rep(i,q) {
scanf(" %s",s);
L = strlen(s);
memset(dp,-1,sizeof(dp));
process();
res = "";
ret = INF;
rep(j,n) {
cur = dp[0][L-1][ch[j]-'a'];
if(cur != -1 && cur < ret) {
ret = cur;
sprintf(temp,"%d",ret);
res = temp;
res += "-";
res += ch[j];
}
}
assert(ret < INF);
printf("%s\n",res.c_str());
}
}
return 0;
}</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com0tag:blogger.com,1999:blog-8676956288282165818.post-37447423175826110282010-11-29T04:48:00.002+06:002012-02-19T16:35:43.284+06:00SWERC 2010: Jumping Monkey [Solved]As you can find on my <a href="http://one-problem-a-day.blogspot.com/2010/11/unsolved-jumping-monkey-assembly-line.html">previous post</a>, I was getting wrong answer on this <a href="http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4959">problem</a>. Thanks to <a href="http://www.blogger.com/profile/15549795308934226672">BearedCrazyCoder</a> aka <a href="http://www.topcoder.com/tc?module=MemberProfile&cr=11809435">Sidky</a> for pointing out the mistake in my approach. I was using dynamic programming and moving from one state to the other recursively. You can read <a href="http://one-problem-a-day.blogspot.com/2010/11/unsolved-jumping-monkey-assembly-line.html?showComment=1290955770385#c7015749024611994712">this</a> comment for understanding the flaw -<br />
<br />
<a name='more'></a><br />
<blockquote><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;">btw, I don't think you can solve this in this approach, because, in this approach, the nodes will be discovered in depth-first order.</span><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;"><br />
</span><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;">Let's say, the nodes are discovered in this order:</span><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;"><br />
</span><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;">v1 v2 v3 v4 v5 v6 v7 ... vp .. vq</span><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;"><br />
</span><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;">Let's say, vq has only one next state, vp.</span><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;"><br />
</span><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;">So, dp[vp] = INF</span><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;"><br />
</span><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;">Now, let's assume, it is possible to reach vp in a shorter path:</span><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;"><br />
</span><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;">v1 v2' v3' ... vq</span><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;"><br />
</span><span class="Apple-style-span" style="color: #666666; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 13px; line-height: 18px;">now, it can visit vp, but since dp[vq] has already been calculated as INF, it will not proceed any further. So, this may lead to a suboptimal solution (or probably no solution)</span></blockquote>So I resorted to good old <a href="http://en.wikipedia.org/wiki/Breadth-first_search">Breadth First Search</a> and my program got accepted in 4.678 seconds which was worst among others. I tried to optimize it in all possible ways (except for IO optimization). The run times and tweaks in my next submissions were -<br />
<br />
<table border="1" style="border:solid"><tr><th>Runtime</th><th>Optimizations</th></tr>
<tr><td>4.100</td><td>Stopped shooting at positions where there is no monkey</td></tr>
<tr><td>1.570</td><td>Converted the vector to simple array</td></tr>
<tr><td>0.709</td><td>Converted all the data types to the most efficient possible [integers to chars for index variables, result array etc.]</td></tr>
<tr><td>0.693</td><td>Converting the most used variables to register</td></tr>
<tr><td>0.723</td><td>At this stage I tried to pre-compute for each integer the positions where it has a '1' bit and store those positions in an array. This really backfired in spite of reduction in loop instructions as array indexing was increased</td></tr>
<tr><td>0.281</td><td>Here, I've observed that I can remove one inner loop. Instead of shooting one tree at a time, I can shoot all the tree at once and later remove the effect of an particular tree to get the state for that tree</td></tr>
</table><br />
<b>One important note, I've found that even on a tree (the graph is tree), it is sometimes not possible to kill the monkey. I can't think such a case. Can you find any?</b><br />
<br />
Here's my final source code - <br />
<br />
<pre class="prettyprint">/*
Problem Name : Jumping Monkey
Problem Number : Live Archive 4959
Link : http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4959
Problem Type : BFS, Optimization
Difficulty : 7 / 10
Interest : 8 / 10
Complexity : O(N*2^N)
Date : November 29, 2010
*/
#include<vector>
#include<cstdio>
#include<cassert>
using namespace std;
#define MAXN 21
#define INF 10234567
#define min(a,b) (((a) < (b)) ? (a) : (b))
#define rep(i,n) for(i=0;i<(n);i++)
char d[(1<<MAXN)]; //distance array...final output
int pre[(1<<MAXN)];
char shoot[(1<<MAXN)];
char n;
int m;
int Q[(1<<MAXN)];
char adj[MAXN+2][MAXN+2];//adjacency list in array form
char ct[MAXN+2]; // counter for adjacency list
//4.678 -> 4.100 -> 1.570 -> .709-> .693 -> .723 -> 0.281
char counter[MAXN+2];
int bfs() {
register int sz = 0, cur = 0;
register char i,j;
register int st, nstate, cur_state;
Q[sz++] = (1<<n) - 1;
memset(d,-1,sizeof(d));
d[(1<<n)-1] = 0;
while(cur < sz) {
st = Q[cur++];
memset(counter,0,sizeof(counter));
cur_state = 0;
rep(i,n) if(st & (1<<i)) {
rep(j,ct[i]) {
counter[adj[i][j]]++;
cur_state |= (1<<adj[i][j]);
}
}
rep(i,n) if(st & (1<<i)) {
nstate = cur_state;
rep(j,ct[i]) {
if(counter[adj[i][j]]-1<=0) nstate &= ~(1<<adj[i][j]);
}
if(d[nstate] == -1) {
d[nstate] = d[st] + 1;
Q[sz++] = nstate;
pre[nstate] = st;
shoot[nstate] = i;
if(nstate == 0) return d[nstate];
}
}
}
return INF;
}
void print(int st) {
if(st == (1<<n)-1) return;
print(pre[st]);
printf(" %d",shoot[st]);
}
int main()
{
int i;
int a,b;
int ret;
while(scanf(" %d %d",&n,&m)==2) {
if(n == 0 && m == 0) break;
memset(adj,0,sizeof(adj));
rep(i,n) ct[i] = 0;
rep(i,m) {
scanf(" %d %d",&a,&b);
adj[a][ct[a]++] = b;
adj[b][ct[b]++] = a;
}
if(m != n-1) { printf("Impossible\n"); continue; }
ret = bfs();
if(ret == INF) { printf("Impossible\n"); continue; }
printf("%d:",ret);
print(0); printf("\n");
}
return 0;
}
</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com1tag:blogger.com,1999:blog-8676956288282165818.post-52012515710345923972010-11-28T15:46:00.001+06:002012-02-19T16:36:00.708+06:00Unsolved: Jumping Monkey & Assembly Line from SWERCToday there will be no solution for solved problem, rather I would post my approach, code and test data for 2 unsolved problems in recent <a href="http://acm.uva.es/archive/nuevoportal/region.php?r=sw&year=2010">SWERC</a> contest and you are invited find flaws in my solution.<br />
<br />
<b><a href="http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4959">Jumping Monkey</a></b><br />
<br />
This is an interesting problem. I've used bitmask DP to solve it. Each state represents the possible locations of the monkey. Now if we shoot a particular tree, if there was a monkey in the tree, it will die and cannot move to neighboring tress. If the monkey was in any other tree, it will move to any of its adjacent trees (including the one we've just shot).<br />
<br />
<a name='more'></a><br />
<br />
Another thing to note is that if the input graph is not a tree, then it will not be possible to kill the monkey as it can always move in a cycle.<br />
<br />
I'm getting wrong answer in this problem. Here's my code -<br />
<br />
<pre class="prettyprint">#include<vector>
#include<cstdio>
#include<cassert>
using namespace std;
#define MAXN 21
#define INF 10234567
#define min(a,b) (((a) < (b)) ? (a) : (b))
#define rep(i,n) for(i=0;i<(n);i++)
vector<int> adj[MAXN+2];
int dp[(1<<MAXN)+5];
int pre[(1<<MAXN)+5];
int shoot[(1<<MAXN)+5];
int n,m;
int go(int st) {
if(dp[st] != -1) return dp[st];
if(st == 0) return dp[st] = 0;
int &ret = dp[st];
ret = INF;
int i,j,k,cur;
int nstate;
rep(i,n) {
nstate = 0;
rep(j,n) if(j !=i && (st & (1<<j))) {
rep(k,adj[j].size()) nstate |= (1<<adj[j][k]);
}
cur = go(nstate) + 1;
if(cur < ret) {
ret = cur;
shoot[st] = i;
pre[st] = nstate;
}
}
return ret;
}
void print(int st) {
if(st == 0) return;
printf(" %d",shoot[st]);
print(pre[st]);
}
int main()
{
int i;
int a,b;
int ret;
while(scanf(" %d %d",&n,&m)==2) {
if(n == 0 && m == 0) break;
assert(n>=1 && n<=21);
memset(adj,0,sizeof(adj));
rep(i,n) adj[i].clear();
rep(i,m) {
scanf(" %d %d",&a,&b);
assert(a>=0 && a<n && b>=0 && b<n && a!=b);
adj[a].push_back(b);
adj[b].push_back(a);
}
if(m != n-1) { printf("Impossible\n"); continue; }
memset(dp,-1,sizeof(dp));
memset(pre,-1,sizeof(pre));
memset(shoot,-1,sizeof(shoot));
ret = go((1<<n)-1);
if(ret == INF) { printf("Impossible\n"); continue; }
assert(ret < INF);
printf("%d:",ret);
print((1<<n)-1); printf("\n");
}
return 0;
}
</pre><br />
Here's the input I've tested on -<br />
<br />
<pre class="prettyprint">17 16
0 2
0 3
2 1
2 5
2 6
3 7
3 4
3 8
5 9
6 10
6 11
6 12
10 14
10 15
11 16
8 13
2 1
0 1
3 3
0 1
1 2
2 0
4 3
0 1
2 3
1 3
1 0
8 7
7 0
0 1
1 2
1 3
3 4
3 5
3 6
8 7
0 1
1 2
2 3
3 4
4 5
5 6
6 7
21 20
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
11 10
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
12 11
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
0 0</pre><br />
And here's the output -<br />
<br />
<pre class="prettyprint">20: 8 3 0 2 5 2 6 10 6 11 10 6 11 6 2 5 2 0 3 8
2: 0 0
Impossible
4: 1 3 3 1
1: 0
6: 0 1 3 0 1 3
12: 1 2 3 4 5 6 6 5 4 3 2 1
38: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
18: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
20: 1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1</pre><br />
<b><a href="http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4961">Assembly Line</a></b><br />
<br />
This is a dynamic programming problem. The states are [start index, end index, character I want to make]. To calculate the result of each state, I've split the sequence in different positions and tried to make different characters in the two portions and then combined them to check whether it is possible for the 2 characters from each portion to make the character I want and if possible whether it is optimal in cost.<br />
<br />
I'm getting Time Limit Exceeded in this problem. Here's my source -<br />
<br />
<pre class="prettyprint">#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cassert>
using namespace std;
#define INF 302345678
#define min(a,b) (((a) < (b)) ? (a) : (b))
#define rep(i,n) for(i=0;i<(n);i++)
vector<string> parse(const string& s,const string& delim=" ") {
vector<string>res;
string t;
for(int i=0;i!=s.size();i++) {
if(delim.find(s[i]) != string::npos) {
if(!t.empty()) {
res.push_back(t);
t="";
}
}
else t+=s[i];
}
if(!t.empty()) res.push_back(t);
return res;
}
#define MAXK 26
#define MAXN 200
int n; //input character ordering sequence length
char ch[MAXK+3]; //input character ordering sequence
int pos[200]; //position of a lower case letter in the input sequence..like pos['e'] = 1 in the 2nd sample
char tran[MAXK+3][MAXK+3]; //character part of input matrix
int cost[MAXK+3][MAXK+3]; //number part of input matrix
int dp[MAXN+2][MAXN+2][MAXK+2]; //dp table
char s[MAXN+5]; //query string
int L; //query string length
vector< pair<int,int> > from[MAXK+2]; //pairs that produces a particular character
int go(int st, int en, char final) {
if(st > en) return INF;
if(dp[st][en][final-'a'] != -1) return dp[st][en][final-'a'];
if(st == en) {
if(s[st] == final) return dp[st][en][final-'a'] = 0;
return dp[st][en][final-'a'] = INF;
}
if(st+1 == en) { //actually don't need to include it as base condition...but just as an optimization
if(tran[pos[s[st]]][pos[s[en]]] == final) {
return dp[st][en][final-'a'] = cost[pos[s[st]]][pos[s[en]]];
}
else return dp[st][en][final-'a'] = INF;
}
int &ret = dp[st][en][final-'a'];
ret = INF;
int i,j;//,k;
int r1,r2;
int p = pos[final];
for(j = st; j < en; j++) {
rep(i,from[p].size()) {
r1 = go(st,j,ch[from[p][i].first]);
if(r1 == INF) continue;
r2 = go(j+1,en,ch[from[p][i].second]);
ret = min(ret, r1 + r2 + cost[from[p][i].first][from[p][i].second]);
}
/*
rep(i,n) {
rep(k,n) if(tran[i][k] == final) {
r1 = go(st,j,ch[i]);
if(r1 == INF) continue;
r2 = go(j+1,en,ch[k]);
ret = min(ret, r1 + r2 + cost[i][k]);
}
}*/
}
return ret;
}
int main()
{
vector<string> t;
int i,j;
string res;
int q;
int cur, ret;
bool f = 0;
char temp[100];
while(scanf("%d",&n)==1) {
if(n == 0) break;
if(!f) f = 1;
else printf("\n");
//input processing
rep(i,n) { scanf(" %c",&ch[i]); pos[ch[i]] = i; from[i].clear(); }
rep(i,n) rep(j,n) {
scanf(" %s",s);
t = parse(s,"-");
cost[i][j] = atoi(t[0].c_str());
tran[i][j] = t[1][0];
from[pos[t[1][0]]].push_back( make_pair(i,j) );
}
//queries
scanf(" %d",&q);
rep(i,q) {
scanf(" %s",s);
L = strlen(s);
memset(dp,-1,sizeof(dp));
res = "";
ret = INF;
rep(j,n) {
cur = go(0,L-1,ch[j]);
if(cur < ret) {
ret = cur;
sprintf(temp,"%d",ret);
res = temp;
res += "-";
res += ch[j];
}
}
assert(ret < INF);
printf("%s\n",res.c_str());
}
}
return 0;
}</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com10tag:blogger.com,1999:blog-8676956288282165818.post-12530048016883045312010-11-27T01:52:00.003+06:002012-02-19T17:01:45.300+06:00TopCoder SRM 473 Div 1 Medium (RightTriangle)Problem Link : <a href="http://www.topcoder.com/stat?c=problem_statement&pm=10976">http://www.topcoder.com/stat?c=problem_statement&pm=10976</a><br />
<br />
In this problem, <br />
<blockquote>given some points on the perimeter of a circle that were selected from a poll of equidistant points, we have to calculate how many different right triangles we can make from those points. points are placed using a generator program. If a position is filled up by a previous point, it will be placed on the next available position.</blockquote>Now this problem has 2 parts -<br />
<br />
<a name='more'></a><br />
<br />
<ol><li>Finding an efficient algorithm to calculate the final position of the generated points.</li>
<li>For a set of points determining how many right triangles are there.</li>
</ol><div>For part 1, I've used a Binary Indexed Tree (BIT) or Fenwick Tree to find final position of each point. For each point, if the position is filled up I've used a binary search to find the first position after that (note that positions wraps around) which is not filled. It was possible to remove the binary search and directly finding on the tree. But the implementation would be tricky.</div><div><br />
</div><div>There can be many other approaches for part 1. Check the official <a href="http://www.topcoder.com/wiki/display/tc/SRM+473">match editorial</a> for alternative methods. Specially check the O(N) algorithm.</div><div><br />
</div><div>For part 2, we know from <a href="http://en.wikipedia.org/wiki/Thales'_theorem">Thales' Theorem</a> that - </div><blockquote><span class="Apple-style-span" style="line-height: 19px;"><span class="Apple-style-span" style="font-family: inherit;">If A, B and C are points on a circle where the line AC is a diameter of the circle, then the angle ABC is a right angle.</span></span></blockquote>It can be easily proved using <a href="http://en.wikipedia.org/wiki/Inscribed_angle_theorem">Inscribed Angle Theorem</a> that the reverse of Thales' Theorem (that is for an inscribed angle on a circle to be right, the two other points have to form a diameter) is also true.<br />
<br />
So, for each point, we just need to check if there is an opposite point 180 degrees apart. If we find one such pair, we can make right triangles using all the remaining points.<br />
<br />
Source code below -<br />
<br />
<pre class="prettyprint">/*
Problem Name : RightTriangle
Problem Number : TopCoder SRM 473 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=10976
Problem Type : Geometry, Data Structure, Search
Difficulty : 6 / 10
Interest : 8 / 10
Complexity : O(N(lgP)^2)
Date : November 27, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cassert>
using namespace std;
#define rep(i,n) for(i=0;i<(n);i++)
#define MAXV 1000000
int tree[MAXV+2];
bool flag[MAXV+2];
struct RightTriangle{
int places;
void update(int dex, int val) {
while(dex <= MAXV) {
tree[dex] += val;
if(dex == 0) break;
dex += (dex & -dex);
}
}
int read(int dex) {
int sum = 0;
while(dex > 0) {
sum += tree[dex];
dex -= (dex & -dex);
}
return sum;
}
int find_position(int x) {
x++;
//search up
int base = read(x);
int lo = x+1, hi = places, mid;
int cur = read(hi);
if(cur - base == hi - x) { //all filled up above..so search from below
lo = 1;
hi = x - 1;
base = 0;
x = 0;
}
while(hi-lo>=3) {
mid = (lo + hi) >> 1;
cur = read(mid);
if(cur - base < mid - x) hi = mid;
else lo = mid + 1;
}
for(int i = lo; i <= hi; i++) {
cur = read(i);
if(cur - base < i - x) return i;
}
assert(0);
}
long long triangleCount(int places, int points, int a, int b, int c) {
if(places & 1) return 0;
long long i;
int x;
int pos;
this->places = places;
memset(tree,0,sizeof(tree));
memset(flag,0,sizeof(flag));
rep(i,points) {
x = (a * i * i + b * i + c) % places;
if(flag[x]) pos = find_position(x); else pos = x+1;
update(pos, 1);
flag[pos-1] = 1;
}
long long res = 0;
int half = places / 2;
rep(i,half) if(flag[i] && flag[i+half]) res += (points-2);
return res;
}
};</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com0tag:blogger.com,1999:blog-8676956288282165818.post-47160754343902572010-11-26T05:53:00.002+06:002012-02-19T17:02:01.810+06:00TopCoder SRM 447 Div 1 Medium (PeopleYouMayKnow)Problem link : <a href="http://www.topcoder.com/stat?c=problem_statement&pm=10580">http://www.topcoder.com/stat?c=problem_statement&pm=10580</a><br />
<br />
This is a nice problem because it can be solved in different ways - dynamic programming, maximum flow or bipartite matching.<br />
<br />
The solution of the problem in one line would be<br />
<blockquote>calculate maximum number of node disjoint paths from node p1 to p2 whose length is less than or equal to 3.</blockquote><br />
<a name='more'></a><br />
<br />
Finding maximum number of node disjoint paths in a graph is a <a href="http://en.wikipedia.org/wiki/Maximum_flow_problem">Maximum Flow</a> problem. And to check if the length of the path is within range or not, we have to assign unit costs to each edge and use Bellman Ford algorithm when finding augmenting path. Also, note that for finding node disjoint paths, you have to split each node in 2 to incorporate node capacity constraint. For more info, check the Wikipedia <a href="http://en.wikipedia.org/wiki/Maximum_flow_problem#Maximum_flow_problem_with_vertex_capacities">page</a>.<br />
<br />
This was the general solution. But as the length of the path is at most 3, we can improvise on it. There can be 2 types of cases -<br />
<br />
<ol><li>The length of the path is 2 i.e. there is just one node between p1 and p2. In this case, we have to remove the node.</li>
<li>The length of the path is 3 and none of the intermediate node satisfies the previous case. In this case, we need to remove at least one of the nodes.</li>
</ol><div>Case 1 can be solved easily - by just checking the adjacency matrix. To solve the Case 2s, we need to create a bipartite graph with nodes connected with p1 on one side and nodes connected with p2 on the other and find maximum matching in it. As the number of nodes is at most 40, one of the bipartite set will contain less than 20 nodes. So, we can just implement a bitmask dp here. Find more information about this approach on the official match <a href="http://www.topcoder.com/wiki/display/tc/SRM+447">editorial</a>.</div><div><br />
</div><div>Bipartite matching is easier to code amongst all the approaches. Check my source code below. Note the case one the input graph is disconnected.</div><div><pre class="prettyprint">/*
Problem Name : PeopleYouMayKnow
Problem Number : TopCoder SRM 447 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=10580
Problem Type : Dynamic Programming, Bipartite Matching
Difficulty : 6.5 / 10
Interest : 7.5 / 10
Complexity : O(N^3)
Date : November 26, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
using namespace std;
#define rep(i,n) for(i=0;i<(n);i++)
#define MAXN 40
bool a1[MAXN+2][MAXN+2], a2[MAXN+2][MAXN+2];
bool graph[MAXN+2][MAXN+2];
bool visited[MAXN+2];
bool flag[MAXN+2];
int matchL[MAXN+2];
int matchR[MAXN+2];
struct PeopleYouMayKnow{
int n;
bool bpm(int u) {
int i;
rep(i,n) if(graph[u][i] && visited[i] == false) {
visited[i] = true;
if(matchR[i] < 0 || bpm(matchR[i])) {
matchL[u] = i;
matchR[i] = u;
return true;
}
}
return false;
}
int maximalScore(vector <string> friends, int p1, int p2) {
int i,j,k;
n = friends.size();
rep(i,n) rep(j,n) a1[i][j] = a2[i][j] = (friends[i][j] == 'Y');
rep(k,n) rep(i,n) rep(j,n) a2[i][j] |= (a2[i][k] & a2[k][j]); //floyd warshall
if(!a2[p1][p2]) return 0; //not connected
int res = 0;
memset(graph,0,sizeof(graph));
memset(flag,0,sizeof(flag));
flag[p1] = flag[p2] = 1;
rep(i,n) if(a1[p1][i] && a1[i][p2]) { flag[i] = 1; res++; } //connected by 1 intermediate friend
//build graph
rep(i,n) if(!flag[i]) {
rep(j,n) if(!flag[j]) {
if(a1[p1][i] && a1[i][j] && a1[j][p2]) {
graph[i][j] = 1;
}
}
}
//bpm
memset(matchL,-1,sizeof(matchL));
memset(matchR,-1,sizeof(matchR));
rep(i,n) if(!flag[i]) {
memset(visited,0,sizeof(visited));
if(bpm(i)) res++;
}
return res;
}
};
</pre></div>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com0tag:blogger.com,1999:blog-8676956288282165818.post-6509916629444675882010-11-25T03:16:00.002+06:002012-02-19T17:02:51.080+06:00TopCoder SRM 477 Div 1 Medium (PythTriplets)Problem Link : <a href="http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157">http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157</a><br />
<br />
In this problem, given some integers (at most <b>200</b>) in the range <b>[1, 999999]</b> you have to find maximum number of <b>disjoint</b> pairs <b>(a,b)</b> such that <b>a^2 + b^2 = c^2</b> for some integer <b>c</b> and <b>a</b> & <b>b</b> are <b>co-prime</b>.<br />
<br />
Now this is a classic example of a <a href="http://en.wikipedia.org/wiki/Matching_(graph_theory)">bipartite matching</a> problem although it may not be evident how to split the numbers in two bipartite sets. Lets consider the different cases possible according to the <b>parity</b> of the numbers in a pair -<br />
<a name='more'></a><br />
<ol><li>Both of them are <b>even</b>: This cannot be a valid pair because numbers in a pair have to be co-prime.</li>
<li>One is <b>even</b>, the other is <b>odd</b>: This is valid. Examples: 3^2 + 4^2 = 5^2, 12^2 + 5^2 = 13^2.</li>
<li>Both of them are <b>odd</b>: This also is not a valid pair. Proof below -</li>
</ol><div>Let <b>a = 2n + 1</b> and <b>b = 2m + 1</b></div><div>So, <b>x = a^2 + b^2 = (2n+1)^2 + (2m+1)^2 = 4(n^2+m^2) + 4(n+m) + 2 = 2 [ 2(n^2+m^2) + 2(n+m) + 1 ]</b></div><div>Now as the first 2 terms inside the square bracket are even numbers, 3 terms combined makes an odd number. So, <b>x = 2y</b> where <b>y</b> is an <b>odd</b> number. As such it is not possible for <b>x</b> to be a <b>square number</b>.</div><div><br />
</div><div>So, it is clear that we can split the numbers in 2 bipartite sets according to their parity. After that all you have to do is implement a bipartite matching algorithm. The code I've written here is inspired by <a href="http://shygypsy.com/tools/">Igor Naverniouk</a> aka Abednego.</div><div><br />
</div><div>Note that instead of splitting the numbers according to their parity, we could have just matched one copy of the whole set to the original set and then divide the number of matchings by two to get the actual answer.</div><div><br />
</div><div>Source code below - </div><br />
<pre class="prettyprint">/*
Problem Name : PythTriplets
Problem Number : TopCoder SRM 477 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157
Problem Type : Bipartite Matching
Difficulty : 5.5 / 10
Interest : 7 / 10
Complexity : O(N^3)
Date : November 25, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
#define rep(i,n) for(i=0;i<(n);i++)
#define MAXN 200
bool adj[MAXN+2][MAXN+2];
bool flag[MAXN+2];
int matchL[MAXN+2];
int matchR[MAXN+2];
vector<int> odd, even;
int n,m;
struct PythTriplets{
vector<string> parse(const string& s,const string& delim=" ") {
vector<string>res;
string t;
for(int i=0;i!=s.size();i++) {
if(delim.find(s[i]) != string::npos) {
if(!t.empty()) {
res.push_back(t);
t="";
}
}
else t+=s[i];
}
if(!t.empty()) res.push_back(t);
return res;
}
bool bpm(int u) {
int i;
rep(i,m) if(adj[u][i]) {
if(flag[i]) continue;
flag[i] = true;
if(matchR[i] < 0 || bpm(matchR[i]) ) {
matchL[u] = i;
matchR[i] = u;
return true;
}
}
return false;
}
int gcd(int a, int b) {
if(b == 0) return a;
return gcd(b, a%b);
}
bool ok(long long a, long long b) {
if(gcd(a,b) != 1) return false;
long long c = a * a + b * b;
long long s = sqrt((long double)c);
if(s * s == c) return true;
return false;
}
int findMax(vector <string> stick) {
int i,j,x;
string s;
//parse input
rep(i,stick.size()) s += stick[i];
vector<string> vs = parse(s);
odd.clear(); even.clear();
rep(i,vs.size()) {
x = atoi(vs[i].c_str());
if(x&1) odd.push_back(x);
else even.push_back(x);
}
//create adjacency matrix
n = odd.size();
m = even.size();
memset(adj,0,sizeof(adj));
rep(i,n) rep(j,m) if(ok(odd[i], even[j])) adj[i][j] = 1;
//bpm
memset(matchL,-1,sizeof(matchL));
memset(matchR,-1,sizeof(matchR));
int res = 0;
rep(i,n) {
memset(flag,0,sizeof(flag));
if(bpm(i)) res++;
}
return res;
}
};
</pre><div><br />
</div>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com1tag:blogger.com,1999:blog-8676956288282165818.post-90261097858942142292010-11-24T04:55:00.002+06:002012-02-19T17:03:02.243+06:00TopCoder SRM 480 Div 1 Medium (NetworkSecurity)Problem Link : <a href="http://www.topcoder.com/stat?c=problem_statement&pm=10736">http://www.topcoder.com/stat?c=problem_statement&pm=10736</a><br />
<br />
This is a nice graph theory problem. The key observation here is that there is no point placing a data gate on an edge that is not <b>directly</b> connected to a server. Because in this way it can serve maximum number of clients. You might think if a client is connected to all the servers through some path and all the paths share an edge (a bridge) that is not directly connected to a server, why not just place a data gate on that edge as it will be useful for all of the paths? The answer is though it comes handy for the client in question, it does not do any help for the clients that are directly connected to the server. They still need a data gate between them and server. So, we have to place data gates further down the path anyway and that gate on the bridge edge will just be redundant.<br />
<br />
<a name='more'></a><br />
<br />
However, not all the clients that are directly connected to a server will require a data gate because sometimes it can choose an alternative path that goes through other clients. So, we have to place gates only for those clients for which we can't find any alternative path.<br />
<br />
Check the source code for more explanations -<br />
<br />
<pre class="prettyprint">/*
Problem Name : NetworkSecurity
Problem Number : TopCoder SRM 480 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=10736
Problem Type : Graph Theory
Difficulty : 5 / 10
Interest : 7 / 10
Complexity : O((N+M)^3)
Date : November 24, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define rep(i,n) for(i=0;i<(n);i++)
#define MAXN 100
struct NetworkSecurity{
bool a[MAXN+2][MAXN+2]; //adjacency matrix
int secureNetwork(vector <string> clientCable, vector <string> serverCable) {
int i,j,k,res;
int n = clientCable.size(),m = serverCable[0].size();
memset(a,0,sizeof(a));
rep(i,n) rep(j,n) if(clientCable[i][j] == 'Y') a[i][j] = 1;
rep(i,n) rep(j,m) if(serverCable[i][j] == 'Y') a[i][j+n] = 1;
rep(k,n) rep(i,n) rep(j,n) a[i][j] |= (a[i][k]&a[k][j]);//floyd warshall
res=n*m;
rep(i,n) rep(j,m) {
if(a[i][j+n] == 0) res--; //if no path to server, then no need to place a data gate
else { //if we can find an intermediate node betwen the current node and server, we can use the gate for that node
rep(k,n) if(k!=i && a[i][k] && a[k][j+n]) { res--; break;}
}
}
return res;
}
};
</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com0tag:blogger.com,1999:blog-8676956288282165818.post-37181376015971762232010-11-23T03:05:00.002+06:002012-02-19T17:03:13.961+06:00TopCoder SRM 379 Div 1 Medium (TheAirTripDivOne)The problems of latest TopCoder <a href="http://www.topcoder.com/stat?c=round_overview&er=5&rd=14241">SRM 488</a> were set by <a href="http://www.topcoder.com/tc?module=MemberProfile&cr=13351270&tab=alg">Vasyl</a>. The set was nice and a bit on the harder side. So, I was looking for the problems Vasyl set previously. I've found this <a href="http://www.topcoder.com/stat?c=problem_statement&pm=11030">one</a>.<br />
<br />
This problem is actually pretty straightforward. You just need to binary search on the <b>safety</b> parameter and for a particular value of <b>safety</b>, you have to determine if it is possible to make a series of trips within specified <b>time</b> to reach city <b>n</b> by waiting at least <b>safety</b> minutes between flights. This is essentially an shortest path problem on weighted graph which can be solved by <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">Dijkstra's algorithm</a>. We won't even need an efficient implementation as number of nodes and edges are within 500.<br />
<br />
<a name='more'></a><br />
<br />
You can check a more detailed analysis <a href="http://www.topcoder.com/wiki/display/tc/SRM+479">here</a>. Btw, you need to be careful to avoid overflow. Safe practice would be to just use long long.<br />
<br />
Source code -<br />
<br />
<pre class="prettyprint">/*
Problem Name : TheAirTripDivOne
Problem Number : TopCoder SRM 479 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=11030
Problem Type : Shortest Path, Binary Search
Difficulty : 5.5 / 10
Interest : 5 / 10
Complexity : O(VE)
Date : November 23, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define rep(i,n) for(i=0;i<(n);i++)
#define MAXN 477
#define INF 1023456789
struct Flight {
int A,B,F,T,P;
};
vector<Flight> fl;
int d[MAXN+2];
bool flag[MAXN+2];
struct TheAirTripDivOne{
int n;
int time;
vector<string> parse(const string& s,const string& delim=" ") {
vector<string>res;
string t;
for(int i=0;i!=s.size();i++) {
if(delim.find(s[i]) != string::npos) {
if(!t.empty()) {
res.push_back(t);
t="";
}
}
else t+=s[i];
}
if(!t.empty()) res.push_back(t);
return res;
}
long long get_next_flight(long long F,long long P, long long cur, long long safety, bool is_first) {
if(is_first) safety = 1;
long long x = (cur + safety - F + P - 1) / P;
if(x < 0) x = 0;
return F + x * P;
}
bool possible(int safety) {
int i,j,mn,mnd;
long long next;
for(i=1;i<=n;i++) d[i] = INF;
memset(flag,0,sizeof(flag));
d[1] = 0;
for(i=1;i<n;i++) {
mnd = INF;
for(j=1;j<=n;j++) if(!flag[j]) {
if(d[j] < mnd) { mn = j; mnd = d[j]; }
}
if(mnd == INF) break;
rep(j,(int)fl.size()) if(fl[j].A == mn) {
next = get_next_flight(fl[j].F, fl[j].P, mnd, safety, (i == 1));
if(d[fl[j].B] > next + fl[j].T) d[fl[j].B] = next + fl[j].T;
}
flag[mn] = true;
}
return (d[n] <= time);
}
int find(int n, vector <string> flights, int time) {
int i;
this->n = n;
this->time = time;
string s = "";
rep(i, (int)flights.size()) s += flights[i];
vector<string> vs = parse(s);
fl.clear();
vector<string> t;
Flight f;
rep(i, (int)vs.size()) {
t = parse(vs[i],",");
f.A = atoi(t[0].c_str());
f.B = atoi(t[1].c_str());
f.F = atoi(t[2].c_str());
f.T = atoi(t[3].c_str());
f.P = atoi(t[4].c_str());
fl.push_back(f);
}
int lo = 1, hi = 1000000000, mid;
while(hi-lo >= 5) {
mid = (lo+hi)>>1;
if(possible(mid)) lo = mid;
else hi = mid-1;
}
for(i=hi;i>=lo;i--) {
if(possible(i)) return i;
}
return -1;
}
};</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com2tag:blogger.com,1999:blog-8676956288282165818.post-50912238629978123432010-11-22T15:43:00.002+06:002012-02-19T17:03:24.591+06:00TopCoder SRM 395 Div 1 Medium (Skyscrapers)Problem link: http://www.topcoder.com/stat?c=problem_statement&pm=8582&rd=11129<br />
<br />
Problem description - <br />
<blockquote><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Helvetica, Verdana, sans-serif; font-size: 11px; line-height: 15px;">The skyline of the city of Terrapin City has <b>N</b> buildings all in a straight line; each building has a distinct height between 1 and <b>N</b>, inclusive. The building at index i is considered visible from the left is there is no building with a smaller index that is taller (formally, height[j] < height[i] for all j < i). Similarly, a building is visible from the right if there is no taller building with a higher index (height[j] < height[i] for all j > i). For example, if the buildings in order are {1, 3, 5, 2, 4}, then three buildings are visible from the left (1, 3 and 5), but only two are visible from the right (4 and 5).<br />
<br />
<a name='more'></a><br />
<br />
You will be given <b>N</b>, <b>leftSide</b> and <b>rightSide</b>, corresponding to the total number of buildings, the buildings visible from the left, and the buildings visible from the right, respectively. Return the number of permutations of the buildings that are consistent with these values; as this can be a large number, you should return it modulo 1000000007. </span><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Helvetica, Verdana, sans-serif; font-size: 11px; line-height: 15px;"><b>N</b> will be between 1 and 100, inclusive. </span><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Helvetica, Verdana, sans-serif; font-size: 11px; line-height: 15px;"><b>leftSide</b> and <b>rightSide</b> will be between 1 and <b>N</b>, inclusive.</span></blockquote>It is a dynamic programming problem. Among the <b>N</b> elements, if we place the highest element in position <b>i</b> (1-based), it will be visible from both left and right. So, we now will need to know number of ways we can place buildings such that there are <b>leftSide-1</b> buildings visible among the <b>i-1</b> buildings on the left and <b>rightSide-1</b> buildings visible among the <b>N-i</b> buildings on the right. You can choose the left set of buildings in <b>nCr(N-1, i-1)</b> ways.<br />
<br />
Now, to calculate the number of ways in which we can place <b>N</b> buildings such that <b>S</b> are visible from left (or right), we can think in a similar way. This time, place the smallest one first. If we place it on the leftmost position, it will be visible and we have to solve the sub-problem of <b>N-1</b> buildings with <b>S-1</b> visible ones. Otherwise, we can place the smallest one in one of the <b>N-1</b> available positions (where it will not be visible) and solve the sub problem of <b>N-1</b> buildings with <b>S</b> visible ones.<br />
<br />
I tried to place the largest one first in the second case, but it doesn't always work. You can find the code commented. Can you suggest what I was doing wrong?<br />
<br />
You can find other approaches for this problem in the official match <a href="http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm395">editorial</a>.<br />
<br />
C++ source code -<br />
<br />
<pre class="prettyprint">/*
Problem Name : Skyscrapers
Problem Number : TopCoder SRM 395 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=8582&rd=11129
Problem Type : Dynamic Programming
Difficulty : 6 / 10
Interest : 8 / 10
Complexity : O(N^2)
Date : November 22, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAXN 100
const long long MOD = 1000000007;
long long fact[MAXN+2];
struct Skyscrapers{
long long dp[MAXN+2][MAXN+2];
long long ncr[MAXN+2][MAXN+2];
long long go(int N, int S) {
if(N <= 1) {
if(S == N) return 1;
return 0;
}
if(dp[N][S] != -1) return dp[N][S];
long long &ret = dp[N][S];
ret = (go(N-1,S-1) + (N-1) * go(N-1,S))%MOD;
return ret;
/*ret = 0;
for(int i = 1; i <= N; i++) {
ret = (ret + (go(i-1,S-1) * (fact[N-i] * nCr(N-1,N-i))%MOD)%MOD) % MOD;
}
return ret;*/
}
long long nCr(int n, int r) {
if(r == 0) return 1;
if(r > n) return 0;
if(ncr[n][r] != -1) return ncr[n][r];
long long &ret = ncr[n][r];
ret = (nCr(n-1,r) + nCr(n-1,r-1))%MOD;
return ret;
}
int buildingCount(int N, int L, int R) {
long long res = 0;
int i;
memset(dp,-1,sizeof(dp));
memset(ncr,-1,sizeof(ncr));
fact[0] = 1;
for(i = 1; i <= MAXN; i++) fact[i] = (fact[i-1] * (long long)i) % MOD;
for(i = 1; i <= N; i++) {
res = (res + ((go(i-1,L-1)*go(N-i,R-1))%MOD * nCr(N-1,i-1))%MOD) % MOD;
}
return (int)res;
}
};</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com0tag:blogger.com,1999:blog-8676956288282165818.post-34901762709403368512010-11-21T20:32:00.002+06:002012-02-19T17:03:40.455+06:00TopCoder SRM 450 Div 1 Medium (Earn)I was searching for what problem to solve today. I tried some - few were too difficult and few were too easy or uninteresting. So, I decided to randomly solve a TopCoder Division 1 medium problem. <a href="http://www.topcoder.com/stat?c=problem_statement&pm=10389&rd=13904">This</a> one came up.<br />
<br />
Problem statement -<br />
<blockquote><span class="Apple-style-span" style="font-family: Arial, Helvetica, Verdana, sans-serif; font-size: xx-small;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; line-height: 15px;">As a serious strategy-games player, you know how important it is for your country to have a strong economy. In order to make this happen, you've just built n factories and hired k specialists. Unfortunately, you now have no gold left, and you must figure out the fastest way to raise target units of gold.</span></span></blockquote><span class="Apple-style-span" style="font-family: Arial, Helvetica, Verdana, sans-serif;"></span><br />
<blockquote><br />
<a name='more'></a><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, Verdana, sans-serif;"><span class="Apple-style-span" style="font-size: xx-small;"><span class="Apple-style-span" style="font-family: Arial, Helvetica, Verdana, sans-serif;">In a single round, you earn F*S units of gold, where F is the number of factories and S is the number of specialists you currently have. At the end of each round, you can build more factories and hire more specialists. Building one new factory or hiring one new specialist costs </span>price units of gold. As long as you can afford them, there is no limit to the number of factories and specialists you have. Return the minimum number of rounds required to earn at least target units of gold.<span class="Apple-style-span" style="font-family: Arial, Helvetica, Verdana, sans-serif;"> </span></span></span></blockquote><blockquote><span class="Apple-style-span" style="font-size: xx-small;">n, k, price and target will each be between 1 and 10^12, inclusive.</span></blockquote><br />
Now, there were 2 things that came intuitively to my mind -<ol><li>If you decide to spend on building factories or hiring specialists, you have to spend as much money as possible. There is no point spending half and saving the other half.</li>
<li>F and S have to stay as close as possible throughout the process.</li>
</ol><div>The second one is easy to prove. Lets say we have 2 numbers - x & y where x > y. Now, if we can increase either of them by one, which one should we do?</div><div>(x+1)y = xy + y</div><div>x(y+1) = xy + x</div><div>So, x(y+1) > (x+1)y</div><div>Its clear that we will have to increase the minimum of the two numbers.<br />
<br />
As target is at most 10^12, we will need no more than 10^6 factories or specialists. So, we can just simulate the process. In each step, we can do one of the 3 things -<br />
<br />
<ol><li>Go till the end with current number of factories and specialists.</li>
<li>If we have enough gold, we can buy factories / specialists in a way such that their difference is minimal.</li>
<li>If we don't have enough gold, we can save current day's gold for future use. In fact, instead of going one day at a time, we can calculate number of days required to acquire the minimum amount of gold needed to buy anything and advance our simulation to that day.</li>
</ol><div>Though it may seem natural to do this simulation using recursion, it will get segmentation fault as no. of steps can be as great as 10^6.</div><div><br />
</div><div>Another trick is to avoid the overflow. As n and k can be as high as 10^12, multiplying them will result in overflow.</div><div><br />
</div><div>C++ Source code -</div><pre class="prettyprint">/*
Problem Name : Earn
Problem Number : TopCoder SRM 450 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=10389&rd=13904
Problem Type : Simulation, Greedy
Difficulty : 6.5 / 10
Interest : 7 / 10
Date : November 21, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
#define min(a,b) (((a)<(b))?(a):(b))
struct StrongEconomy{
long long earn(long long n, long long k, long long price, long long target) {
long long res = 10000000, cur = 0, cur_day = 0;
long long z,d,x;
res*=res;
while(1) {
if(k > n) swap(n,k);
if(cur >= target) break;
if(log((long double)n)+log((long double)k) >= log((long double)target-cur)) { //log to prevent overflow
res = min(res, cur_day+1);
break;
}
//go through till the end
res = min(res, cur_day + (target - cur + n*k-1) / (n*k));
//buy factory or specialist
if(cur >= price) {
z = cur / price;
d = n - k;
if(d >= z) k+=z;
else {
z -= d;
k = n;
n += (z/2);
k += (z/2);
if(z%2 == 1) n++;
}
cur -= (cur/price)*price;
}
else { //save gold
x = (price - cur + n*k-1) / (n*k);
cur += (n*k*x);
cur_day += x;
}
}
return res;
}
};
</pre><div>Do you have any suggestions on what should I solve next?</div></div>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com2tag:blogger.com,1999:blog-8676956288282165818.post-16670377592141076062010-11-20T16:22:00.002+06:002012-02-19T17:05:06.446+06:00Strange TownThis is problem <a href="http://codeforces.com/contest/42/problem/D">D</a> from <a href="http://codeforces.com/contest/42">Codeforces Round 41</a>. You can find the analysis of the whole problemset <a href="http://codeforces.com/blog/entry/884">here</a>.<br />
<br />
The problem in short -<br />
<blockquote>Given a graph with <b>N</b> nodes and bidirectional edges between all pair of nodes, you have to assign <b>distinct</b> prices to the edges of the graph in a way such that all the Hamiltonian cycles cost the <b>same</b>. Price of an edge cannot exceed <b>1000</b>.</blockquote>Now there are some key observations here -<br />
<a name='more'></a><br />
<ol><li>Instead of assigning prices to <b>edges</b>, if we assign them to <b>nodes</b>, then all the Hamiltonian cycles will cost the same and that will be double the sum of prices of the nodes.</li>
<li>Lets say, there are 2 edges - <b>(i,j)</b> and <b>(k,l)</b>. Now <b>a[i] + a[j] != a[k] + a[l]</b> where <b>a[x]</b> is the price of node <b>x</b>. So, <b>a[i] != a[k] + a[l] - a[j]</b>.</li>
</ol><div>We can use observation 2 to employ a greedy strategy to solve the problem. We are going to assign prices one by one. For a node <b>i</b>, we have to assign it a price <b>a[i]</b> such that for any tuple <b>(j,k,l)</b> of already assigned nodes, <b>a[i] != a[k] + a[l] - a[j]</b>.</div><div><br />
</div><div>We could have just assigned Fibonacci numbers to the nodes as</div><blockquote><b>F(n) > F(n-1) + F(n-2) - F(1)</b></blockquote>that is every new number in Fibonacci sequence is greater than sum of 2 largest number minus the lowest number. So, naturally <b>a[i] != a[k] + a[l] - a[j]</b> will always hold. But 20-th number of Fibonacci sequence is way larger than 1000, so we can't use it.<br />
<br />
Btw, you can check this new (going-to-be-awesome) blog by Moshiur-<br />
<a href="http://problem-solving-notes.blogspot.com/">http://problem-solving-notes.blogspot.com/</a><br />
<br />
C++ Source code - <br />
<br />
<pre class="prettyprint">#include<stdio.h>
#include<string.h>
#define rep(i,n) for(i = 0; i < (n); i++)
#define MAXN 20
bool flag[1024];
int main() {
int N;
int i,j,k,l;
int a[MAXN+2];
while(scanf(" %d",&N)==1) {
a[0] = 1, a[1] = 2, a[2] = 3;
for(i = 3; i < N; i++) {
memset(flag,0,sizeof(flag));
rep(j,i) flag[a[j]] = 1;
rep(j,i) rep(k,i) rep(l,i) {
if(j == k || k == l || l == j) continue;
if(a[k] + a[l] - a[j] > 0) flag[a[k]+a[l]-a[j]] = 1;
}
for(j=1;j<=1000;j++) if(!flag[j]) break;
a[i] = j;
}
rep(i,N) {
rep(j,N) {
if(j > 0) printf(" ");
if(i == j) printf("0");
else printf("%d",a[i]+a[j]);
}
printf("\n");
}
}
return 0;
}</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com1tag:blogger.com,1999:blog-8676956288282165818.post-79969406943335788152010-11-17T17:55:00.000+06:002010-11-17T17:55:53.209+06:00Taking a breakI'm taking a break of 2/3 days from this blog as it is Eid day here. Alhough few years back, when I was a university student, I used to spend these days solving problems and participating in contests, things are a bit different right now - have to take some family responsibilities :)<br />
<br />
Eid Mubarak to all!Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com0tag:blogger.com,1999:blog-8676956288282165818.post-74238611798074682902010-11-16T10:49:00.001+06:002012-02-19T16:39:54.594+06:00Product of PricesI've solved another Binary Indexed Tree problem today. It is the Div 1 Hard <a href="http://www.topcoder.com/stat?c=problem_statement&pm=10170&rd=13515">problem</a> from TopCoder SRM 424. This problem is a bit harder to formulate than the previous one. You can check the complete analysis of the problem in the official match <a href="http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm424">editorial</a>. And don't forget to check the <a href="http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees">tutorial</a> if you have any difficulty understanding BIT.<br />
<br />
<a name='more'></a><br />
<br />
I'm not going into any detail analysis today as the editorial explains the solution nicely. Just note that BIT stores the frequencies from index 1 and in this problem we need indices in the range [0,L). So, we have to increase each index by 1.<br />
<br />
<br />
<pre class="prettyprint">/*
Problem Name : Product Of Prices
Problem Number : TopCoder SRM 424 Div 1 Hard
Link : http://www.topcoder.com/stat?c=problem_statement&pm=10170&rd=13515
Problem Type : Search
Difficulty : 6.5 / 10
Interest : 8.5 / 10
Complexity : O(NlogL)
Date : November 16, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define rep(i,n) for(i=0;i<(n);i++)
#define MAXL 200000
#define i64 long long
const i64 MOD = 1000000007;
i64 tree[2][MAXL+2];
int L;
struct ProductOfPrices{
void update(int tr, int dex, int val) {
while(dex <= L) {
tree[tr][dex] += val;
dex += (dex & -dex);
}
}
i64 read(int tr, int dex) {
i64 sum = 0;
while(dex > 0) {
sum += tree[tr][dex];
dex -= (dex & -dex);
}
return sum;
}
int product(int N, int L, int X0, int A, int B) {
::L = L;
int x;
int i;
i64 f1,f2, s1,s2, sl,sh;
i64 res = 1;
A %= L;
B %= L;
memset(tree,0,sizeof(tree));
x = X0 % L;
update(0,x+1,1);
update(1,x+1,x+1);
for(i=1;i<N;i++) {
x = (x * (long long)A + B) % L;
f1 = read(0,x+1); //total numbers below (or equal) current number
f2 = read(0,L) - f1; //total numbers above current number
s1 = read(1,x+1); // sum below (or equal) current number
s2 = read(1,L) - s1; // sum above current number
sl = (f1 * (x+1) - s1)%MOD; //sum of differences for numbers below (or equal) current number
sh = (s2 - f2 * (x+1))%MOD; //sum of differences for numbers above current number
res = (res * (sl + sh)%MOD) % MOD;
update(0,x+1,1);
update(1,x+1,x+1);
}
return res;
}
};
</pre>Sabbir Yousuf Sannyhttp://www.blogger.com/profile/06850218318798376482noreply@blogger.com2