# Invitation to International Coding League 2018- External Rated Contest

Short explanation for last problem: Raid Systems

The first idea of the problem is to see that files on xth hard disk can be retrieved using files on hard disk 1. The file indices differ by exactly (x-1). For example, if at any moment of time, hard disk 1 has files f1, f2, f5 when n = 5, then hard disk 2 has files f(1+2-1), f(3+2-1), f(5+2-1) i.e. f2, and f3 (f7 is discarding). See the table to convince regarding this observation. Thus, the queries of both type can be handled very easily using binary search only provided we are able to find the files in sorted order on hard disk 1 on any day.

Next thing is to notice is that the pattern of files being stored on hard disk 1 will repeat after some time, to be precise after 2^(ceil(log2(n)). Draw a table for n = 8 and n = 5 to get view of it. Next observation is that total number of files we require for all possible days is bounded by 3^ceil(log2(n)). For example: Consider n = 4

0: f1
1: f1, f2, f3, f4
2: f1, f3
3: f1, f2
4: same as 0 i.e. pattern repeats.

The total number of files stored i.e. slots used is (1 + 4 + 2 + 2) = 9, 3^2. You can see this thing for any general n. Complete the table for n=5 and observe the same. Now, we just need to come up with a 3^(ceil(log2(n)) generation algorithm, which gives us the files in sorted order on any day. The memory complexity will also be the same. Many constructive algorithms can exist and you can try to find your own. My solution uses just one of my finding, idea is again similar to binary search i.e. can be divide the files (in sorted order) in half, calculate the files on left side and use it to calculate the files on right side. Basically, I mean to say that if a particular bit is set in “y” and we calculate the lower half files, then the upper half files are basically the mirror image on the lower half files. You can check my “gen” function in the solution code for details.

(https://github.com/likecs/ICL-18-Solutions/blob/master/Raid%20systems.cpp)
1 Like

For each test case, output a single line containing two space seperated integers a and b such that a / b = Pmax - the maximum possible power achievable after transformation and gcd(a,b) = 1

I don’t get this part. Can anyone explain?

In problem 2

I considered lsum(count of letter) and rsum(-count of numbers + (sum of numbers/K))

So,For each i since sum += 1(count of letter) or -1(count of number) +(val(s[i])/k)

int num = (int)a[i]-96;
if(num/k - 1 > 1)
lsum += num/k - 1;
else
rsum++;

What is wrong with this

[1]: https://www.codechef.com/viewsolution/17560153

In problem 1
Can we solve by checking the frequency of each number from 1 to 100 and if frequency of every element is even then there will be “draw” otherwise “cyborg” will win?

OR can anyone can provide testcases were this solution fails CodeChef: Practical coding for everyone

In problem2. “Geno” can never win… that’s cool observation

@vivek_1998299 ALPHA refers to alphabet size, which is 20 here. OR convolution refers to polynomial multiplication where c_0 x^{p_0} \cdot c_1 x^{p_1} = c_0c_1 x ^{p_0 | p_1}. To put it simply the coefficients at p_0 and p_1 affect p_0 | p_1 instead of p_0 + p_1.

This is relevant here in the following manner: assume you know there are c_0 substrings with mask p_0 that begin at “x”. Similarly there are c_1 substrings with mask p_1 that end at “x”. So there will be c_0c_1 substrings with mask p_0 | p_1 that contain “x” irrespective of where it lies.

2 Likes

Sorry for the delays, the editorials are given in below links:

Contest starts in 20 minutes.

In problem 2
Next part is to modify the cost function as “length — 2(count of numbers) + (sum of numbers)/k”
I am not able to get this! Can you elaborate a bit more on this?

Count of numbers + count of characters = n (i.e. length of array). So we replace count of characters in the cost function using the above equation.

For example after simplifying the function, you find the value as 12/10, So you should print the answer as “6 5”.

2 Likes

This problem is quite interesting and it seems the accepted solutions use various different methods. My solution uses the fact that the queries can be reduced to the form of find the position of the a^{th} odd number in the b^{th} row of Pascal’s triangle, due to the pattern that shows up. And it turns out that all the odd numbers are at the positions which are numbers obtained by removing zero or more set bits from the binary representation of b (source).

1 Like

Won’t the length of array change on replacing character to number?
Eg: Character : z
Number : 26

solution:CodeChef: Practical coding for everyone
what is wrong with solution?

I get it. Thanks

@dishant_18, don’t see numbers literally, try to understand them as single object occupying a position and what value it adds if it was present.

1 Like

I too had got the first observation, that its required to calculate for hard disk 1 only. Noticed the pattern too, but couldn’t formulate it in terms of code. Had the idea of binary search, but messed up.

PS: Same pattern of bits occurs in problem CodeChef: Practical coding for everyone

1 Like

you are considering floor division, while the problem requires float division.