### Easy Coding Contest 15 Editorial

Posted:

**Sat Dec 02, 2017 2:00 pm**Contest Problem Archiev Link: https://devskill.com/ContestArchive/Con ... d53364c275

Contest Ranklist Link: https://devskill.com/home/contestrankli ... d53364c275

Problem A: Dwindle Words

For each word in a given list, firstly calculate the total number of distinct letters in it. You can do this simply increasing frequency of every 26 characters in given string and then looping over all 26 character to find how many of them are there.

After this, find out the value of lowest distinct letter containing word. Now, simply iterate from word 1 to N to see if they have lowest value, if they have then print them. Doing this will automatically print valid words in increasing order.

Problem B: Minimum Base

Find the maximum digit in the given number. Here value of 0-9 is same,A-Z is between 10-35 respectively and a-z is between 36-61 respectively.Then print max+1. If max=0 then print 2 because base is between 2-62(inclusive).

Here max=maximum digit in the given number.

Problem C: Boltu vs Balti

If you Notice the increasing sequence of factorial is too much higher than the increasing sequence of partial sum. From 1st to 3rd factorial number and partial sum are pretty similar. If you think about the 1st to 5th factorial number and partial sum hope so you will get the answer.

For the first test case N = 4. The factorial of 4 is 24 (1*2*3*4) and 4-th Partial sum is 10 (1+2+3+4). While 4-th factorial number and 4-th partial sum is not same that's why output is "NO".

If you observe carefully, you will see that only for 1 and 3, both value will be same.

Problem D: Sanvi and Magical String

A string will be Magical String if all the letters of the string are identical.Your task is to convert the given string into Magical String in minimum number of steps.In each step, you may select any index of the current string and convert the letter at that index into another letter of your choice. Here, you can greedily keep the maximum occurred letter in the word unaltered and change remaining character.

If max_fre=maximum frequency of any character in given word.

and, n= length of word.

Then, answer will be simply: n-max_fre.

Problem E: Easy Game

You are given String S consisting of lowercase alphabets. Alice always starts first. In each step, they chooses an index and changes the character at that index to lowercase alphabet letter which is lexicographically smaller than previous one. So, they can not make a move if character of the index is 'a'. One who can not make any move losses the game.

You can simply convert above scenario into NIM game with N piles each having some coins. Here, N means total length of string S and coins in each pile will be equal to ( character-'a' ) in every index. Now, we may apply NIM theory so that Alice will win the game if bitwise XOR of all coins in the list is not equal to zero. Otherwise, Bob will win.

You may learn more about NIM game here: https://www.topcoder.com/community/data ... thm-games/

Contest Ranklist Link: https://devskill.com/home/contestrankli ... d53364c275

Problem A: Dwindle Words

For each word in a given list, firstly calculate the total number of distinct letters in it. You can do this simply increasing frequency of every 26 characters in given string and then looping over all 26 character to find how many of them are there.

After this, find out the value of lowest distinct letter containing word. Now, simply iterate from word 1 to N to see if they have lowest value, if they have then print them. Doing this will automatically print valid words in increasing order.

Problem B: Minimum Base

Find the maximum digit in the given number. Here value of 0-9 is same,A-Z is between 10-35 respectively and a-z is between 36-61 respectively.Then print max+1. If max=0 then print 2 because base is between 2-62(inclusive).

Here max=maximum digit in the given number.

Problem C: Boltu vs Balti

If you Notice the increasing sequence of factorial is too much higher than the increasing sequence of partial sum. From 1st to 3rd factorial number and partial sum are pretty similar. If you think about the 1st to 5th factorial number and partial sum hope so you will get the answer.

For the first test case N = 4. The factorial of 4 is 24 (1*2*3*4) and 4-th Partial sum is 10 (1+2+3+4). While 4-th factorial number and 4-th partial sum is not same that's why output is "NO".

If you observe carefully, you will see that only for 1 and 3, both value will be same.

Problem D: Sanvi and Magical String

A string will be Magical String if all the letters of the string are identical.Your task is to convert the given string into Magical String in minimum number of steps.In each step, you may select any index of the current string and convert the letter at that index into another letter of your choice. Here, you can greedily keep the maximum occurred letter in the word unaltered and change remaining character.

If max_fre=maximum frequency of any character in given word.

and, n= length of word.

Then, answer will be simply: n-max_fre.

Problem E: Easy Game

You are given String S consisting of lowercase alphabets. Alice always starts first. In each step, they chooses an index and changes the character at that index to lowercase alphabet letter which is lexicographically smaller than previous one. So, they can not make a move if character of the index is 'a'. One who can not make any move losses the game.

You can simply convert above scenario into NIM game with N piles each having some coins. Here, N means total length of string S and coins in each pile will be equal to ( character-'a' ) in every index. Now, we may apply NIM theory so that Alice will win the game if bitwise XOR of all coins in the list is not equal to zero. Otherwise, Bob will win.

You may learn more about NIM game here: https://www.topcoder.com/community/data ... thm-games/