fork download 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Diagnostics;
  6.  
  7. namespace FindNumbers
  8. {
  9.     class Program
  10.     {
  11.         static void Main(string[] args)
  12.         {
  13.             var input = new List<int>();
  14.  
  15.             var rand = new Random();
  16.  
  17.             for (int i = 0; i < 7000; ++i )
  18.             {
  19.                 input.Add(rand.Next(100));
  20.             }
  21.  
  22.             Console.WriteLine("====== Standard =============================================================");
  23.             var sw = new Stopwatch();
  24.             sw.Start();
  25.             List<int> r1 = null;
  26.             for (int i = 0; i < 10; ++i)
  27.             {
  28.                 r1 = NumberFinder.FindNumbersStandard(input);
  29.             }
  30.             sw.Stop();
  31.             Console.WriteLine("Elapsed: {0}ms", sw.ElapsedMilliseconds);
  32.             Console.WriteLine("====== Fast =================================================================");
  33.             var sw2 = new Stopwatch();
  34.             sw2.Start();
  35.             List<int> r2 = null;
  36.             for (int i = 0; i < 10; ++i)
  37.             {
  38.                 r2 = NumberFinder.FindNumbersFast(input);
  39.             }
  40.             sw2.Stop();
  41.             Console.WriteLine("Elapsed: {0}ms", sw2.ElapsedMilliseconds);
  42.  
  43.  
  44.             if (r1.Count != r2.Count)
  45.             {
  46.                 Console.WriteLine("BUG - different number of results");
  47.             }
  48.             for (int i = 0; i < r1.Count; ++i)
  49.             {
  50.                 if (r1[i] != r2[i])
  51.                 {
  52.                     Console.WriteLine("BUG - count mismatch");
  53.                     break;
  54.                 }
  55.             }
  56.         }
  57.     }
  58.  
  59.     public class NumberFinder
  60.     {
  61.         public static List<int> FindNumbersStandard(List<int> input)
  62.         {
  63.             var res = new List<int>(input.Count * 2);
  64.  
  65.             for (int i = 0; i < input.Count; ++i)
  66.             {
  67.                 int current = input[i];
  68.  
  69.                 int numElementsLargerToTheRight = 0;
  70.                 int numElementsSmallerToTheLeft = 0;
  71.  
  72.                 for (int j = i + 1; j < input.Count; ++j)
  73.                 {
  74.                     if (input[j] > current) numElementsLargerToTheRight++;
  75.                 }
  76.  
  77.                 for (int j = i - 1; j >= 0; --j)
  78.                 {
  79.                     if (input[j] < current) numElementsSmallerToTheLeft++;
  80.                 }
  81.  
  82.                 res.Add(numElementsSmallerToTheLeft);
  83.                 res.Add(numElementsLargerToTheRight);
  84.                 //Console.WriteLine("input[{0}] = {1}, {2} smaller elements to the left, {3} larger elements to the right", i, current, numElementsSmallerToTheLeft, numElementsLargerToTheRight);
  85.             }
  86.  
  87.             return res;
  88.         }
  89.  
  90.         public static List<int> FindNumbersFast(List<int> input)
  91.         {
  92.             var res = new List<int>(input.Count * 2);
  93.  
  94.             var keyIndexMap = new Dictionary<int, List<int>>();
  95.  
  96.             int maxKey = -1;
  97.  
  98.             // find the list of all indices for each element in the array
  99.             for (int i = 0; i < input.Count; ++i)
  100.             {
  101.                 var current = input[i];
  102.                 maxKey = current > maxKey ? current : maxKey;
  103.                 List<int> indices;
  104.                 if (!keyIndexMap.TryGetValue(current, out indices))
  105.                 {
  106.                     indices = new List<int>();
  107.                     keyIndexMap[current] = indices;
  108.                 }
  109.                 indices.OrderedInsert(i);
  110.             }
  111.  
  112.             for (int i = 0; i < input.Count; ++i)
  113.             {
  114.                 var current = input[i];
  115.                 int numElementsLargerToTheRight = 0;
  116.                 int numElementsSmallerToTheLeft = 0;
  117.  
  118.                 for (int k = current + 1; k <= maxKey; ++k)
  119.                 {
  120.                     List<int> indices;
  121.                     if (!keyIndexMap.TryGetValue(k, out indices))
  122.                         continue;
  123.  
  124.                     int firstIndexBiggerThanCurrent = indices.FindPosition(i); 
  125.                      numElementsLargerToTheRight += indices.Count - firstIndexBiggerThanCurrent;
  126.                 }
  127.                 for (int k = current - 1; k >= 0; --k) 
  128.                 {
  129.                     List<int> indices;
  130.                     if (!keyIndexMap.TryGetValue(k, out indices))
  131.                         continue;
  132.                     int lastIndexSmallerThanCurrent = indices.FindPosition(i);
  133.                    numElementsSmallerToTheLeft += lastIndexSmallerThanCurrent;                    
  134.                 }
  135.  
  136.                 res.Add(numElementsSmallerToTheLeft);
  137.                 res.Add(numElementsLargerToTheRight);
  138.                 //Console.WriteLine("input[{0}] = {1}, {2} smaller elements to the left, {3} larger elements to the right", i, current, numElementsSmallerToTheLeft, numElementsLargerToTheRight);
  139.             }
  140.  
  141.             return res;
  142.         }
  143.     }
  144.  
  145.     public static class OrderedExtensions
  146.     {
  147.         public static void OrderedInsert(this List<int> @this, int item)
  148.         {
  149.             var index = @this.BinarySearch(item);
  150.             if (index < 0) index = ~index;
  151.             @this.Insert(index, item);
  152.         }
  153.  
  154.         // item should not be in the list as item is the index of current, 
  155.         // the binary search will return the first index which is bigger than item which is what we are after
  156.         public static int FindPosition(this List<int> @this, int item)
  157.         {
  158.             var index = @this.BinarySearch(item);
  159.             System.Diagnostics.Debug.Assert(index < 0, "broken");
  160.             return ~index;
  161.         }
  162.     }
  163. }
  164.  
Time limit exceeded #stdin #stdout 5s 35072KB
comments ()
stdin 
Standard input is empty
stdout 
====== Standard =============================================================
Elapsed: 4212ms
====== Fast =================================================================
Elapsed: 1347ms
https://ideone.com/ni51ah
language:
C# (gmcs 5.20.1)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!