alohamaloha's blog

By alohamaloha, 12 years ago, In English

I have been trying this problem http://www.spoj.pl/problems/FPOLICE/. My idea is to modify the single source shortest path problem to 2-D.So instead of using an array to denote the shortest distance I am using a 2-D matrix where state[i][j] indicates the shortest path from the source to the ith node with still having j time left.(The upper limit on left time is denoted by t) Finally I check the last row (state[n-1][j] for all j=t to j=0 ) the minimum cost.If the minimum cost comes out to be INFINITY then there is no way to reach the destination with atleast 0 time remaining.If minimum costs occur for several values of j i pick up the j which is larger.That is the case which yields more remaining time ( i.e. minimum time).For the single source shortest path I started with dijikistra but then switched to bellman-ford for simplicity.(Doesn't looks like o(n^2*t) will be problem)

UPD: Code modified to fix some bugs

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<stack>
#include<queue>
#include<string>
#include<cstring>


#define PR(x) printf(#x"=%d\n",x)
#define READ2(x,y) scanf("%d %d",&x,&y)
#define REP(i,a) for(int i=0;i<a;i++)
#define READ(x) scanf("%d",&x)
#define PRARR(x,n) for(int i=0;i<n;i++)printf(#x"[%d]=\t%d\n",i,x[i])
const int INF=2<<29;

int costMatr[101][101];
int timeMatr[101][101];
using namespace std;

int main()
	{
	int n;
	int t;
	/*Input section */
	int tstcase;
	scanf("%d",&tstcase);
	while(tstcase--){
	scanf("%d %d",&n,&t);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			{
			scanf("%d",&timeMatr[i][j]);
			}
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			{
			scanf("%d",&costMatr[i][j]);
			}
	
	
	/*End input */	
	
	int state[101][251]; //state[i][j] represents cost from source node to ith node with j time remaining
	for(int i=1;i<n;i++) 
		for(int j=0;j<=t;j++)
		{
		
		 state[i][j]=INF; //initialize all states to infinity
		
		 }
		 
	for(int i=0;i<=t;i++) state[0][i]=0; //cost to reach 0th node will be 0 regardless of time left
	for(int i=1;i<n;i++)
	if(t-timeMatr[0][i]>=0) state[i][t-timeMatr[0][i]]=costMatr[0][i]; //initialize state matrix for neighbours of source nodeh

	/*DP begin */
	for(int k=t;k>=0;k--)
	
		{
		for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
		if(i==j) continue;
		 
			if(costMatr[i][j]+state[i][k]<=state[j][k])
				{
				
				if(k-timeMatr[i][j]>=0) {
				#ifndef ONLINE_JUDGE
				printf("Distance to %dth node updated for time %d. previous value at this state=%d",j,k,state[j][k]);
				#endif
				state[j][k-timeMatr[i][j]]=costMatr[i][j]+state[i][k];
				#ifndef ONLINE_JUDGE
				printf("New value for this time %d =%d\n",k-timeMatr[i][j],state[j][k]);
				#endif
				}
				}
		
			
		}
	}
	
	/*DP END*/
	/*possible answer in state[n-1][t] where t is all possible values of remaining time */
	
	int minCost=INF;
	int minTime=t;	
	for(int k=t;k>=0;k--)
	{
	if(state[n-1][k]<minCost)
	{
	minCost=state[n-1][k];
	minTime=k;
	}
	}
	if(minCost==INF)
	puts("-1");
	else
	printf("%d %d\n",minCost,t-minTime);
	}
	}

Kindly suggest some test cases where my algorithm might be failing.I am almost sure my idea of 2-D Dp is correct,just that I am not able to implement it properly.

UPD: Got the bug.TYpo in if(costMatr[i][j]+state[i][k]<=state[j][k]) should have been if(costMatr[i][j]+state[i][k]<=state[j][k-timeMatr[i][j]])

Full text and comments »

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

By alohamaloha, 12 years ago, In English
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<stack>
#include<queue>
#include<string>
#include<cstring>


#define PR(x) printf("")
#define READ2(x,y) scanf("%d %d",&x,&y)
#define REP(i,a) for(int i=0;i<a;i++)
#define READ(x) scanf("%d",&x)
#define PRARR(x,n) for(int i=0;i<n;i++)printf("")
using namespace std;
typedef long long ll;
int main() { 
string s1,s2;
cin>>s1;cin>>s2;
int idx=1;
string subst;
char ch=s1[0];
int len1=s1.length();
int len2=s2.length();
int lenC=1;
while(idx<len1&&ch!=s1[idx++]) lenC++;
PR(lenC);
if(lenC!=len1) {

for(int j=1;j<lenC&&j<len1;j++){
while(len1%lenC!=0) lenC++;
for(int k=j+lenC;k<len1;k+=lenC){
if(s1[j]!=s1[k]) {
//printf("VIolation at %d %d char values %c %c\n",j,k,s1[j],s1[k]);
k-=lenC;
lenC+=1;

}

}
}

}
lenC=min(len1,lenC);
int count1=0;
for(int i=1;i*lenC<=len1;i++) count1++;
PR(lenC);
PR(count1);
subst=s1.substr(0,lenC);
if(len2%lenC!=0||len2<lenC) {
			puts("0");
			return 0;
		}
bool flg=false;
for(int i=0;i<lenC;i++){
for(int j=i;j<len2;j+=lenC)
if(s2[j]!=subst[i]){
//printf("VIolation at %d %d char values %c %c\n",i,j,s2[j],subst[i]);
flg=true;
break;
}
if(flg) break;
}
if(flg) {
		puts("0");
		return 0;
	}
int num2=0;
for(int i=1;i*lenC<=len2||i*lenC<=len1;i++) if(len2%(i*lenC)==0&&len1%(i*lenC)==0)num2++;
int ans=num2;
printf("%d\n",ans);
}

I am getting wrong answer on pretest 9.The pretest is very long so can't see the complete test case. My solution is based on the following approach 1.if a substring x is a divisor of a string S then it will be either a.Shortest divisor of S(in terms of length) b.It can be broken down into smaller divisors based on the constraint for all divisor length l S.length()%l==0

I find out the smallest divisor in either string,then check if it is a divisor in the other string,if it is not then the strings dont have any common divisor.In case it is a divisor then i combine the smaller divisor to get bigger divisors such that the length of bigger divisors divide both S1.length() and S2.length() where S1 and S2 are the input strings.

Full text and comments »

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