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:
 The for each hint loop has to be turned into a recursive method such that only range or the children and grand children of the current range get updated. If a range gets updated donâ€™t update its children and its grand children.

n is too large, up to 10^9 but since the number of hints is up to 10^5 we can compress it such that in the end we donâ€™t have to check for ranges that end at 10^9. Actually when compressing the values the maximum possible range to check will be range[1 : 10^5]. I donâ€™t need to spoil all the fun, you can think of how to do this by yourself.
 Our magical array can actually be implemented but it will be more than one array, Iâ€™ll also leave this to you.
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:
 Read this segment tree tutorial on topcoder.
 Solve MSTICK using the tutorial in 1 and other sources in the internet if you have too. If you canâ€™t understand the segment tree tutorial try to modify the algorithm in order to solve this problem. Youâ€™ll understand it at some point if you keep doing alterations.
 Solve GSS1 and GSS3. In Java BufferedReader will probably time out for these 2 problems, if you use Java use a fast reader template or I can send you a readInt method that will do the job.
 You can read my solution to MSTICK or check the editorial. I canâ€™t give you a link of a nice solution because I havenâ€™t checked them but if you still canâ€™t understand check the solutions of the best coders.
 My solution to A3 follows the explanation I gave you. The code is not commented but it might be useful to read, if there is any doubt just ask, also check the other solutions, maybe youâ€™ll find a better approach, I havenâ€™t check them yet.
@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.