Created
December 13, 2016 07:28
-
-
Save jianminchen/98f38cfb31bace070184b641c95d14b9 to your computer and use it in GitHub Desktop.
Kindergarten adventure - score 1.09 - pass test case 0 and 1 -
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Diagnostics; | |
using System.IO; | |
using System.Linq; | |
class Solution | |
{ | |
static void Main(String[] args) | |
{ | |
SegmentTreeProcessing(); | |
//TestSampleTestcase(); | |
} | |
/* | |
* Sample test case: | |
* n = 1 | |
* 1, 0, 0 | |
* | |
* segment tree: | |
* | |
* 0 | |
* / \ | |
* 0 2 | |
* / \ / | |
* 2 1 1 | |
* | |
*/ | |
private static void TestSampleTestcase() | |
{ | |
int n = 3; | |
int[] extraMinutes = new int[] { 1, 0, 0 }; | |
var tree = BuildTree(n, extraMinutes); | |
int id = FindMaxValue(tree, extraMinutes); | |
Debug.Assert(id == 2); | |
} | |
/* | |
* Code change: | |
* | |
*/ | |
public static void SegmentTreeProcessing() | |
{ | |
int n = int.Parse(Console.ReadLine()); | |
var extraMinutes = Console.ReadLine().Split().Select(int.Parse).ToArray(); | |
var tree = BuildTree(n, extraMinutes); | |
Console.WriteLine(FindMaxValue(tree, extraMinutes)); | |
} | |
/* | |
* | |
*/ | |
private static int FindMaxValue(SegmentTree tree, int[] extraMinutes) | |
{ | |
int bestIndex = 1; | |
int best = 0; | |
for (int i = 1; i <= extraMinutes.Length; i++) | |
{ | |
var curr = tree.Query(i - 1); | |
if (curr > best) | |
{ | |
best = curr; | |
bestIndex = i; | |
} | |
} | |
return bestIndex; | |
} | |
/* Extract a standalone function | |
* | |
*/ | |
private static SegmentTree BuildTree_question(int n, int[] extraMinutes) | |
{ | |
var tree = new SegmentTree(n); | |
for (int i = 0; i < n; i++) | |
{ | |
int curr = extraMinutes[i]; | |
int len = extraMinutes.Length; | |
if (curr >= len) continue; | |
int start = (i + 1) % len; | |
int end = (i + extraMinutes.Length - curr) % len; | |
if (start <= end) | |
tree.Modify(start, end - start + 1, 1); | |
else | |
{ | |
tree.Modify(start, len - start, 1); | |
tree.Modify(0, end + 1, 1); | |
} | |
} | |
return tree; | |
} | |
/* | |
* Build tree myway - range is determined from two portions - left and right | |
* Test case: | |
* 3 | |
* 1 0 0 | |
* currentExtraMinutes == 0, the node i is counted twice. | |
*/ | |
private static SegmentTree BuildTree(int n, int[] extraMinutes) | |
{ | |
var tree = new SegmentTree(n); | |
for (int i = 0; i < n; i++) | |
{ | |
int currentExtraMinutes = extraMinutes[i]; | |
int len = extraMinutes.Length; | |
if (currentExtraMinutes >= len) continue; | |
int currentNode = i; | |
int lastNode = len - 1; | |
int firstNode = 0; | |
int leftPart = currentNode; | |
int rightPart = lastNode - currentNode; | |
if (leftPart > currentExtraMinutes - 1) | |
{ | |
// add range - 0 -> leftPart - curr | |
int start = firstNode; | |
int end = currentNode - currentExtraMinutes; | |
tree.Modify(start, end - start + 1, 1); | |
} | |
if (rightPart > currentExtraMinutes - 1) | |
{ | |
// add range - i + curr -1 -> len | |
int start = (currentNode + currentExtraMinutes); | |
if (currentExtraMinutes == 0) | |
start++; // avoid duplicate adding - fix the bug | |
int end = lastNode; | |
tree.Modify(start, end - start + 1, 1); | |
} | |
} | |
return tree; | |
} | |
public class SegmentTree | |
{ | |
private readonly int[] tree; | |
public SegmentTree(int size) | |
{ | |
tree = new int[size * 2]; | |
} | |
/* | |
* code review: Dec. 10, 2016 | |
* from leaf node, | |
* left % 2 == 1 => ? | |
* | |
*/ | |
public void Modify_old(int start, int count, int value) | |
{ | |
int size = tree.Length / 2; | |
int left = start + size; | |
int right = start + count + size; // open border | |
for (; left < right; left >>= 1, right >>= 1) | |
{ | |
if (left % 2 == 1) tree[left++] += value; | |
if (right % 2 == 1) tree[--right] += value; | |
} | |
} | |
/* | |
* Segment Tree code review: | |
* | |
*/ | |
public void Modify(int start, int count, int value) | |
{ | |
int size = tree.Length / 2; | |
int left = start + size; | |
int right = start + count + size; // open border | |
for (int i = left; i < right; i++) | |
{ | |
tree[i] += value; | |
} | |
} | |
/* | |
* code review: Dec. 10, 2016 | |
* Find the leaf node, leftmost one | |
* | |
*/ | |
public int Query(int index) | |
{ | |
int i = index + tree.Length / 2; | |
return tree[i]; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment