Unofficial Editorials February Lunchtime

Hello Guys, I’m back with another set of editorials in hope you would like them. :slight_smile:

I had performed badly in February Cook Off and wasn’t in a good mood, that’s the reason of no editorials for Cook Off this time.

Without wasting much time, Here are the editorials.

#Jumping in the hills

Difficulty: Cakewalk

Problem:

Given the heights of hills and U and D (and one parachute too), determine how far we can move, if we cannot climb more than U units in a single jump, nor fall more than D units (unless using a parachute).

Solution:

Simplest solution is to simulate the whole process.

  1. If next hill has height same as current hill, Just jump.
  2. If next hill has height greater than current hill height+U, terminate, else jump.
  3. If next hill has height smaller than current hill, but is within D units, jump.
  4. If next hill has height smaller than current hill-D, jump using parachute if available, else terminate.

That’s all guys. Just keep updating index and print the answer.

Link to my


[2].

#[Game with numbers][3]

#### Difficulty:Easy-Medium

### Problem:

We are to simulate the game between Chef and his brother, game is as follows.       
Staring with a number of cards A[i] occuring D[i] times, chef and his brother takes turns to remove B[i] cards.
Aim of Chef is to maximize sum of remaining cards while that of his brother is to minimize sum.

We have to answer final sum after K turns.

### Solution:

Firstly,Sort all tuple(Ai, Di) with on basis of Ai.

Now, we need to determine, **given a set of cards**, which cards will be **removed by chef** and which cards will be **removed by his brother**.

To maximize sum of remaining cards, Chef will remove cards with minimum value, while his brother, to minimize sum of remaining cards, will remove cards with maximum value.

This way, we can even handle chef's turns and his brother's turns separately. Suppose **Chef** denote number of cards Chef removes, while **Bro** denote number of cards that chef's brother remove.

The answer to this problem is **Sum of all cards - sum of Chef smallest cards - Sum of Bro largest cards**.

**Proof**: Chef will remove smallest cards available while brother will remove largest cards only. This way, turn of one doesn't affect the choice of other. We can simply remove **Chef** cards from front and **Bro** cards from the end.

Here's a simple [implementation][4].

This problem can also be a good problem for understanding [two pointers technique][5]. I have solved this using two pointers technique too, which can be referred [here][6].


#[Prefix Borders][7] (Only 40 points solution)

#### Difficulty: Easy-medium

### Problem

Given a String, we need to answer queries of the form p, k. Consider prefix of length p of given string, find length of kth smallest border of this prefix.

Border here is defined as the string which is both prefix and suffix of a string.

### Solution;

Since this is a simple solution for 40 points solution only, Constraints for this editorials are $N \le 100$ and editorial will be very short and too the point.

Define ArrayList[N+1] for string border lengths of ith prefix.

**For every prefix 1 to p, Find all the border of this prefix, push it into adj[p] the length of border found.**

This part can be done using brute force in $O(N^3)$ as $N<=100$.

After adding all the borders, sort all the ArrayLists.

Now we can answer queries in O(1) time.

If pth prefix doesn't have k borders, print -1, else print adj[p][k-1].

So simple to get 40 points.

Here's the link to my 

8.

Hope you all like my editorials.

As always i ask you all, to feel free to ask questions, share your approach for all problems.

Happy Coding :stuck_out_tongue:

5 Likes

Fixed formatting.

Thanks a lot!!

It wasn’t just getting right today.

Not all heroes wear capes.

:3 :stuck_out_tongue: XD

2 Likes

:smiley:

Some of them are writing unofficial editorials. :stuck_out_tongue:

and improving formatting. :slight_smile:

2 Likes

Lovely. That was what I call a real comeback XD

Sorry for posting it here but there is a “?” symbol near the answering box which redirects me to some spam website. I don’t know whether it is happening to me or others too so please check out the matter and report it to @admin

Screenshots:

image_1.png

