12406 - Help Dexter

All about problems in Volume 124. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

12406 - Help Dexter

Post by brianfry713 »

I didn't notice any tricky test cases, here's some I/O from my AC program:

Code: Select all

11
2 2
2 1
2 3
15 12
12 15
1 1
1 6
6 1
17 17
17 3
3 17

Code: Select all

Case 1: 12
Case 2: 12 22
Case 3: impossible
Case 4: 111111212122112 222111212122112
Case 5: impossible
Case 6: 2
Case 7: impossible
Case 8: 111112 222222
Case 9: 11211111212122112
Case 10: 11111111111111112 22222222222222112
Case 11: impossible
Check input and AC output for thousands of problems on uDebug!
Top
outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

Re: 12406 - Help Dexter

Post by outsbook »

Input:

Code: Select all

153
1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4
5 1
5 2
5 3
5 4
5 5
6 1
6 2
6 3
6 4
6 5
6 6
7 1
7 2
7 3
7 4
7 5
7 6
7 7
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
11 1
11 2
11 3
11 4
11 5
11 6
11 7
11 8
11 9
11 10
11 11
12 1
12 2
12 3
12 4
12 5
12 6
12 7
12 8
12 9
12 10
12 11
12 12
13 1
13 2
13 3
13 4
13 5
13 6
13 7
13 8
13 9
13 10
13 11
13 12
13 13
14 1
14 2
14 3
14 4
14 5
14 6
14 7
14 8
14 9
14 10
14 11
14 12
14 13
14 14
15 1
15 2
15 3
15 4
15 5
15 6
15 7
15 8
15 9
15 10
15 11
15 12
15 13
15 14
15 15
16 1
16 2
16 3
16 4
16 5
16 6
16 7
16 8
16 9
16 10
16 11
16 12
16 13
16 14
16 15
16 16
17 1
17 2
17 3
17 4
17 5
17 6
17 7
17 8
17 9
17 10
17 11
17 12
17 13
17 14
17 15
17 16
17 17
My program generate output:

Code: Select all

