10317 - Equating Equations

All about problems in Volume 103. 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
..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

10317 - Equating Equations

Post by .. » Sat Jul 13, 2002 6:49 pm

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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Sat Jul 13, 2002 7:25 pm

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Not a super efficient method

Post by shahriar_manzoor » Sun Jul 14, 2002 2:31 am

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 :-).

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sun Jul 14, 2002 8:23 pm

Thanks shahriar_manzoor, with your hint, I got AC now :D

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Sun Jul 14, 2002 8:49 pm

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
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am

Thanking words!

Post by uzioriluzan » Mon Sep 09, 2002 4:56 pm

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
New poster
Posts: 20
Joined: Wed Mar 06, 2002 2:00 am

10317 WA..please help me..^^

Post by rascle » Tue Oct 07, 2003 8:05 am

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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

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

Post by Dmytro Chernysh » Fri Oct 10, 2003 1:04 am

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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Fri Oct 10, 2003 6:50 pm

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

rascle
New poster
Posts: 20
Joined: Wed Mar 06, 2002 2:00 am

Post by rascle » Tue Oct 14, 2003 7:15 am

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
New poster
Posts: 35
Joined: Wed May 02, 2007 11:48 pm
Location: Brasil

Re: Thanking words!

Post by adelar » Tue Nov 27, 2007 10:24 pm

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

audition2014
New poster
Posts: 1
Joined: Sat Aug 31, 2013 12:18 pm

Re: 10317 - Equating Equations

Post by audition2014 » Sat Aug 31, 2013 12:38 pm

Can anyone give some input/output? It gets WA

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 10317 - Equating Equations

Post by red_apricot » Tue Jul 19, 2016 6:12 am

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
New poster
Posts: 1
Joined: Thu Jun 11, 2015 10:25 pm

Re: 10317 - Equating Equations

Post by jack7737 » Wed Oct 05, 2016 5:17 am

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

Post Reply

Return to “Volume 103 (10300-10399)”