image_2.png

Seems like an advert from wmd editor :confused:
The domain name is wmd-editor.com tho.

For any issue which you are confused like this, directly mail me. I forwarded in to @admin in morning and they are working on removing it.

1 Like

thanks. next time i will mail it to you if i see something fishy :slight_smile:

Question 2 - Game with numbers

What is the significance of the clause - “Note that the elements of A don’t have to be unique”

@karanmundra It means that the elements can be the same ie 1 1 2 2 3 3 3 if they were unique then all elements would appear only once and there would be no need of the occurrence array as every element would appear only once

I think I have a fast solution for Prefix Borders. However it is untested. I will try to write the code soon, so please tell me if there is any problems with my thinking.

We can use the idea for suffix arrays on the long string S. After all of the suffixes are sorted in n * log n time, all of the borders each border string will be close to the whole string S.
An example should make it clear:

ab

abcab

b

bcab

cab

These are all of the suffixes in sorted order. The border string that contains the border of “ab” is represented by elements close together in the suffix array: “ab” and “abcab”. By scanning through strings near “abcab” that share a common prefix with length >= 1 (calculated using LCP array), all border strings that can be formed using some prefix of string S can be found. A segment tree with lazy propagation can be used to keep track of the lengths of strings that can be formed because if “ab” can be a border, then “a” can also be a border. Every length from 1 to the length of the common prefix can be a border string length, and they should be marked in the segment tree with 1 (indicating that there is a border string with that length).

While handling the queries, the order the p-th prefixes to be handled in should be in sorted order. Also, the segment tree should be updated with any suffixes in the suffix array that share a common prefix with the original string S when the query’s p exceeds any of the indexes of the suffixes with common prefixes with S. Basically, the segment tree is updated to allow new border strings to be counted for each query.

Finally, to find the length of the k-th shortest border string, binary search (for q * log^2 n time) or explicitly traversing the segment tree (for q * log n time) can be done to answer the queries. The final time complexity should be around O(n * log n + q * log n) if everything is implemented in the fastest algorithm.

This might be a little confusing and I think I might be overthinking/over complicating the question.

3 Likes

Daringfireball link proposed here can be used.

I am unable to understand one thing-The post says “Proof: Chef will remove smallest cards available while brother will remove largest cards only. This way, turn of one doesn’t affect the choice of other. We can simply remove Chef cards from front and Bro cards from the end.”
In the code also, we are counting the number of cards that the chef and bro would remove.However. when we are subtracting the values from the total values of the card, then instead of solving them alternatively(once for chef and once for bro), we are first considering all the cards that the chef would remove and then we are considering the cards that bro would remove.How would it work?For example- After the first chance of the chef, bro won’t be able to choose the minimum numbered cards that we initially had.Rather, he would have to select the minimum cards FROM THE NOW AVAILABLE CARDS.So how can we say that the choice of chef doesn’t affect the choice of bro and vice versa?

Sorry, my mistake, i forgot to mention that firstly we sort the cards on basis of values written over them.

Now, u may see that chef only remove cards from front (as these are smallest) while his brother removes cards only from rightmost end (cards with largest value).

We can simply remove Chef cards from front and Bro cards from right separately and find sum of remaining cards.

“As u said, after first turn of chef, bro might not be able to pick cards” This would mean that chef deleted cards from right end too, which is not optimal.

This seems to be a nice simple idea, but u should try to implement it. Do let me know if you implement this.

Yes I got it now and got AC.But is there a way in which we can get the answer by considering the cards both bro and chef SELECT rather than REMOVING?During the contest, I was trying to update 2 variables-start and end after every chance but was unable to implement it correctly and was unable to think of actually considering the cards they both REMOVE and hence I was wondering if it is possible to get the answer using what I though during the contest?

Selecting x cards from set is same as removing all cards other than x present in set.

For that, you might give a look at my two pointer solution.

can someone explain me prefix border?