LPSS - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Alice has X copies of A, Y copies of B, Z copies of C.
She’ll create a string using all of them, in some order.
Then, Bob will delete all occurrences of exactly one of the characters.
Alice’s score is the length of the longest palindromic subsequence of the string.

Alice wants to maximize her score, Bob wants to minimize it.
Find Alice’s score if both play optimally.

EXPLANATION:

Bob deletes one type of character entirely, so in the ideal situation Alice will be able to use all the remaining characters to form a palindrome.

This isn’t always possible, of course: for example, suppose Bob deletes all C's.
If there’s one A and one B left after deletion (so the string is either AB or BA), both characters can’t be part of the palindrome.
However, it’s possible to get pretty close: in particular, Alice can ensure that all but one of the remaining characters will form a palindromic subsequence.

To see how, once again suppose Bob deletes all the C's.
There are X occurrences of A and Y occurrences of B. Now,

  • If X and Y are both even, Alice could’ve arranged the string as
    AAA\ldots ABBB\ldots BBB\ldots AAA
    That is, start with \frac{X}{2} occurrences of A, then all the B's, then again \frac{X}{2} occurrences of A.
    This makes everything a palindrome.
  • if X is odd and Y is even, do the same thing, but stick the extra A in the center instead. That is,
    AAA\ldots ABBB\ldots B\underline{A}B\ldots BBB\ldots AAA
    Here, there are \frac{Y}{2} occurrences of B on either side of the central A.
  • If Y is odd and X is even, the situation is clearly symmetric.
  • If both are odd, then one character must be left out (since a palindrome can’t have two characters with odd frequency).
    Choose any one to leave out, and then it goes back to a previous case.

Now, of course Alice doesn’t know if Bob is going to delete C or not; and she can’t rearrange characters after his deletion.
However, it’s not hard to see that the above construction can be extended to work for all three characters, no matter which one is deleted.
In short, do the following:

AA\ldots AABB\ldots BBCC\ldots CC \ \ [ABC] \ \ CC\ldots CCBB\ldots BBAA\ldots AA

That is, place half the A's, then half the B's, then half the C's.
After that, if any of A/B/C have odd frequency, place the “extra” character(s) in the middle. These are represented by the square braces in the middle.
Then, place the remaining half of the C's, then the B's, then finally the A's.

For example, if X = 2, Y = 3, Z = 5 the resulting string will be

ABCC\ \ [BC] \ \ CCBA

It’s easy to see that no matter which character Bob deletes now, the remaining characters will all be used to form a palindrome (except one central character, if and only if both frequencies are odd).

In the above example,

  • Deleting A results in BCCBCCCB where the longest palindromic subsequence has length 7: this is as expected since B and C both have odd frequency, so one character has to be left out.
  • Deleting B results in ACCCCCA, a palindrome itself.
  • Deleting C results in ABBBA, also a palindrome.

Now that Alice’s string is known, Bob will of course delete whichever character results in the minimum final score.
There are only three options for him, try all three and take the minimum.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    x, y, z = map(int, input().split())
    
    v1 = x + y - (x%2)*(y%2) # deleting c
    v2 = x + z - (x%2)*(z%2) # deleting b
    v3 = z + y - (z%2)*(y%2) # deleting a
    print(min(v1, v2, v3))
2

when will you stop giving these non sense puzzles in an algorithmic contest.

1 Like
3

Spent 1 hour and not once did it cross “AB” is not palindromic.

4

Alice’s final score is defined as the length of the longest palindromic subsequence, but the output expected is the length of palindrome somehow. Why is there such an anomaly?

5

brother it was good problem, and it’s really hard to come up good 7-8 problem each Wednesday.

6

They have been setting 7-8 problems each week from a very long time, earlier their used to be good problems on binary search, bit manipulation, prefix sums, STL and other relevant stuff. I like constructive problems but these puzzles are just useless and just look how imbalanced is the difficulty level of contests.

7

Bro I have written a code that fulfills all the constraints but hidden test cases are failing , what should i do? The below is my code:

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
    public static void main(String[] args) throws java.lang.Exception
    {
        // your code goes here
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t > 0) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            //System.out.println(x+" "+y+" "+z);
            if (x == 0 && y == 0 || y == 0 && z == 0 || z == 0 && x == 0) {
                System.out.println(0);

            }

            else if (x == z && z == y) {
                if (x % 2 == 0) {

                    System.out.println(x * 2);
                }
                else {
                    System.out.println((x*2)-1);
                }

            }
            else {
                int max = Math.max(x, Math.max(y, z));
                //System.out.println("max: "+max);
                int a = 0, b = 0;

                if (max == x) {
                    a = y;
                    b = z;
                }
                else if (max == y) {
                    a = x;
                    b = z;

                }
                else {
                    a = x;
                    b = y;
                }

                if (a != b) {
                    if (a % 2 != 0 && b % 2 == 0 || a % 2 == 0 && b % 2 != 0) {
                        System.out.println(a + b);
                    }
                    else if (a % 2 != 0 && b % 2 != 0) {
                        System.out.println(a + b - 1);
                    }
                }
                else if (a == b) {
                    if (a % 2 != 0) {
                        System.out.println(a + b - 1);
                    }
                    else {
                        System.out.println(a + b);
                    }


                }


            }
            t--;
        }

    }
}