The problem required us to find the expected saving chef can make considering the average of all the discounts over all the combinations Chief might select.

A novice approach of trying all combinations will TLE.

Dynamic programming might be of help here. As the chief would like to maximize the discount he may get over a combination he would use lower discounts for lower costs articles.

My Approach -

1. Sort all costs in ascending order.

2. Sort all discounts in ascending order.

We have N articles and K discounts to use.

expected(n,k)= (expected(n+1,k+1)+cost(n)*discount(k))*((K-k)/(N-n))+expected(n+1,k)*(1-(K-k)/(N-n))

Here n and k denote the number of articles considered and the number of discounts used till now. We have to find expected(0,0) and the multiplication of (K-k)/(N-n) is done to one side and (1-(K-k)/(N-n)) to the to the other because when while calculating expected(n,k) (N-n) articles remain to be considered and (K-k) discounts remain. The probability of getting the article is (K-k)/(N-n) and not getting is (1-(K-k)/(N-n)).

Using this approach we find the expected discount that chef can achieve.

I used this code during the contest which had memoization and i got TLE.

I used this code after the contest which avoided recursion and used straight forward DP and got WA.

Can anyone help me here. 

EDIT: Got AC... Used sliding window DP by minimizing the memory table to 2 rows. As only 2 are required.

Here is the Code

Here is a short description on how I solved the 3 problems hopefully it is helpful.

The first problem required manual checking. As I use Java, StringTokenizer helped me to break the string using '.' as the delimiter. As I had 2 strings I could check for the last character of the first string and if it was equal to 9 I printed "GOTO Vasilisa." and for the other case I checked if the first char of the other string was greater than '5' if yes I added 1 to the first strings last char else print the same string.

Problem B was easier considering the mathematical nature of the problem. There were a few cases to take care of and a score of 900+ was easily get able. On summing up the volumes if they don't divide equally among the n cups, then the answer is unrecoverable. If all of the values are equal to the average then the pages did not play any prank. On the other hand if more than 2 cups deviate from the average the answer is again unrecoverable. If the number of cups that deviate is 2. We can find the cups which were used for transfer and find the volume transferred by calculating the difference of the values from the mean.

The problem is easy but during the contest I could not come with a very good approach in one go. I started waywardly and in the end pre computed all the 24 configurations which are equal to each other. Then I just checked how many different configurations can be made using the colors given. Generate all the 720 permutations of the string for that.

For the generation of the 24 configurations I fixed a top and then rotated the cube by 90 degs again and again to get all the 4 configurations for that top. Fixing all the  6 tops. We get in total 6*4=24 configurations as equivalent to each other.

code snippet

//24 configurations given

configs[]={"012345","031425","043215","024135","103254","120534",

"152304","135024","254103","215043","201453",

"240513","310542","351402","345012","304152","453201",

"425031","402351","430521","513240","521430","542310","534120"};

This was a straight forward question which required the checking of "0000000" or "1111111" as a substring contained in the given string. Java implementation allows the use of str.contains() function which makes the code very short.

This question could be solved by brute force considering the small constraints for this question. Keeping a recursive method which takes the temporary number created till now the count of fours and sevens and global variable which stores the answer can help us solve the question with ease.

Again a straight forward implementation. Some of the things to note. If the string contains the substrings all characters of that substring have to be replaced. Hence we replace with the favorite char but if the favorite char is already there we replace with 'A' or 'a' because that happens to be lexographically smallest. Corner case- Favorite char is 'A' , if yes.. if 'A' is present as a part of substring replacement is done by 'B'.

Some of the things which I did not take note of during the competition which prevented my solution from passing. Use adjacency list instead of matrix as the number of roads are only 1000. The question says that there can be multiple roads between junctions so updation needs to be done to adj[s][e] when a lower distance comes up.

Approach

A combination of djikstra and DFS allows us to find the minimum cost incurred in traversing the points. Update your djikstra cost array at all nodes which can be visited from the taxi you are in. This can be done using DFS. Again find the minimum cost junction and continue. If at the end you are not able to reach the destination output should be -1.