Codeforces 282B Painting Eggs Solution & Explanation

Difficulty : 1500

Problem Description

The Bitlandians are quite weird people. They have very peculiar customs.

As is customary, Uncle J. wants to have n eggs painted for Bitruz (an ancient Bitland festival). He has asked G. and A. to do the work.

The kids are excited because just as is customary, they’re going to be paid for the job!

Overall uncle J. has got n eggs. G. named his price for painting each egg. Similarly, A. named his price for painting each egg. It turns out that for each egg the sum of the money both A. and G. want for the painting equals 1000.

Uncle J. wants to distribute the eggs between the children so as to give each egg to exactly one child. Also, Uncle J. wants the total money paid to A. to be different from the total money paid to G. by no more than 500.

Help Uncle J. Find the required distribution of eggs or otherwise say that distributing the eggs in the required manner is impossible.

Input

The first line contains integer n (1 ≤ n ≤ 10⁶) — the number of eggs.

Next n lines contain two integers a_i and g_i each (0 ≤ a_i, g_i ≤ 1000; a_i + g_i = 1000): a_i is the price said by A. for the i-th egg and g_i is the price said by G. for the i-th egg.

Output

If it is impossible to assign the painting, print “-1” (without quotes).

Otherwise print a string, consisting of n letters “G” and “A”. The i-th letter of this string should represent the child who will get the i-th egg in the required distribution. Letter “A” represents A. and letter “G” represents G. If we denote the money Uncle J. must pay A. for the painting as S_a, and the money Uncle J. must pay G. for the painting as S_g, then this inequality must hold: |S_a  -  S_g|  ≤  500.

If there are several solutions, you are allowed to print any of them.

Examples

Solution

C# Solution

In my solution,

• Start looping through each egg.
• For each egg, read the prices named by G. and A. from the input.
• Calculate two possible total prices, tmp1 and tmp2:
  • tmp1 = sum + a, representing the total price if the egg is given to A.
  • tmp2 = sum – g, representing the total price if the egg is given to G.
• Choose the one with a smaller absolute value between tmp1 and tmp2 to minimize the difference in total prices between A. and G., i.e., |sum|.
• Update sum with the chosen total price, and mark the selected child (A. or G.) as the recipient of the egg.
• Repeat this process until all eggs are assigned.
• Finally, check if the absolute value of sum exceeds 500. If yes, it means Uncle J.’s conditions cannot be satisfied, so output “-1”. Otherwise, output the final distribution of eggs.

First try – Time limit exceeded 

int n = int.Parse(Console.ReadLine());  //number of eggs 

int sum = 0;
string res = "";

for(int i=0; i<n;i++){
    string[] arr = Console.ReadLine().Split(' '); //split by space
    int a = int.Parse(arr[0]);
    int g = int.Parse(arr[1]);
    
    int tmp1 = sum+a;
    int tmp2 = sum-g;
    
    if(Math.Abs(tmp1)<Math.Abs(tmp2)){
        res+="A";
        sum = tmp1;
    }
    else{
        res+="G";
        sum = tmp2;
    }
}

if(Math.Abs(sum)>500){
    Console.WriteLine("-1");
}
else
{
    Console.WriteLine(res);
}

The overall logic is correct, but the issue of running for an extended period has arisen.

So, we’ll make some improvements in our next solution.

• Firstly, given that the sum of  a_i and g_i always equals 1000, we can replace the line int g = int.Parse(arr[1]); with int g = 1000 – a;.
• Secondly, in a loop where string concatenation (+=) is used extensively, it incurs a significant time cost due to copying at each iteration. To address this, we can optimize the process by using a char array instead.

Solution1

int n = int.Parse(Console.ReadLine());  //number of eggs 

int sum = 0;
string res = "";
char[] resArr = new char[n];

for(int i=0; i<n;i++){
    string[] arr = Console.ReadLine().Split(' '); //split by space
    int a = int.Parse(arr[0]);
    //int g = int.Parse(arr[1]);
    int g = 1000 - a;
    
    int tmp1 = sum+a;
    int tmp2 = sum-g;
    
    if(Math.Abs(tmp1)<Math.Abs(tmp2)){
        //res+="A";
        resArr[i] = 'A';
        sum = tmp1;
    }
    else{
        //res+="G";
        resArr[i] = 'G';
        sum = tmp2;
    }
}

if(sum>500 || sum<-500){
    Console.WriteLine("-1");
}
else
{
    //Console.WriteLine(res);
    Console.WriteLine(new string(resArr));
}

And then the solution passed the time constraints! Congratulations!

Java Solution

Solution1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        
        int sum = 0;
        String res = "";
        char[] resArr = new char[n];
        
        for(int i=0; i<n;i++){
            String[]arr = scanner.nextLine().split(" "); // split by space
            int a = Integer.parseInt(arr[0]);
            int g = 1000 - a;
            
            int tmp1 = sum+a;
            int tmp2 = sum-g;
            
            if(Math.abs(tmp1)<Math.abs(tmp2)){
                resArr[i] = 'A';
                sum = tmp1;
            }
            else{
                resArr[i] = 'G';
                sum = tmp2;
            }
        }
        
        if(sum>500 || sum<-500){
            System.out.println("-1");
        }
        else
        {
            System.out.println(new String(resArr));
        }

    }
}

Conclusion

This is the second problem from codeforces contest – Dashboard – Codeforces Round 173 (Div. 2) – Codeforces

You can find the solution for the first problem here – Codeforces 282A Bit++ Solution & Explanation

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks you~~

✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know !!

The problem link : Problem – 282B – Codeforces

Random Codeforces Posts