549 - Evaluating an Equations Board

All about problems in Volume 5. 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
Sesse
New poster
Posts: 5
Joined: Tue Nov 26, 2002 2:05 am
Contact:

549 - Evaluating an Equations Board

Post by Sesse » Tue Nov 26, 2002 2:09 am

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
New poster
Posts: 5
Joined: Tue Nov 26, 2002 2:05 am
Contact:

Error, please disregard

Post by Sesse » Tue Nov 26, 2002 4:49 am

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

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm

549

Post by oriol78 » Tue Mar 09, 2004 11:41 am

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

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse » Tue Aug 23, 2005 7:33 pm

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
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse » Tue Aug 23, 2005 7:35 pm

did you use recursion?

Sesse
New poster
Posts: 5
Joined: Tue Nov 26, 2002 2:05 am
Contact:

Post by Sesse » Tue Aug 23, 2005 7:54 pm

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
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse » Tue Aug 23, 2005 8:00 pm

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
New poster
Posts: 5
Joined: Tue Nov 26, 2002 2:05 am
Contact:

Post by Sesse » Tue Aug 23, 2005 8:03 pm

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
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse » Tue Aug 23, 2005 8:10 pm

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
New poster
Posts: 5
Joined: Tue Nov 26, 2002 2:05 am
Contact:

Post by Sesse » Tue Aug 23, 2005 8:15 pm

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
New poster
Posts: 9
Joined: Wed Aug 27, 2008 6:50 pm

pls give me critical input for 459 graph connectivity :-?

Post by nayimsust » Sat Sep 12, 2009 4:32 pm

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
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 549: Error in input set?

Post by calicratis19 » Sun Sep 13, 2009 1:06 am

@nayimsust check this input

Code: Select all

1

E
AB
CD
BE
CE

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

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 549 - Evaluating an Equations Board

Post by metaphysis » Thu May 11, 2017 5:04 pm

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
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 549 - Evaluating an Equations Board

Post by metaphysis » Sun Feb 11, 2018 4:11 am

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;
}

Post Reply

Return to “Volume 5 (500-599)”