SRM 569 : Blunder

Having a bad day here because even after a whole week I was still not able to finish the editorial for SRM 568. The first big delay was because of the harder than usual div1 500, but the worst happened later when I got sick... I recovered on Monday and tried to use that time to understand the div1 hard. It is a work in progress.

Then it was SRM time, and I scored another flat zero.

Div1 1000: Mega factorial

This problem was like an evil over the top version of SuperSum, but this time with factorials. And you have to count the number of leading zeros in a very recursive variation of the factorial. Seems mathy. That's probably good because I am tired of those silly div1 1000s in which the solution comes out of nowhere. At least this one will be easy to explain once I find the solution, I think

Div1 500: The one with Jedis

You are given an array of numbers called students that contains the initial number of students in each floor. When assigning Jedis to floors with some students you compute sum( ceiling( students in floor i) / K). However, you can move any students from a floor to either the next or previous one. Let us minimize that sum.

The constraint on the number of floors is low (20). I knew the solution was going to be exponential, making a binary decision for each floor. But no idea how to make that decision.

Some cases I thought of seemed very confusing, like {7,2,7} K=8, it is best to move 1 student to the first floor and another to the third floor. This specific case can be solved by moving 14 students to the middle floor, but there are other variations. It was a bit confusing to my brain.

Div1 250: The one with binary operations.

As my new strategy says, 10 minutes before the end of the match and I have to open the easy problem.

You have a device that takes 2 sequences of bits, and for each bit position in the sequence performs binary AND, OR or XOR between the two bits of the corresponding positions of the input sequences . You already got a number of sequences of bits you can use. What is the minimum number of additional sequences you will need?

Each bit position is a separate problem in reality. If for a bit position all the sequences have bit 0 , you probably will need a sequence with bit 1 in that position. Let us say you know the number of required extra bits for each position. The maximum of them all is the final result : Just make some new sequences with the required bits in total, for the slots that do not need as many new sequences, feel free to repeat some bits.

What is left is this question, that deals with only one bit position: You have z sequences that contain 0 in this position and o sequences that contain 1, what is the number of additional sequences this position needs?

Here is when I made the blunder. I knew that I had to make truth tables for XoR, OR and AND to know what sort of bits are needed to differentiate between the three. But for some stupid reason I decided to rush and make a stupid assumption instead. So I assumed that you need 2 zeros and 2 ones.

That is wrong and fails example cases. Then I made another stupid assumption. That you need two different bits and either one extra 1 or one extra 0. This is also wrong.

Match ended.

This is when I make a truth table in paper:

		AND	OR	XOR
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

And it was so fast and it makes things so clear that I really regret I didn't do it during the coding phase. Note how having two zeros is completely useless, (0,0) cannot help you differentiate between AND, OR, XOR. Having two different bits (0,1) helps you differentiate between OR and AND or between OR and XOR, but cannot help you when differentiating between OR and XOR. 1,1 helps you differentiate between OR and XOR. In conclusion you need at least two sequences with 1 and one with 0.

int minimumAdditional(vector <string> plates)
{
    int need = 0;
    for (int i=0; i<plates[0].size(); i++) {
        int z = 0;
        int o = 0;
        // count the number of sequences with 0 and 1 in this bit position
        for (int j=0; j<plates.size(); j++) {
            z += ( plates[j][i] == '0');
            o += ( plates[j][i] == '1');
        }
        // we need 2 ones and 1 zero:
        int x = 2 - std::min(2, o) + 1 - std::min(1, z) ;
        need = std::max(need, x);
        
    }
    return need;
}