### kavishrox's blog

By kavishrox, 9 years ago,

Hi,

I was trying to code a problem on printing all possible LIS of a string in sorted order. The link to the problem is http://www.spoj.com/problems/UPSUB/. My idea is simply to calculate a 2D LCS matrix by LCS(string s, sort(string s)) and then backtrack over the LCS matrix with optimization to get all the LIS. I am facing problems in optimizing my backtracking code because its visiting way too many states that required.

#include <bits/stdc++.h>
using namespace std;
/*u,l,d correspond to the possible directions from which the maximum value of the LCS array came from*/
struct node{
int val,u,l,d;
};
int n,maxlen;
set<string> ans;
string s,s1;
//int vis[110][110];
vector<vector<node > > dp;
/*calculates LIS=LCS(s,sort(s))*/
void lis(void){
s1=s;
sort(s1.begin(),s1.end());
//cout<<s1<<endl;
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
if(s1[i-1]==s[j-1]){
/*if(i==1 and j==2)
cout<<"Came wrong way "<<endl;*/
int x=max(max(dp[i-1][j].val,dp[i][j-1].val),dp[i-1][j-1].val+1);
dp[i][j].val=x;
if(dp[i-1][j].val==x){
dp[i][j].u=1;
}
if(dp[i][j-1].val==x){
dp[i][j].l=1;
}
if((dp[i-1][j-1].val+1)==x){
dp[i][j].d=1;
}
}
else{
int x=max(dp[i-1][j].val,dp[i][j-1].val);
dp[i][j].val=x;
if(dp[i-1][j].val==x){
dp[i][j].u=1;
}
if(dp[i][j-1].val==x){
dp[i][j].l=1;
}
}
}
}
maxlen=dp[n][n].val;
//cout<<maxlen<<endl;
}
string st;
void dfs(int x,int y){
cout<<"now at "<<x<<"\t"<<y<<endl;
if(x==0 or y==0){
if(st.size()==maxlen){
set<string>::iterator it=ans.begin();
ans.insert(it,st);
//cout<<"print at "<<x<<"\t"<<y<<endl;
}
return;
}
if(dp[x][y].d==1 ){
st=s[y-1]+st;
dfs(x-1,y-1);
st.erase(st.begin(),st.begin()+1);
}
if(dp[x][y].u==1){
dfs(x-1,y);
}
if(dp[x][y].l==1){
dfs(x,y-1);
}
}
void print_lis(void){
for(int i=0;i<=n;i++){
cout<<endl;
for(int j=0;j<=n;j++){
cout<<dp[i][j].val<<"\t";
}
}
cout<<endl;
}
int main(void){
int tc;
cin>>tc;
while(tc--){
cin>>s;
n=s.size();
dp.resize(n+1);
for(int i=0;i<=n;i++){
dp[i].resize(n+1);
}
lis();
//print_lis();
dfs(n,n);
//sort(ans.begin(),ans.end());
for(set<string>::iterator it=ans.begin();it!=ans.end();it++)
cout<<*it<<endl;
}
return 0;
}



Please suggest me some ways by which I can optimize the dfs(i,j) part.

• -3

By kavishrox, 9 years ago,

I made the following code for the problem http://www.spoj.com/problems/HIKE/ but its showing Wrong Answer and I am not able to find the case for which its going wrong . It would be very helpful if someone gives the case for my solution goes wrong.

#include<iostream>
#include<cstdio>
#include<vector>
#include<utility>
#include<string>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<queue>

using namespace std;

vector<vector<char> > v;
int dp[51][51][51];
queue<int> q;
int n;
void bfs(int a,int b,int c){
a--,b--,c--;
q.push(a);
q.push(b);
q.push(c);
dp[a][b][c]=0;
//cout<<dp[a][b][c]<<endl;
while(!(q.empty())){
int x=q.front();
q.pop();
int y=q.front();
q.pop();
int z=q.front();
q.pop();
for(int i=0;i<n;i++){
if(v[x][i]==v[y][z] and dp[i][y][z]>dp[x][y][z]+1){
q.push(i);
q.push(y);
q.push(z);
dp[i][y][z]=dp[x][y][z]+1;
}
else if(v[y][i]==v[x][z] and dp[x][i][z]>dp[x][y][z]+1){
q.push(x);
q.push(i);
q.push(z);
dp[x][i][z]=dp[x][y][z]+1;
}
else if(v[z][i]==v[x][y] and dp[x][y][i]>dp[x][y][z]+1){
q.push(x);
q.push(y);
q.push(i);
dp[x][y][i]=dp[x][y][z]+1;
}
}
}
}
int main(){

while(cin>>n and n){
v.resize(n);
for(int i=0;i<n;i++){
v[i].resize(n);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
dp[i][j][k]=INT_MAX-10;
}
}
}
int a,b,c;
cin>>a>>b>>c;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>v[i][j];
}
}
/*for(int i=0;i<n;i++){
cout<<endl;
for(int j=0;j<n;j++){
cout<<v[i][j]<<" ";
}
}*/
bfs(a,b,c);
int sol=INT_MAX-10;
for(int i=0;i<n;i++){
//cout<<dp[i][i][i]<<endl;
if(dp[i][i][i] < sol)
sol=dp[i][i][i];
}
if(sol==INT_MAX-10)
cout<<"impossible"<<endl;
else
cout<<sol<<endl;
}
return 0;
}


