COOK115 - Brief Editorials

editorial
, ,
1

Hope you guys had an awesome contest :slight_smile:
Before the official editorials are posted (might take a couple of more days), here are brief editorials to the problems-

PSHOT

The result of the shoot-out can be known as soon as one of the teams has a score which is greater than - the score of the other team + the number of shots remaining for the other team. This is because the other team won’t be able to catch up with the former team even if it manages to score in all its remaining turns and the former team misses in all its remaining turns.
If all turns are over without a clear winner, it will be a draw. We can only know be sure of a draw after all 2N shots have been taken.

Pseudo-code 
scoreA = scoreB = 0 //current scores
leftA = leftB = N  //shots remaining

for(shot = 1; shot <= 2*N; shot++)
{
    if(shot%2 = = 1) //this was A's turn
    {
        scoreA + = resultOf[shot]; 
        leftA - -;
    }
    else //this was B's turn
    {
        scoreB + = resultOf[shot]; 
        leftB - -;
    }

    // Can we be sure of the result now?
    if((scoreA>scoreB+leftB) OR (scoreB>scoreA+leftA) OR (scoreA==scoreB&&shot==2N))
        break;
}

print(shot);

XORGM

In the solution permutation C, all (A_1 \oplus C_1) = (A_2 \oplus C_2) = (A_3 \oplus C_3) = \ldots = (A_N \oplus C_N).

Let (A_1 \oplus C_1) = x.
As (A_1 \oplus C_1) = (A_2 \oplus C_2),
\implies(A_2 \oplus C_2) = x.
\implies (A_1 \oplus C_1) \oplus (A_2 \oplus C_2) = (x \oplus x) = 0
\implies (A_1 \oplus C_1) \oplus (A_2 \oplus C_2) \oplus (A_3 \oplus C_3) = (x \oplus x \oplus x) = x

As N is odd,
\implies (A_1 \oplus C_1) \oplus (A_2 \oplus C_2) \oplus (A_3 \oplus C_3) \oplus \dots \oplus (A_N \oplus C_N) = x

The sequence (A_1 \oplus C_1) \oplus (A_2 \oplus C_2) \oplus (A_3 \oplus C_3) \oplus \dots \oplus (A_N \oplus C_N) is nothing but the xor of all values of A and B (C will just be a permutation of B). Thus, after xor-ring all values of A and B, we shall get x.

If we xor x with A_1, we’ll get C_1. Similarly, we can get C_2, C_3, C_4, \ldots C_N by xor-ring the corresponding elements of A with x.

Now, we just need to check if we can obtain this C from B, i.e. , if we can re-arrange the elements of B in some way to get C. There are multiple ways to do this. One way is to compare the frequencies of corresponding elements in these arrays.

If this C is indeed a permutation of B, we have found a solution. We can output C. Else, it is not possible to reorder B to satisfy the given equation and the answer is -1.

CYCLSUM

Refer to this to learn how to find the maximum sum subarray.
The maximum sum prefix of an array is some prefix ending before, say, i, such that the sum of this prefix is greater than the sum of other prefixes of this array. We can define the maximum sum suffix of an array in a similar way.

Let us visualise the rotations in a particular way:
After i rotations, the sequence will be A_i, A_{i+1}, A_{i+2}, \ldots A_N, A_1, A_2, A_3 \ldots A_{i-1}.
Imagine the array has now been cut into two parts,
Part 1: A_i, A_{i+1}, A_{i+2}, \ldots A_N, and
Part 2: A_1, A_2, A_3 \ldots A_{i-1}.

Now, the maximum sum subarray can be either:

  1. In Part 1, or
  2. In Part 2, or
  3. The subarray obtained by joining some suffix of Part 1 with some prefix of Part 2.

This ‘some’ suffix and prefix will actually be the maximum sum suffix of Part 1 and maximum sum prefix of Part 2.

Thus, after a particular rotation, if we know the value of the maximum sum subarray in Part 1, the maximum sum subarray in Part 2, and the values of maximum sum suffix from Part 1 and maximum sum prefix from Part 2, we can compare these and print the maximum among these as the answer for this rotation.

The above values can be obtained for every rotation by extending their previous values (refer to implementations). Thus, we can find the answer for every rotation.

SLAB

This is a pretty straightforward problem. The tax bracket can be found using if/switch, and then the tax can be calculated, as explained in the problem sample case explanations. Once tax is calculated, it can be subtracted from the income, to get the net income. As N is a multiple of 100, using integer data types, instead of floating-point data types, works too. (Refer to solutions).

8 Likes
2

I have implemented your logic in the question XORGM.
here is my Code:

#include<iostream>
#include<unordered_map>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--)
	{
		long n;
		cin>>n;
		int arr[n],brr[n];
		unordered_map<long,int> mp;
		long x=0,f=0;
		for(int i=0;i<n;i++)
			{cin>>arr[i];x=(x^arr[i]);}
		for(int i=0;i<n;i++)
			{cin>>brr[i];mp[brr[i]]++;x=(x^brr[i]);}
		for(int i=0;i<n;i++)
		{
			if(mp.find(x^arr[i])!=mp.end()&&mp[x^arr[i]]>0){
            	continue;
            }
            else {
            	f=1;
            	break;
            }
		}
		if(f==1)
			cout<<"-1"<<endl;
		else for(int i=0;i<n;i++) cout<<(arr[i]^x)<<" ";
		cout<<endl;

	}
}
3

while taking input in brr array …you are xor-ring with arr[i] instead of brr[i]

2 Likes
4

https://www.codechef.com/viewsolution/29780451
i implemented the same logic and got AC

5

It was a silly mistake , thanks for pointing it out , now my submission is accepted.

2 Likes
6

Anyone with editorials of PEPPERA ? @taran_1407

8

PEPPERA editorial will be posted tomorrow. Thanks for your patience :slight_smile:
The main topic it involves is knapsack DP.

1 Like
9

Please include the editorial for CHEFDIV also.

11

@admin @akashbhalotia how many more days will it take to release the editorials??

12

All will be ready by tomorrow. Some are ready, but can’t be moved to public discuss yet, so not sure how much time it will take.
If you want, I can email you the editorials you require, by tomorrow. Just send me a mail at akashbhalotia.unofficial@gmail.com, and tell me the ones you require.

13

hopefully this help in solving the xorgame problem

https://www.codechef.com/viewsolution/29885933

14

@admin @akashbhalotia are we getting the editorials or not ?? please answer

15

Where is PEPPERA Editorial ?

16

@admin when can we expect that the editorials of contest are released on time?

17

I even mailed @akashbhalotia asking for unofficial editorials few days back but no response uptill now

18

Let A_i be number of pepperoni on left half of ith row and B_i be number of pepperoni on right half of ith row.

Now, From each row, we either select A_i pepperoni, or B_i pepperoni. Let F(i, X) denote whether considering first i rows, can we can get exactly X pepperoni on left side? We can see, if F(i-1, X) is true, then we have F(i, X+A_i) and F(i, X+B_i) true.

Above is just knapsack DP. Then choose number of pepperoni on left side which minimizes differences, and then backtrack to find whether we chose A_i or B_i at each step and reversing rows accordingly.

2 Likes