Case 1: 2
Case 2: 12 22
Case 3: 12
Case 4: 112 222
Case 5: 112 212
Case 6: 112
Case 7: 1112 2222
Case 8: 1112 2212
Case 9: 1112 2112
Case 10: 2112
Case 11: 11112 22222
Case 12: 11112 22212
Case 13: 11112 22112
Case 14: 12112 22112
Case 15: 22112
Case 16: 111112 222222
Case 17: 111112 222212
Case 18: 111112 222112
Case 19: 112112 222112
Case 20: 122112 222112
Case 21: 122112
Case 22: 1111112 2222222
Case 23: 1111112 2222212
Case 24: 1111112 2222112
Case 25: 1112112 2222112
Case 26: 1122112 2222112
Case 27: 1122112 2122112
Case 28: 2122112
Case 29: 11111112 22222222
Case 30: 11111112 22222212
Case 31: 11111112 22222112
Case 32: 11112112 22222112
Case 33: 11122112 22222112
Case 34: 11122112 22122112
Case 35: 12122112 22122112
Case 36: 12122112
Case 37: 111111112 222222222
Case 38: 111111112 222222212
Case 39: 111111112 222222112
Case 40: 111112112 222222112
Case 41: 111122112 222222112
Case 42: 111122112 222122112
Case 43: 112122112 222122112
Case 44: 112122112 212122112
Case 45: 212122112
Case 46: 1111111112 2222222222
Case 47: 1111111112 2222222212
Case 48: 1111111112 2222222112
Case 49: 1111112112 2222222112
Case 50: 1111122112 2222222112
Case 51: 1111122112 2222122112
Case 52: 1112122112 2222122112
Case 53: 1112122112 2212122112
Case 54: 1212122112 2212122112
Case 55: 1212122112
Case 56: 11111111112 22222222222
Case 57: 11111111112 22222222212
Case 58: 11111111112 22222222112
Case 59: 11111112112 22222222112
Case 60: 11111122112 22222222112
Case 61: 11111122112 22222122112
Case 62: 11112122112 22222122112
Case 63: 11112122112 22212122112
Case 64: 11212122112 22212122112
Case 65: 11212122112 21212122112
Case 66: 11212122112
Case 67: 111111111112 222222222222
Case 68: 111111111112 222222222212
Case 69: 111111111112 222222222112
Case 70: 111111112112 222222222112
Case 71: 111111122112 222222222112
Case 72: 111111122112 222222122112
Case 73: 111112122112 222222122112
Case 74: 111112122112 222212122112
Case 75: 111212122112 222212122112
Case 76: 111212122112 221212122112
Case 77: 111212122112 211212122112
Case 78: 111212122112
Case 79: 1111111111112 2222222222222
Case 80: 1111111111112 2222222222212
Case 81: 1111111111112 2222222222112
Case 82: 1111111112112 2222222222112
Case 83: 1111111122112 2222222222112
Case 84: 1111111122112 2222222122112
Case 85: 1111112122112 2222222122112
Case 86: 1111112122112 2222212122112
Case 87: 1111212122112 2222212122112
Case 88: 1111212122112 2221212122112
Case 89: 1111212122112 2211212122112
Case 90: 1111212122112 2111212122112
Case 91: 1111212122112
Case 92: 11111111111112 22222222222222
Case 93: 11111111111112 22222222222212
Case 94: 11111111111112 22222222222112
Case 95: 11111111112112 22222222222112
Case 96: 11111111122112 22222222222112
Case 97: 11111111122112 22222222122112
Case 98: 11111112122112 22222222122112
Case 99: 11111112122112 22222212122112
Case 100: 11111212122112 22222212122112
Case 101: 11111212122112 22221212122112
Case 102: 11111212122112 22211212122112
Case 103: 11111212122112 22111212122112
Case 104: 11111212122112 21111212122112
Case 105: 11111212122112
Case 106: 111111111111112 222222222222222
Case 107: 111111111111112 222222222222212
Case 108: 111111111111112 222222222222112
Case 109: 111111111112112 222222222222112
Case 110: 111111111122112 222222222222112
Case 111: 111111111122112 222222222122112
Case 112: 111111112122112 222222222122112
Case 113: 111111112122112 222222212122112
Case 114: 111111212122112 222222212122112
Case 115: 111111212122112 222221212122112
Case 116: 111111212122112 222211212122112
Case 117: 111111212122112 222111212122112
Case 118: 111111212122112 221111212122112
Case 119: 111111212122112 211111212122112
Case 120: 211111212122112
Case 121: 1111111111111112 2222222222222222
Case 122: 1111111111111112 2222222222222212
Case 123: 1111111111111112 2222222222222112
Case 124: 1111111111112112 2222222222222112
Case 125: 1111111111122112 2222222222222112
Case 126: 1111111111122112 2222222222122112
Case 127: 1111111112122112 2222222222122112
Case 128: 1111111112122112 2222222212122112
Case 129: 1111111212122112 2222222212122112
Case 130: 1111111212122112 2222221212122112
Case 131: 1111111212122112 2222211212122112
Case 132: 1111111212122112 2222111212122112
Case 133: 1111111212122112 2221111212122112
Case 134: 1111111212122112 2211111212122112
Case 135: 1211111212122112 2211111212122112
Case 136: 1211111212122112
Case 137: 11111111111111112 22222222222222222
Case 138: 11111111111111112 22222222222222212
Case 139: 11111111111111112 22222222222222112
Case 140: 11111111111112112 22222222222222112
Case 141: 11111111111122112 22222222222222112
Case 142: 11111111111122112 22222222222122112
Case 143: 11111111112122112 22222222222122112
Case 144: 11111111112122112 22222222212122112
Case 145: 11111111212122112 22222222212122112
Case 146: 11111111212122112 22222221212122112
Case 147: 11111111212122112 22222211212122112
Case 148: 11111111212122112 22222111212122112
Case 149: 11111111212122112 22221111212122112
Case 150: 11111111212122112 22211111212122112
Case 151: 11211111212122112 22211111212122112
Case 152: 11211111212122112 21211111212122112
Case 153: 11211111212122112
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed
Top
outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

