JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
SRM 330 LongLongNim Problem | Reply
Hi,

I was reading topcoder article on Game theories where I found LongLongNim Problem:

http://community.topcoder.com/stat?c=problem_statement&pm=6856

I was going through the editorials and Petr's Solution but not able to understand it. Can anyone please provide a simpler explanation of the mentioned problem.

http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm330

using System; 
using System.Collections.Generic; 
 
public class LongLongNim { 
  public int numberOfWins(int maxN, int[] moves) { 
    int mask = (1 << 22) - 1; 
    int res = -1; 
    Dictionary<int, int> last = new Dictionary<int, int>(); 
    List<int> r = new List<int>(); 
    for (int i = 0; i <= maxN; ++i) 
    { 
      mask <<= 1; 
      ++res; 
      foreach (int j in moves) 
        if ((mask & (1 << j)) == 0) 
        { 
          ++mask; 
          --res; 
          break; 
        } 
      mask &= (1 << 22) - 1; 
      if (last.ContainsKey(mask)) 
      { 
        int pLength = i - last[mask]; 
        int cnt = (maxN - i) / pLength; 
        i += cnt * pLength; 
        res += cnt * (res - r[last[mask]]); 
      } 
      last[mask] = i; 
      r.Add(res); 
    } 
    return res; 
  } 
 
 
} 


Thanks
RSS