java - Number Guessing Game Over Intervals -

I have just started a long way to become a better codec on CodeChef. People start with problems marked as 'easy' and I did that.

The statement of the problem defines the following: -

1. N , where 1 & lt ; = N & lt; = 10 ^ 9 . It's an integer that keeps Johnny secret
2. k , where 1 & lt; = K & lt; = 10 ^ 5 . For each test case or game, Johnny signs exactly to Ellis exactly as k .
3. A signal op num yes / no , where -
   • op one operator , & gt; , = .
   • num is an integer, again satisfactory 1 < = Num & lt; = 10 ^ 9 .
   • The answer to the yes or no question is: What relationship does n op num hold?
   • If the answer to the question is correct, Johnny has spoken the truth otherwise, he is lying.

     Each alert program is fed and the program determines whether it is true or possibly a lie. My job is to find the minimum number of lies.

     Now uses the concept of tree segments, which I can not wrap my head at all. I was thinking that there is alternative data structure or method to solve this question, perhaps a simple, this idea is in the 'easy' category.

     This is what I tried -:

       class solution // represents a test case {hashaseet < SolutionObj & gt; Set = new hashet & lt; SolutionObj & gt; (); // Biggester maximum = new BigInteger ("100000000") to prevent duplicates; // Maximum limit BigTeague Min = new BigInteger ("1"); // minimum limit int lie = 0; // false counter zero addHint (strings) {string [] vals = s.split (""); Set.add (new solution obz (Wall [0], Walls [1], Wall [2])); } Zero test heets () {for (SolutionObj obj: set) {// The given number is not in the range of lies. If (obj.bg.compareTo (min) == -1 || obj.bg.compareTo (max) == 1) {false ++; to continue; } If (obj.yesno) {if (obj.operator.equals ("& lt;")) {max = new bigigneer (obj.bg.toString ()); // Change the maximum value} and if (obj.operator.equals ("& gt;")) {min = New BigInteger (obj.bg.toString ()); // Change less value}} and {// still keeping this part in mind}}}} class SolutionObj // represents a single signal. {String operator; Bigtegger BG; Boolean yeah; SolutionObj (string op, string integer, string yes) {operator = op; Bg = new bigteger (integer); If (yesno.toLowerCase (.) Equals ("Yes")). This.yesno = true; And this.Yes = wrong; } @ Override Public Boolean Equals {if (o Instance of Solution Oz) {SolutionObj s = (SolutionObj) o; // Make the cast if (this is YESNOW == S.INO & amp; this.bg.equals (s.bg)) & amp; this. Operator Angle (S. operator)) true return; } return false; } @ Override Public Ent Hashod () {return.bg.intValue (); }}   
      Obviously, this partial solution is wrong, save for the limit check that I have done before entering  (if not). I was thinking of updating the boundaries according to the signals provided, but the result is not born with the result of how the problem can be reached in addition to the use of Segment trees.   
      
      
      Consider the following approach, which may be easy to understand. Draw the 1d axis of the chandelix, and place k signals on it. Each gesture can be considered '(' or ')' or '=' (less or equal than, respectively).  
      Example:  
       ----- (---) ------- (- = -----) ----- ------)   
      Now, the true value is one of the 40 values ​​of this axis, but in fact only 8 volumes are interesting, because in the right / wrong section The number of signs is the same, it means that you can scan the signal according to their command on the signal, and at that point you can make a counter of the right signals.  
      In the above example, it goes like this:  
       Segment counter ------------------ ---- ------- (3 --- 4) ------- (3 - 4 = 5 & lt; --- Maximum ----- 4) ----- ----- - 3) 2   
      This algorithm needs to sort only the K signals and then scan them. This is near the linear in Kashmir (o * k), which is not dependent on n, so it should be time to walk properly.  
       Note:   
      1) In behavior, signals can have a non-specific condition, so you have to put all the same signals in the same condition at the same time.  
      2) If you need to go back to the minimum set of lies, then you should maintain a set instead of the counter. If you use hash sets then there should be no effect on complexity at that time.