CPMagical CP Library

Problem solution · Java

CCC 1998 P4 - Lottery

CCC 1998 P4 - Lottery: a Java solution using sliding window or two pointers. Learn the idea, check the complexity, and read the full code, with credit to CCCSolutions.

Technique
Sliding window or two pointers
Source
CCCSolutions
Length
143 lines
Start with the idea.

Try the problem first. If you get stuck, read the approach below, then write your own solution. The full code is at the bottom.

Approach

Sliding window or two pointers

For CCC 1998 P4 - Lottery, the implementation maintains a moving interval and updates only the information that enters or leaves the window.

  1. Choose the invariant that makes a window valid or useful.
  2. Advance the right boundary and add the new element.
  3. Move the left boundary only as needed while maintaining the invariant and updating the answer.

Code notes

  • 143 lines of Java from the credited upstream file ccc98s4.java.
  • The implementation visibly relies on sequence storage.
  • 9 loop blocks detected.

Complexity

Confirm that neither pointer moves backwards; if so, the scan is usually linear apart from the window’s data-structure operations.

Check the problem constraints before deciding whether this complexity will pass.

Source

Code and credit

This code comes from CCCSolutions by CCCSolutions contributors · Milliken Mills High School and is used under the MIT licence.

Open problem ↗Original source ↗
Full codeCCC 1998 P4 - Lottery · JavaJava
Use this to learn the idea, then write your own version.
// CCC// 1998: Problem D Lottery//// Add () according to bedmas in expression involving X, +, - only// Example: "123 + 456 X 789 - 876" becomes "(123 + (456 X 789)) - 876"//// Ugly, no tricks. Find the operator, then find the operand to left// and right (which may be a number or a bracketed expression)// and add the '(' or ')'//// file input consists of the number of expressions// followed by the expressions themselves import java.awt.*;import hsa.*; public class P4Lottery{    static Console c;     public static void main (String [] args)    {	c = new Console (); 	TextInputFile fi = new TextInputFile ("lottery.in");	TextOutputFile fo = new TextOutputFile ("lottery.out");	int n, x;	String s; 	n = fi.readInt ();	for (int i = 1 ; i <= n ; i++)	{	    s = fi.readLine (); 	    // find each 'X' and bracket it	    x = 0;	    while (x < s.length ())	    {		while (x < s.length () && s.charAt (x) != 'X')		    x++;		if (x < s.length ())		{		    s = left (s, x);		    s = right (s, x + 1);		}		x = x + 2;    // 1 for the '(' and 1 to move	    } 	    // find each '+' or '-' and bracket those	    x = 0;	    while (x < s.length ())	    {		while (x < s.length () && !(s.charAt (x) == '+' || s.charAt (x) == '-'))		    x++;		if (x < s.length ())		{		    s = left (s, x);		    s = right (s, x + 1);		}		x = x + 2;   // 1 for the '(' and 1 to move	    }	    c.println (s.substring (1, s.length () - 1));	    c.println ("");	    fo.println (s.substring (1, s.length () - 1));	    fo.println ("");	}	fi.close ();	fo.close ();    }      // puts in the '(' to the left    // given a string and the place of the operator    // back off 2 places    //     if a ')', find the matching '('    //     else find a space (or beginning of string)    // add in the '('    // return the string so it can be updated in main.    public static String left (String s, int x)    {	x = x - 2;	if (s.charAt (x) == ')')	{	    int count = 1;	    x--;	    while (count != 0)	    {		if (s.charAt (x) == ')')		    count++;		else if (s.charAt (x) == '(')		    count--;		x--;	    }	}	else	{	    while (x >= 0 && s.charAt (x) != ' ')		x--;	}	if (x == -1)	    s = "(" + s;	else	    s = s.substring (0, x + 1) + "(" + s.substring (x + 1);	return s;    }      // puts in the ')' to the right    // given a string and the place of the operator    // go ahead 2 places    //     if a '(', find the matching ')'    //     else find a space (or end of string)    // add in the ')'    // return the string so it can be updated in main.    public static String right (String s, int x)    {	x = x + 2;	if (s.charAt (x) == '(')	{	    int count = 1;	    x++;	    while (count != 0)	    {		if (s.charAt (x) == '(')		    count++;		else if (s.charAt (x) == ')')		    count--;		x++;	    }	}	else	{	    while (x < s.length () && s.charAt (x) != ' ')		x++;	}	if (x == s.length ())	    s = s + ")";	else	    s = s.substring (0, x) + ")" + s.substring (x);	return s;    }}

Keep practising

Did this explanation save you time? I'm a Grade 11 student building this free library to make difficult algorithms easier to understand.

Buy me a coffee ↗