does anyone have any DEEPER notion about A3 - The Guessing Game: http://www.codechef.com/problems/A3 approach?
thanx beforehand.
edit: pls look below for explanation. and pls show your gratitude by VOTING UP the answer of both @betlista and @junior94 for their effort. i love codechef for their coders that are willing to help others. without them(coders who help) it would be difficult to gain a new skill and improve ourselves. thank you.
Nice problem 
My first idea is to use intervals for each negated condition, then the rursult is to find point with minimum intervals…
I saw your question and was able to solve to problem thanks to @betlista’s answer, it was a big hint but I’ll go deeper and try to explain my full solution.
Problem:
Alice and Johnny play the following game: Johnny chooses an int n (1 <= n <= 10^9) and gives Alice k (1 <= k <= 10^5) hints where each hint is given as operator li (1 <= li <= 10^9) logicValue where operator can be <, > or =, and logicValue can be either “Yes” or “No” (without quotes) such that the condition n operator li logicValue holds for every hint. If logicValue is “Yes” the expression in the hint is true, otherwise is false. Alice knows that Johnny may lie (saying “Yes” instead of “No” and viceversa) so she wants to know for every game they play what is the minimum possible number of lies Johnny told her. (Read the problem statement for a better explanation).
Solving the problem:
Let’s simplify things and play a variant of the game where 1 <= n <= 10 and 1 <= li <= 10 and 1 <= k <= 10. For these constraints finding the number of lies is pretty straight forward and we can solve it using a very naive solution: for every value of n from 1 to 10 go through every hint and check if it is true for the current value of n, if it is increase the count of true hints for the current value of n, in the end the answer for the current game will simply be k - (maximum count of true hints) which is the same as saying taking the maximum count of trues from the total number of hints. Since we want the minimum number of lies we have to subtract the maximum number of trues. We could also count the number of lies for each value of n, it could be done using either way but I solved the problem using the first way.
@garakchy, the good news is that the solution above works for the big constraints as well, all we have to do is to reduce the number of repeated operations. There are 2 ways to do this, using segment trees or fenwick trees, I used segment trees and this is the one that I’ll explain. I don’t want to talk about fenwick trees for this particular problem since before solving any problem you can’t be 100 % sure if your way of thinking is right and using fenwick tree would be solving the problem in a different way. To be more accurate I’m also a very lazy person so if whoever uses fenwick tree to solve the problem and gets AC is willing to explain it would be cool to post the answer in this thread (@garakchy you want to go DEEPER, right ?). Now continuing…
Segment trees
So why solve using segment trees? Well, it may not click as soon as we read the problem statement but we can get there. How ? First let’s consider what we want to do, going back to the naive approach: we want to count the number of true hints for each value of n and take the maximum of those values. We also know that the naive approach is very costly but we have no other ideas and we want to optimize the naive approach. Let’s try and look from the hints perspective. Instead of counting the number of true hints for every n let’s go through each hint and increase the count of those values of n which satisfy the current hint.
Let’s consider a few examples, remember that when the logicValue is “No” only the counts of those values of n which do NOT satisfy the expression will be increased, if the logicValue is “Yes” only the counts of those values of n which satisfy the expression will be increased:
For each hint:
if operator == '<':
if logicValue == "Yes":
add 1 to every count[n] such that 1 <= n < l[i]
else:
add 1 every count[n] such that l[i] <= n <= 10^9 // maximum value of n is 10^9
else if operator == '>':
if logicValue == "Yes":
add 1 to every count[n] such that l[i] < n <= 10^9
else:
add 1 to every count[n] such that 1 <= n <= l[i]
else: // operator is '='
if logicValue == "Yes":
add 1 to count[l[i]] // only 1 value satisfies the condition
else:
add 1 to count[n] such that 1 <= n < l[i]
add 1 to count[n] such that l[i] < n <= 10^9
Seeing the code above we can see that in the worst case we will be updating 10^9 - 1 values of n and like this wasn’t enough k can be as large as 10 ^ 5. But know we now that the real cost is updating all the range and we want to update only what is needed. So let’s imagine that somehow we have a magical array representing each range so now we would increase the count of each range instead of increasing all the values of n. In this array if we can access each range directly for example the range 1:10 can be accessed like array[1:10] and the complexity for accessing each range is O(1).
For each hint:
if operator == '<':
if logicValue == "Yes":
add 1 to range[l[i] : n - 1] // remember that our array is magical
else:
add 1 to range[n : 10^9]
else if operator == '>':
if logicValue == "Yes":
add 1 to range[l[i] + 1 : 10^9]
else:
add 1 to range[1 : l[i]]
else: // operator is '='
if logicValue == "Yes":
// magical array but we always have to specify the begin and the end of the array
add 1 to range[l[i] : l[i]]
else:
add 1 to range[1 : l[i] - 1]
add 1 to range[l[i] + 1 : 10^9]
There are two hints that will always be lies:
But now let’s ignore them and since our array is magical it doesn’t do anything if such cases are reached.
Moving on, we can easily update our magical array but how to know which value of n holds the maximum value ? Well, let’s begin with the simplest way: for each possible range increase the values of each value of n present in the range.
for 1 <= begin <= 10^9:
for begin <= end <= 10^9: // end can never be lower than begin
for begin <= n <= end:
count[n] += range[begin : end]
maximum = max(count[n], range[begin: end]
Maximum is the maximum value of true hints for every possible value of n but the method we’re using is way too expensive. One thing to note is that there are in total 10^9 * (10^9 + 1) ranges but only 10 ^ 5 hints. That means that at most 10 ^ 5 ranges will be updated. Our array range is very magical and it can detect if a certain range was updated or not so we can change our code in order to only go through the important ranges.
for 1 <= begin <= 10^9:
for begin <= end <= 10^9: // end can never be lower than begin
if range[begin: end] was updated:
for begin <= n <= end:
count[n] += range[begin : end]
maximum = max(count[n], range[begin: end]
This method is still too costly even with tuning up our range array but we won’t give up. Let’s try to do it recursively without looping over every possible range. And let’s add more magic to our array such that it knows if any child was updated. A child of a range[begin : end] is a range[begin1 : end1] such that begin1 >= begin <= end and begin1 <= end1 <= end and either begin1 > begin or end1 < end (to avoid infinite loops).
function updateNs(begin, end):
if range[begin : end] was updated:
for begin <= n <= end:
add 1 to count[n]
// don't access this range again, otherwise we would be adding it multiple times
set range[begin : end] as no longer updated
if no children of this range were updated just return
// There are still updated childs
for begin <= begin1 <= end:
for begin1 <= end1 <= end:
if begin1 != begin or end1 != end:
updateNs(begin1, end1)
We have somehow reduced the cost but not so much. Considering that the main range is range[1…10^9] and every range falls within this one we would still go through every possible range. And there is still another pitfall: there are a lot of children that have a huge number of parents which means that there are still many loops. consider range[1 : 5]. It would be checked for every parent. Ranges that would surely check it: range[1 : 6], range[1 : 7] and so on up to range[1 : 10^9]. And as if that weren’t enough there are many more ranges that have so many parents.
So what to do?
The main problem is that each range has a lot of parents. Let’s try and make sure that each range has only one direct parent but how can we do this?
We can try to make sure each range has some number of children such that each one of it’s children are not shared by other ranges. Let’s try saying that each range can only have 5 children. The most effective way to do this is to break each range the in the best way we can:
range[1 : 20] would be separated into the following ranges:
range[1 : 4], range[5 : 8], range[9 : 12], range[13 : 16], range[17 : 20].
As we can see none of range[1 : 20] children can no longer have 5 children. Somehow we have to break those ranges too. We could say that each range will have at most 5 children. Then there would be ranges with 2, 3, 4 children. There is no range with 1 child, ranges that can only have 1 child only have 1 value and there wouldn’t make much sense to say that a range is a child of itself, for those special ranges just update the one value they have. Now going back, we are saying that ranges will have 1, 2, 3, 4, 5, children but checking all those children and knowing how many children fall within the range is extra work so let’s try and make sure that each range will have the same number of children. For this we will have to choose the least possible number such that we can break all ranges into that number of children. The best way to do this is to choose the lowest possible number of children which is 2 (1 can’t be chosen for reasons mentioned earlier). Of course we don’t want to break the range arbitrarily so let’s break the range into two ranges with length difference at most 1.
range[1 : 20] would then be broken into range[1 : 10], range[11 : 20]
range[1 : 10] would then be broken into range[1 : 5], range[6 : 10]
range[1 : 5] would then be broken into range[1 : 2], range[3 : 5] // range[3 : 5] is one length bigger than range[1 : 2] but that’s okay
range[1 : 2] would then be broken into range[1 : 1] and range[2 : 2] // each one of those has no child and will only update one value of n
Now another problem has risen… Damn!!! Okay, let’s not give up. Have you identified it yet? Well how can we get to range[2 : 5] or range[5 : 6] ? It seems like its not possible but let’s see something interesting:
range[2 : 5] is range[2 : 2] + range[3 : 5]
range[5 : 6] is range[5 : 5] + range[6 : 6]
Overall to get the answer we would do:
For each hint:
if operator == '<':
if logicValue == "Yes":
add 1 to range[l[i] : n - 1]
else:
add 1 to range[n : 10^9]
else if operator == '>':
if logicValue == "Yes":
add 1 to range[l[i] + 1 : 10^9]
else:
add 1 to range[1 : l[i]]
else: // operator is '='
if logicValue == "Yes":
add 1 to range[l[i] : l[i]]
else:
add 1 to range[1 : l[i] - 1]
add 1 to range[l[i] + 1 : 10^9]
Our array is still magical but now with some help of non magical stuff.
function getMaxTrueHints(begin, end):
maxTrueHints = 0 // check how many true hints fall within this range
if range[begin : end] was directly updated:
maxTrueHints += range[begin : end]
if begin == end: // special case
return maxTrueHints
if range[begin : end] has an indirectly updated child:
//a child is considered indirectly updated if itself or one of its children was updated
mid = (begin + end)/2 // as integer division
//mid is the splitting point, it will be the end of the first child
//the begin of the second child is mid + 1
//we want the children to be independent
//mid is integer division and it is okay, for a range with odd length the second child will
//be one unit bigger than the second one
child1 = getMaxTrueHints(begin, mid)
child2 = getMaxTrueHints(mid+1, end)
maxTrueHints += max(child1, child2) // getting the maximum true hints between those two children
return maxTrueHints
To get the answer we just have to call getMaxTrueHints(0, 10^9). This is the segment tree approach to the problem but there are a few things that should be noted that I can’t write right now because this answer is already too big:
Well, I tried to go as deep as I could but I believe I gave you some base. If there is some part you don’t understand feel free to ask, if I can I’ll answer it. I could explain the full method and explain each line of the code and why it works but as I said this answer is already too long, ask in the comments, I’ll try to answer the best I can. I assure you that if what I wrote doesn’t make sense now it will after following these steps (even if you have to spend a day or a week in those, try to understand them), follow them in the order they are:
@garakchy, this being said I haven’t gone as deep as I could have been, if I had this answer would have been several pages long but I hope it can point you to the right direction. At some point I might have omitted something or skipped, I don’t really know, if you notice something like this, again, just ask. I welcome anyone to correct grammar, logical and syntactical errors as I’m sure I’ve made quite a few. If you have something to add you’re free to go as well.
garakchy, you do not need to, you up vote is sufficient 
No problem, glad to help… And thanks for the extra points, really generous of you but keep some of it for yourself you might need it later :)…
Thanks for sharing the solution. I found your solution nice and elegant. Also, the Topcoder tutorial was very helpful.