10317 - Equating Equations

[..]

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

[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.

[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 .

[..]

Thanks shahriar_manzoor, with your hint, I got AC now

[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.

[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!

[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

[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?

[Dmytro Chernysh]

I can give you my input/output.
Mail me.

[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

[adelar]

Hi friends,

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

[audition2014]

Can anyone give some input/output? It gets WA

[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?

[jack7737]

I think the testcase has some mistakes since no one gets AC recently