549 - Evaluating an Equations Board

[Sesse]

I tried to submit 549 with a lot of different algorithms and parser twists, but I always ended up getting WA... Finally, I added some basic sanity checks to the input parser... They failed. I've tried making a _very_ flexible parser, but still no luck... My algorithm is more than fast enough (~0.2secs), but it's a bit difficult when I think there is a data set error :-) Any ideas, anybody? Two people have obviously solved it...

[Sesse]

It was my fault after all -- I rewrote the parser once again and fixed a minor bug, and now it got accepted :-)

[oriol78]

Hi, can anybody posts inputs an outputs please? tanks for advance

[jjtse]

I'm working on that problem as well. One main concern here is subtraction.

Because 9-(5-4) is not the same as (9-5)-4.

[jjtse]

did you use recursion?

[Sesse]

No, I didn't use recursion, but you can solve the problem recursively if you'd like (I know that at least one of the solutions are written recursively).

/* Steinar */

[jjtse]

I didn't use recursion either. What I did was try every single possible combination.

But the problem with that is, trying combinations doesn't solve this problem:

9-(5-4) = 8 VS (9-5)-4 = 0.

With multiplication and addition, you don't run into this problem, as they are associative and commutative.

So What I did was, for every combination I try that has a 'minus' sign, I do this.

ans1 = a-b;
ans2 = b-a;

and then treat ans1 and ans2 as if they are two different cases and run independent test cases for each of them. This fixed the 9-(5-4) problem stated above, but the thing is, I submitted my codes and I still got wrong answer. So, I'm thinking what if it's something like 9-8-(7-6)-3-(2-1)....then I'm wondering if my program will still work for something like that. I don't know. Do you have any ideas? I'm working on this problem right now. I see you've dealt with this problem a while back. Did you get to solve it?

I'm pretty sure it's the way I deal with 'minus' operators that's giving me the wrong answer.

[Sesse]

You are sort of on the right track; but remember, you can also have (1-2)x(3+(4-5)) etc...

And yes, I solved it, but it's ages ago (as you can see, my last submitted run on it is from 2002). I still have the source, but I doubt this forum exists for trading solutions :-)

/* Steinar */

[jjtse]

haha, you misunderstood me. I'm not here to search for other people's codes. I'm here to write my own codes. I believe I'm 90% done. All the test cases I used have worked with my program, yet the judge keeps on saying 'wrong answer'. So I'm kind of stuck and don't know what can go wrong. I'm just looking for clues as to what kind of cases I haven't taken account of in my codes.

That example, (1-2)x(3+(4-5)) is one that I haven't tried and probably will fail on my program. Let me try this and see what happens. I'll let you know if I finished it.

Thanks.

*one more thing,

When you submit codes using your ID, and then check your own status, does it come out as someone else's name? I signed up like a week ago and this is what's happening. I'm getting someone else's ID and password. So when I submit code, it is not submitted under my name. Some of the guys in this forum just told me to wait a few more days....

[Sesse]

No such problem here, but I haven't submitted code in several years. :-) In any case, you'd have to consider arbitrary parenthesis setting, so (hint:) infix notation might not be the best possible data representation.

/* Steinar */

[nayimsust]

this is my code if any one have time then try to find my bug please :
i used straight forward mst algorithm :

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <algorithm>
#include <string>
using namespace std;

long array[100001][4],test,number,i,rank[100001],total,p[100001],x,y,j,k,n,m,counter[100001],mAx,f[100001],t=0;
char a[100],c;

int find_set( int x )
{
if( x != p[x] )
p[x]=find_set(p[x]);
return p[x];
}

void make_set( int x )
{
for(i=1;i<=x;++i)
{
p=i;
rank=0;
counter=1;
f=0;
}
}

void link( int x , int y )
{
if( rank[x] > rank[y] )
{
p[y]=x;
counter[x]+=counter[y];
if( mAx < counter[x] )
mAx=counter[x];
}
else
{
p[x]=y;
counter[y]+=counter[x];
if( mAx < counter[y])
mAx=counter[y];
if( rank[x] == rank[y] )
rank[y]=rank[y]+1;
}
}

void Union( int x , int y )
{
link(find_set(x) , find_set(y) );
}

int main()
{
scanf("%ld\n",&test);
while( test -- )
{
scanf("\n");
mAx=0;
gets(a);
number= (a[0]-'A')+1;
make_set( number );
n=-1;
while( gets(a) )
{
if( a[0] == NULL )
break;
array[++n][1]=(a[0]-'A')+1;
array[n][2]=(a[1]-'A')+1;
}
for(i=0;i<=n;++i)
if( find_set( array[1] ) != find_set( array[2] ) )
Union( array[1] , array[2] );

total=0;
for(i=1;i<=number;++i)
if( f[ p ] == 0 )
{
++total;
f[ p ] = 1;
}

/*for(i=1;i<=number;++i)
printf("%ld ",p[i]);
printf("\n");*/
if(t!=0)
printf("\n");
printf("%ld\n",total);
++t;
}
return 0;
}

[calicratis19]

@nayimsust check this input

Code: Select all

1

E
AB
CD
BE
CE

this is not the thread for this problem and when you post your code please try to follow the procedure . like i have posted the input.it would be easier to look at the code.
hope it helps.

[metaphysis]

The solution on uDebug seems buggy.

Code: Select all

+1xx0358+80
10

Output of uDebug is "solution", but it's impossible to get "10" just using "+1xx0358+80".

[metaphysis]

Test data generator.

Code: Select all

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, char *argv[])
{
    srand(time(NULL));
    
    char symbols[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '-', 'x'};

    for (int i = 1; i <= 1000; i++)
    {
        int goal = rand() % 100;
        int numberOfSymbols = (goal >= 10 ? 11 : 12);
        for (int j = 1; j <= numberOfSymbols; j++)
            cout << symbols[rand() % 13];
        cout << '\n';
        cout << goal << '\n';
    }
    
    return 0;
}