Re: 12406 - Help Dexter

Post by outsbook »

Remove Code After AC

I go WA For this test Case
Input:

Code: Select all

2
3 4
4 5
Output:

Code: Select all

Case 1: 112
Case 2: 2112
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed
Top
Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

Re: 12406 - Help Dexter

Post by Farsan »

Getting TLE....is this problem solvable with bitmask?? i counted current position and previous combination of (1,2) as my dp state.Here is my code.

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<limits>
#include<iomanip>
#define inf 4611686018427387904
#define Max(v) *max_element(v.begin(),v.end())
#define Min(v) *min_element(v.begin(),v.end())
#define inp1(x) scanf("%d",&x)
#define inp2(x,y) scanf("%d %d",&x,&y)
#define Unique(v) v.resize(unique(v.begin(),v.end())-v.begin())
#define Sort(v) sort(v.begin(),v.end(),greater<int>());
#define fread() freopen("inp.txt","r",stdin)
#define fwrite() freopen("out.txt","w",stdout)
#define mem(n,m) memset(n,m,sizeof n)
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
int cnt_leading_zero_bits(int N){return __builtin_clz(N);}
int cnt_trailing_zero_bits(int N){return __builtin_ctz(N);}
int cnt_no_of_bits_on(int N){return __builtin_popcount(N);}

//priority_queue< int, vector<int>, greater<int> > PQ;// keeps in ascending order
// bool operator < ( const node& b ) const


using namespace std;

long long dp_mn[18][1<<18],dp_mx[18][1<<18],p,q;
bool visited[18][1<<18];

pair<long long,long long> solve(int no,int msk,long long val)
{
    if(no>p)
    {
        if(val%q==0&&val!=0)
        {
            return make_pair(val,val);
        }
        else
        return make_pair(inf,-1);
    }
    if(visited[no][msk])
    return make_pair(dp_mn[no][msk],dp_mx[no][msk]);
    visited[no][msk]=true;
    pair<long long,long long>a,b,c;
    int msk2=Set(msk,no);
    long long one,two;
    one=val+pow(10,no-1);
    two=val+2*pow(10,no-1);
    a=solve(no+1,msk,one);
    b=solve(no+1,msk2,two);
    if(a.first==-1)
    dp_mn[no][msk]=b.first;
    else if(b.first==-1)
    dp_mn[no][msk]=a.first;
    else
    dp_mn[no][msk]=min(a.first,b.first);
    if(a.second==inf)
    dp_mx[no][msk]=b.second;
    else if(b.second==inf)
    dp_mx[no][msk]=a.second;
    else
    dp_mx[no][msk]=max(a.second,b.second);
    c.first=dp_mn[no][msk];
    c.second=dp_mx[no][msk];
    return c;
}

int main()
{
    int i,j,k,m,n,t,cs=0;
    cin>>t;
    while(t--)
    {
        cs++;
        cin>>p>>q;
        q=pow(2,q);
        for(i=0;i<=p;i++)
        {
            k=pow(2,i);
            for(j=0;j<=k;j++)
            visited[i][j]=false;

        }
        //mem(visited,false);
        //mem(dp,-1);
        //inp2(p,q);
        pair<long long,long long>pa;
        pa=solve(1,0,0);
        cout<<"Case "<<cs<<": ";
        if(pa.first==inf)
        cout<<"impossible\n";
        else
        {
            if(pa.first==pa.second)
            {
                cout<<pa.first<<endl;
            }
            else
            {
                cout<<pa.first<<" "<<pa.second<<endl;
            }
        }
    }
    return 0;
}
Top
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12406 - Help Dexter

Post by brianfry713 »

I just tested every number of length p made up of only 1's and 2's. Why do you need DP and bitmask?
Check input and AC output for thousands of problems on uDebug!
Top
Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

Re: 12406 - Help Dexter

Post by Farsan »

Because thats what came to my mind at first glance :roll: @brianfry713
Top
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12406 - Help Dexter

Post by brianfry713 »

Rewrite your code as I described.
Check input and AC output for thousands of problems on uDebug!
Top
Post Reply

Return to “Volume 124 (12400-12499)”