Code Chef january challenge unofficial editorial for first 5 problems

Rectangle:

This is the easiest problem of the contest. Opposite sides of a rectangle are equal. So use this property to see if there are 2 pairs of equal sides.

//inside int main()
int t;
cin >> t;
while(t--){
    int a[4];
    for(int i = 0 ; i < 4 ; i++)cin >> a[i];
    sort(a,a + 4);
    if(a[0] == a[1] and a[2] == a[3])
        cout << "YES\n";
    else 
        cout << "NO\n";
}

---

Maximum Score:

Start solving the problem from last list instead of first list, because in order to get the maximum sum we must select the maximum element from the last list. Obviously sorting makes the task easier. So sort all the lists and let our variable ans be 0 initially. First select the maximum value from last list and store it in a variable(say last) and add it to ans, then find the maximum value from second last list which is less than last, let it be val and then set last = val and add val to the ans. Similarly do for other lists. Finally ans will be our final answer.
Complexity : 
using sorting: O(n*n*log(n)) per test-case
without sorting: O(n*n) per test-case

Link to my solution

---

K-Concatenation:

Pre-requisites: Kadane's Algorithm or maximum sum sub-array problem.

Let a be the given array of n elements and k is the number of arrays. 

Let sum be the sum of elements of array a[n].

There are 3 cases:

ans1 = maximum sum sub-array from array a[] and ignoring all the (k-1) arrays.

ans2 = max_suffix_sum_of_a + (k-2)*sum+ max_prefix_sum_of_a.

ans3 = maximum sum sub-array from joining array a[] 2 times.
Final answer will be equal to maximum of ans1, ans2, and ans3.
Don't forget to make a different case when k = 1, because ans2 and ans3 are not valid when k = 1.

Complexity: O(n) per test-case
Link to my solution in C++

---

String Merging:

Pre-requisites: Longest common sub-sequence
We know that our answer counts only when there are 2 unequal characters. So first of all get rid of continuous equal characters by replacing them with a single occurrence because they are not going to add anything to the answer. Eg. If string s = "piikkkaachhu" then make s = "pikachu". So after shortening both the given strings a and b, we can see that, we can merge them in such a way that the characters of their longest common sub-sequence collides, so that most of the characters can be made continuous in the merged string and final answer can be minimized.
Let n be the length of shortened a string.
Let m be the length of shortened b string.
Then our final answer will be n + m - lcs(a,b), where lcs(string1, string2) returns the length of lcs of string1 and string2.
Complexiy: O(n*m) per case
Link to my solution in C++  

---

Partition the numbers:

Observations:

Sum of first n natural numbers, sum = (n*(n+1)) / 2.

Let's remove x(1<=x<=n) from sequence. So, sum = (n*(n+1)) / 2 - x.

Now if sum is odd, we can never divide the remaining numbers into 2 sets.

When n = 2 or n = 3, answer is "impossible", no matter what is the value of x.

Approach:

We need to find if sum/2 can be formed from the remaining numbers. If yes! then what are those numbers which sums to sum/2.

Let req = sum/2

Make an array color[n] to represent the partitions.

Color 0 represents the first partition and Color 1 represents another partition and Color 2 represents the x.

Initially color all numbers with color 0. It means all numbers are initially in partition 1.

It's obvious that req is always greater then n.

So, start a loop, counter i from n to 1 and if color[i] == 0, subtract i from req and change color[i] to 1. Break the loop once you get that after next addition req will be < 0. 

So now we have 2 cases:
Case 1:

if(color[req] == 0){
    color[req] = 1;
    return;
}

Case 2:
Now if(color[req] != 0)  we need to make req from addition of some numbers which are in first partition(i.e. having color[i] = 0).

We can make req in 2 ways from given numbers:

Way 1:

Eg:  1, 2, 3, 4, 5. How can you make 6 from these numbers(1 to (6-1 = 5)).

1 + 4 = 2 + 4. So yep, we have 2 ways to make 6(see the pattern: one number from start and one number from end).

Similarly req can be formed from one of the combinations(1 to (req-1)).

Conditions: color[first] = 0 and color[second] = 0 and first < second, where first and second are the first and second numbers respectively.

If you find a combination make color[first]=1 and color[second]=1, and then return
Way 2:
Eg:  6, 7, 8, 9, 10, 11, 12........
Let 12 be already in second partition(color[12] = 1 and is the last element from last which has color = 1), and we need to make req = 6 from numbers greater than 6. What rubbish? xD. Yep we can!🤘, by the following steps.
Now remove 12 from second partition and add it in first partition and add 12 to req.
Now req = 12+6 = 18. Now, How can you make 18 from numbers from 7 to 11 (lets say color[7] =  ...  = color[11] = 0)?
7 + 11 = 8 + 10 = 18. Now we have 2 ways.(Again! observe the pattern.)
In this way find the 2 numbers whose sum equals req and color them with 1 finally.
Finally after coloring all the numbers, check if the really are divided into partitions. If yes then print the colors, else print "impossible".
Complexity: Linear per case
Link to my solution in C++

Thank you !
Keep coding!

PS: If you find anything wrong in the post, please feel free to mention it in comment section.