Page 1 of 1

10317 - Equating Equations

Posted: Sat Jul 13, 2002 6:49 pm
by ..
I use DFS to solve 10317, but don't know why I got TLE.

My algorithm for a 16 terms equeation is:
First re-write the formula by putting all the terms to the left of equations.
Then I will have X '+' and Y '-' signs on LHS (X+Y = 16)
I will use DFS to try all C(16, X) combinations of numbers to put them next to '+' (the remain put next to '-'), then check if the sum is 0.

This search will search up to C(16, 8) = 12870 combinations, so it should finish the problem in instant. I tried some 16-terms equeations myself, and the program works fine.

I am really confused what's going on. Please help....Thanks

Posted: Sat Jul 13, 2002 7:25 pm
by gvcormac
I believe that the uva test suite has hundreds of test cases so you have to use a faster algorithm than this. Hint: look for one that takes ]~256) instead of ~65536 operations.

Request to problem adapter: If you are looking for a super-efficient method, please use bigger input or specify the number of test cases. Otherwise its a guessing game to try to figure out what's expected.

Not a super efficient method

Posted: Sun Jul 14, 2002 2:31 am
by shahriar_manzoor
The method is not super efficient. My solution uses around 13000 operations as well. But as there is only +/- operators we can check decisions by odd/even checking (No more explanation please) for some equations and even without attempting to solve. of the 12000 equations in the input 8000 are of these kind :-).

Posted: Sun Jul 14, 2002 8:23 pm
by ..
Thanks shahriar_manzoor, with your hint, I got AC now :D

Posted: Sun Jul 14, 2002 8:49 pm
by gvcormac
I continue to believe that the quality of the contest would be improved if such "guessing game" tricks were avoided.

There should be enough information in the question to determine whether or not you have solved it within the set constraints.

Thanking words!

Posted: Mon Sep 09, 2002 4:56 pm
by uzioriluzan
Thanks to shahriar_manzoor and .. comments.
They helped me solve the problem in less than 2 secs.

As shahriar_manzoor intended, if there is an odd number of odd numbers, there will be no solution.
The other cases, a combination of all possibilities will do, as .. said.

Regards!

10317 WA..please help me..^^

Posted: Tue Oct 07, 2003 8:05 am
by rascle
Could anyone give me some test data, please...

My method is

1. Move the minus operand to the opposite side, and memorize the
locations of all operators in each side.

2. Count the summation of each side, and count the abs(sum1-sum2).
If
abs(sum1 - sum2 ) is odd, then "no solution"
ELSE
try to find an element in left side to swap with an element in
the right side that can decrease abs(sum1-sum2)...
keep doing until abs(sum1-sum2) == 0

10317 - solution which is better than Shahriar's :-)

Posted: Fri Oct 10, 2003 1:04 am
by Dmytro Chernysh
I finally did it !!!
I solved 10317 !!! And by the way, with better time than the author - Shahriar Manzoor :-)

Many thanks to LittleJohn Yo(rank 3) for providing me an input/output.

As you can see, everything is possible :-) :-) :-)

P.S. As I read earlier, it's possible to solve a problem in 256 steps instead of 65520. How?

Posted: Fri Oct 10, 2003 6:50 pm
by Dmytro Chernysh
I can give you my input/output.
Mail me.

Posted: Tue Oct 14, 2003 7:15 am
by rascle
thank you, Dmytro_Chernysh..

But my method doesn't work in such case:

input :
8 + 97 + 100 = 6 + 4 + 97 + 100

abs(205 - 207) = 2

Can't find swaping elements that resulting in decreasing abs(sum1-sum2),
so output "no solution".

But there exists one solution like:

6 + 100 + 100 = 8 + 4 + 97 + 97

abs(206 - 206) = 0

Re: Thanking words!

Posted: Tue Nov 27, 2007 10:24 pm
by adelar
Hi friends,
uzioriluzan wrote: As shahriar_manzoor intended, if there is an odd number of odd numbers, there will be no solution.
The other cases, a combination of all possibilities will do, as .. said.
this work in this problem?

thanks in advance

Re: 10317 - Equating Equations

Posted: Sat Aug 31, 2013 12:38 pm
by audition2014
Can anyone give some input/output? It gets WA

Re: 10317 - Equating Equations

Posted: Tue Jul 19, 2016 6:12 am
by red_apricot
I'm getting WA with a seemingly correct code:

Code: Select all

/*
 * 10317. Equating Equations
 * TOPIC: recursion
 * status: TLE
 */
import java.io.*;
import java.util.*;
import java.util.regex.*;

class Main {

	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	Pattern p = Pattern.compile("(\\d+)");
	char []op;
	int m,n,pluses;
	int []x,z = new int[0x20],sum = new int[1<<16];