• 0

By kavishrox, 9 years ago,

Code of the day(COD) is a 10 day long coding contest of MNNIT Allahabad as a part of the technical festival Avishkar in which one question will show up every day at 10 PM IST and you will get points based on how early you can solve that problem .
The theme for this year's contest is Sherlock Holmes to make it all more interesting. The contest starts on 22 September @ 10 PM IST .

• -13

By kavishrox, 10 years ago,

I was doing this particular problem 1021. Aibohphobia and not able to space optimize my DP code . Though I did it using length-lcs method , I couldn't do it this way .

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
static int dp[6101][6101];
main()
{
int tc;
scanf("%d",&tc);
while(tc--)
{
char s[6102];
scanf("%s",s);
int len=strlen(s);
memset(dp,0,sizeof dp);
for(int i=1;i<len;i++)
for(int j=0,k=i;k<len;k++,j++)
dp[j][k]=(s[j]==s[k])?dp[j+1][k-1]:min(dp[j][k-1],dp[j+1][k])+1;
printf("%d\n",dp[0][len-1]);
}
return 0;
}


• 0

By kavishrox, 10 years ago,

I wrote the following code using dijkstra's for the problem but can't determine why the answer is going wrong . [](http://www.spoj.com/problems/FPOLICE/) http://www.spoj.com/problems/FPOLICE/

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<utility>
#include<climits>
using namespace std;
#define mp make_pair
main()
{
int n,tc,t;
scanf("%d",&tc);
while(tc--)
{
scanf("%d%d",&n,&t);
vector<vector<int> > dist,risk;
dist.resize(n);
risk.resize(n);
for(int i=0;i<n;i++)
{
dist[i].resize(n);
for(int j=0;j<n;j++)
scanf("%d",&dist[i][j]);
}
for(int i=0;i<n;i++)
{
risk[i].resize(n);
for(int j=0;j<n;j++)
scanf("%d",&risk[i][j]);
}
queue <pair<int,int> > q;
vector <vector<int> > dp;
vector <vector<bool> > ch;
dp.resize(t+1);
ch.resize(t+1);
for(int i=0;i<t+1;i++)
{
ch[i].resize(n,false);
dp[i].resize(n,INT_MAX);
}
/*-----------------------------------------------------------------------------------------------------*/
//DIJKSTRA'S starts here
dp[0][0]=0;
q.push(mp(0,0));
ch[0][0]=true;
while(q.size())
{
pair<int,int> myp=q.front();
//cout<<myp.first<<" "<<myp.second<<endl;
q.pop();
ch[myp.first][myp.second]=false;
int amt=dp[myp.first][myp.second];
for(int i=0;i<n;i++)
{
//cout<<"Hi2"<<endl;
if(i!=myp.second)
{
//cout<<"Hi3"<<endl;
int nt=dist[myp.second][i]+myp.first;
if(nt>t)
continue;
int tot=amt+risk[myp.second][i];
if(tot<dp[nt][i])
{
//cout<<"Hi"<<endl;
dp[nt][i]=tot;
if(!ch[nt][i])
{
//cout<<"Hi1"<<endl;
ch[nt][i]=true;
q.push(mp(nt,i));
}
}

}
}
}
int min=INT_MAX,x;
for(int i=0;i<=t;i++)
if(dp[i][n-1]<min)
{
min=dp[i][n-1];
x=i;
}
printf("%d %d\n",min,x);
}
return 0;
}



• 0

By kavishrox, 10 years ago,

Hi Guys,- I am only 2 contests old on codeforces but the way the competition is organized and the level of participation impresses me a lot. I thought therefore to write my views over the benefits of using codeforces

### CODEFORCES

1. A very good ELO rating system . Quite balanced and relative for all.
2. Regular competitions. This one is very good for a person who is new to coding(like me) and wants to get into the groove of things as fast as possible . A competition almost every week ensures that one doesn't have to go here and there for online competitions.
3. The problems are good in a sense that they are usually set by people having very good intellect and experience. A competition involves problems on 4-5 different .
4. Testing system — Like topcoder the hacking system during a running contest ensures that a problem has a lot of good test cases for program to pass. One has to make his program time efficient and considering each and every test case otherwise if it gets hacked in the end one could loose easy points because of that. We usually get to learn it a hard way when a 500 point problem goes away for some silly mistake.
5. One gets to know where his program went wrong because the test cases on which the program was tested are shown to every user with the time it took for each test case. So here one gets to know very well the efficiency of his solution and the place where it actually went wrong.
6. A 2 hour contest is ideal because it neither doesn't take a lot of time from your busy schedule and involves adrenaline rush throughout the competition because the price of a problem goes on decreasing as the competition advances. Another advantage is that usually in a 3 to 3.5 hour contest one gets a way to cheat on stack overflow or stack exchange because one may usually get good replies there within 1 hour(I have seen a lot of that on codechef cook off) .
7. The website runs awesome . Its very smooth during a competition and things start as and when supposed to. there are hardly any performance glitches during a competition.Usually codechef has a lot of it during its contests.
8. Following a top coder system of Room divisions and rating division is also very helpful because one gets questions which if he tries can solve.

so this was what I like about codeforces ... though there might be some points left i would like to know if in the contribution part one can give his/her problems for competitions even if one is not red or orange so that one gets to think of problems outside the domain of the available problems...

• +6