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.
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”.
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).
Won’t the length of array change on replacing character to number?
Eg: Character : z
Number : 26
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.
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
you are considering floor division, while the problem requires float division.
Initial answer N/1.
change your condition to (num > 2*K) and add (num/K - 2)*freq[i] to answer. Handle fractions instead of taking floor division.
I have used double k to do float division.I understand your logic,But what is wrong with my logic.
My idea is to either choose letter or convert to number.
The cost of one letter is 1 and cost of one number is (-1)+(num/k),so my condition is num/k - 1(cost of number) > 1(cost of one letter) then convert to number else add 1 to sum
Yes we can, though there is a small problem with your solution, the constraints state that ‘A[i][j]’ can also be ‘0’ since 0 doesn’t count towards the score, its frequency doesn’t matter, but you are considering that in your solution. A small change in the last loop of your solution to ignore the frequency of zero gets an ac. CodeChef: Practical coding for everyone
@garrykevin, you are using float arithmetic here which is causing the issue, consider the following testcase where k is 3 and the string is ‘j’. since replacing j with 10 gives us benefit we should replace it. Now your solution stores it in rsum in the form 2.333333333 (assuming precision of 9 digits) when you convert it back it converts back to 2333333333/1000000000 though the precise answer should be 7/3 (as the actual value is 2.33 repeating). You are loosing precision while storing it as double. Instead store integer numerator and denominators separately.
Can anyone explain this line “For the substring which contain “x” in the middle we can visualise them as 2 parts, left and right and their mask being the “OR” of the left and right mask. Thus doing this OR convolution of the left and right masks in naive manner i.e. O(ALPHA**2) we can find their contribution too.”,what does convolution means here and what is ALPHA?any help or reference to any tutorial for learnig such concepts is welcomed.
Thanx in advance!!
thanks mate.