	static int []who = new int[1<<17];
	static int L( int k ) { return k & (~(k)+1); }
	static int BIT( int k ) { return (1<<k); }
	static char[]R = new char[0x200];
	static int MASK( int k ) { return BIT(k)-1; }
	static int []bts = new int[1<<21];

	public static void main( String ... args ) throws Exception {
		int i;
		for ( i = 0; i < 17; who[BIT(i)] = i, ++i );
		for ( i = 0; i < (1<<21); ++i )
			bts[i] = bts[i>>1]+(i&1);
		R[R['+'] = '-'] = '+';
		new Main().go();
	}

	boolean oddEvenTest() {
		int parity = 0,i;
		for ( i = 0; i < n; ++i ) 
			parity += (Math.abs(x[i])%2);
		return (parity%2) == 0;
	}

	boolean f( int k, int s, int used ) throws Exception {
		int i,u;
		if ( k == n ) {
			if ( s == 0 ) {
				for ( bw.write(z[0]+""), i = 1; i < m; bw.write(" "+op[i]+" "), bw.write(z[i++]+"") );
				bw.write(" = ");
				for ( bw.write(z[i++]+""); i < n; bw.write(" "+R[op[i]]+" "), bw.write(z[i++]+"") );
				bw.write("\n");
				return true ;
			}
			return false ;
		}
		if ( s > sum[(~used)&MASK(n)] ) return false ;
		if ( s < -sum[(~used)&MASK(n)] ) return false ;
		for ( u = (~used)&MASK(n); u > 0; u &= ~L(u) ) {
			z[k] = x[i = who[L(u)]];
			if ( f(k+1,s+(op[k]=='+'?z[k]:-z[k]),used|BIT(i)) )
				return true ;
		}
		return false ;
	}

	boolean g() throws Exception {
		int u,v,i,s = 0,P = 0, M = 0,k,l;
		int []pl = new int[pluses], mn = new int[n-pluses];
		for ( u = 0; u < (1<<n); ++u ) 
			if ( bts[u] == pluses ) {
				s = P = M = 0;
				for ( i = 0; i < n; ++i )
					if ( ((u>>i)&1) == 1 ) {
						s += x[i];
						pl[P++] = x[i];
					}
					else {
						s -= x[i];
						mn[M++] = x[i];
					}
				if ( s == 0 ) {
					k = l = 0;
					for ( i = 0; i < m; ++i )
						if ( op[i] == '+' ) {
							if ( i == 0 ) {
								bw.write(pl[k++]+"");
								continue ;
							}
							bw.write(" + ");
							bw.write(pl[k++]+"");
						}
						else {
							bw.write(" - ");
							bw.write(mn[l++]+"");
						}
					assert op[i] == '-';
					bw.write(" = ");
					for ( ;i < n; ++i ) {
						if ( op[i] == '+' ) {
							bw.write(" - ");
							bw.write(pl[k++]+"");
						}
						else {
							if ( i == m ) {
								bw.write(mn[l++]+"");
								continue ;
							}
							bw.write(" + ");
							bw.write(mn[l++]+"");
						}
					}
					bw.write("\n");
					return true ;
				}
			}
		return false ;
	}

	void go() throws Exception {

		String s;
		StringTokenizer st;
		int i,j,k;
		Map<Integer,List<Character>> operations;
		List<Integer> numbers;

		for ( ;(s=br.readLine())!=null; ) {
			st = new StringTokenizer(s);
			operations = new HashMap<Integer,List<Character>>();
			numbers = new ArrayList<Integer>();
			for ( i = 0; i < 2; operations.put(i++,new ArrayList<Character>()) );
			for ( k = 0; st.hasMoreTokens(); ) {
				String tmp = st.nextToken();
				switch ( tmp ) {
					case "=": ++k; break ;
					case "-": operations.get(k).add(tmp.charAt(0)); break;
					case "+": operations.get(k).add(tmp.charAt(0)); break;
					default: numbers.add(Integer.parseInt(tmp)); break ;
				}
			}
			op = new char[operations.get(0).size()+operations.get(1).size()+2];
			m = operations.get(0).size()+1;
			i = 0; op[i++] = '+';
			for ( Character c: operations.get(0) )
				op[i++] = c;
			op[i++] = '-';
			for ( Character c: operations.get(1) )
				if ( c == '-' )
					op[i++] = '+';
				else {
					assert c == '+';
					op[i++] = '-';
				}
			n = numbers.size();
			for ( pluses = 0, i = 0; i < n; ++i )
				if ( op[i] == '+' )
					++pluses;
			assert op.length == n;
			x = new int[numbers.size()];
			i = 0;
			for ( int a: numbers ) 
				x[i++] = a;
			if ( !oddEvenTest() || !g() ) 
				bw.write("no solution\n");
		}
		bw.flush();
	}
};

What's wrong with this code?

Re: 10317 - Equating Equations

Posted: Wed Oct 05, 2016 5:17 am
by jack7737
I think the testcase has some mistakes since no one gets AC recently