数字猜测间隔游戏

Question

我刚刚开始了我成为CodeChef上更好的编码器的漫长道路。人们从标记为“易”的问题开始，我也这样做了。

The Problem

问题语句定义如下 - ：

1. n，其中1 <= n <= 10^9。这是约翰尼保守秘密的整数。
2. k，其中1 <= k <= 10^5。对于每个测试案例或游戏实例，约翰尼精确地向爱丽丝提供k提示。
3. 一个提示的形式op num Yes/No，其中的 -
   • op是从<，>，=一个运算符。
   • num是一个整数，再次满足1 <= num <= 10^9。
   • Yes或No是对问题的回答：关系n op num是否成立？
4. 如果问题的答案是正确的，约翰尼已经说出了一个事实。否则，他在撒谎。

每个提示都反馈给程序，程序确定它是真相还是可能的谎言。我的工作是找到尽可能少的谎言。

现在CodeChef's Editorial answer使用分段树的概念，我根本无法包裹头部。我想知道是否有替代数据结构或方法来解决这个问题，也许是一个简单的问题，因为它在“简单”类别中。

这是我尝试 - ：

class Solution //Represents a test case. 
{ 
    HashSet<SolutionObj> set = new HashSet<SolutionObj>(); //To prevent duplicates. 
    BigInteger max = new BigInteger("100000000"); //Max range. 
    BigInteger min = new BigInteger("1"); //Min range. 
    int lies = 0; //Lies counter. 

    void addHint(String s) 
    { 
     String[] vals = s.split(" "); 
     set.add(new SolutionObj(vals[0], vals[1], vals[2])); 
    } 

    void testHints() 
    { 
     for(SolutionObj obj : set) 
     { 
      //Given number is not in range. Lie. 
      if(obj.bg.compareTo(min) == -1 || obj.bg.compareTo(max) == 1) 
      { 
       lies++; 
       continue; 
      } 
      if(obj.yesno) 
      { 
       if(obj.operator.equals("<")) 
       { 
        max = new BigInteger(obj.bg.toString()); //Change max value 
       } 
       else if(obj.operator.equals(">")) 
       { 
        min = new BigInteger(obj.bg.toString()); //Change min value 
       } 
      } 
      else 
      { 
       //Still to think of this portion. 
      } 
     } 
    } 

} 

class SolutionObj //Represents a single hint. 
{ 
    String operator; 
    BigInteger bg; 
    boolean yesno; 

    SolutionObj(String op, String integer, String yesno) 
    { 
     operator = op; 
     bg = new BigInteger(integer); 
     if(yesno.toLowerCase().equals("yes")) 
      this.yesno = true; 
     else 
      this.yesno = false; 
    } 

    @Override 
    public boolean equals(Object o) 
    { 
     if(o instanceof SolutionObj) 
     { 
      SolutionObj s = (SolutionObj) o; //Make the cast 
      if(this.yesno == s.yesno && this.bg.equals(s.bg) 
        && this.operator.equals(s.operator)) 
       return true; 
     } 
      return false; 
    } 

    @Override 
    public int hashCode() 
    { 
     return this.bg.intValue(); 
    } 
} 

显然，这部分解决方案是不正确，保存为范围检查，我已经进入if(obj.yesno)部分之前完成。我正在考虑根据提供的提示更新范围，但这种方法并未取得成果。除了使用细分树之外，我应该如何解决这个问题？

Answer 1

考虑下面的方法，这可能更容易理解。查看整数的第1轴，并在其上放置k个提示。每个提示可被视为'（'或'）'或'='（分别大于，小于或等于）。

实施例：

-----(---)-------(--=-----)-----------) 

现在，真正价值是某处在此轴上的40个值中的一个，但实际上只有8个段是有趣的检查中，由于段内的任意位置的真实数目和/虚假提示保持不变。 这意味着您可以根据轴上的顺序扫描提示，并在该位置维护一个真正提示的计数器。

在上面的例子中它是这样的：

segment   counter 
----------------------- 
-----(   3 
---    4 
)-------(   3 
--     4 
=     5 <---maximum 
-----    4 
)-----------  3 
)     2 

该算法仅需要到第k提示进行排序，然后对其进行扫描。它在k（O（k * log k））中接近线性，不依赖于n），因此它应该有一个合理的运行时间。

注：

1）在实践中，提示可能有非不同的位置，所以你必须处理所有相同类型的提示在相同的位置在一起。 2）如果你需要返回最少的一组谎言，那么你应该保持一套而不是一个计数器。如果使用散列集合，这对时间复杂性应该不会产生影响。

Answer 2

如果目标号码= 1（将其存储在变量lies中），计算谎言的数量。

让target = 1

排序和组由它们各自的值的语句。

遍历报表。

• 将target更新为当前语句组的值。根据这些语句中有多少将成为真或假，更新lies。

• 然后更新target该值+ 1（为什么这样做时，请考虑有> 5和< 7 - 6可能是最好的价值），并相应地更新lies（跳过这一步如果下一个语句组的值是该值）。

返回lies的最小值。

运行时间：

O(k)用于初始计算。

O(k log k)这种排序。

O(k)用于迭代。

O(k log k) total。

Answer 3

我对这个问题的想法与Eyal Schneider如何看待它类似。将'>'表示为更大，'<'小于等于'='，我们可以按照他们的num对所有'提示'进行排序，并逐个扫描所有有趣的点。

对于每个点，我们保留从0到该点（在一个名为int[]lessAndEqual的数组）中的'<'和'='的所有数目，从该点开始的数字'''和'='一个数组叫int[]greaterAndEqual）。我们可以很容易地看到，谎言在一个特定的点i的数量等于

lessAndEqual[i] + greaterAndEqual[i + 1] 

我们可以很容易地填补lessAndEqual和greaterAndEqual阵列由两个扫描在O（n）和排序的所有提示在O（nlogn ），结果时间复杂度为O（nlogn）

注意：对于提示中的num等于的情况应该采取特殊处理。另请注意，num的范围是10^9，这要求我们有一些形式的点压缩以适应阵列到内存中。