Challenge Overview
Problem Statement  
DISCLAIMER:
There is a square board separated into NxN square cells. Rows of the board are numbered 0 to N1 (top to bottom). Columns are numbered 0 to N1 (left to right). Originally all cells of the board are empty. You are given a String S that contains N*N characters. You need to place its characters (in the same order as they go within the string) to board's cells according to the following rules:
In other words, you need to place the given string into the board so that it forms a Hamiltonian path. Once all characters are placed, we will calculate C  the number of connected components on the board. A connected component is a maximal (by inclusion) set of cells such that there exists a path between any two cells of this set. A path between X and Y is a sequence of cells that starts at X and ends at Y such that all cells (including X and Y) contain the same character and each two consecutive cells are adjacent (by side). Your goal in this task is to minimize the value of C. You will need to implement the method placeString. Its input is the string S. The return value must be an int[] containing N*N + 1 elements. First two elements are the row and the column where you place the first character. Each of the next N*N  1 elements should be the direction (relative to the current cell) where you place the next character. 0 means right, 1 means up, 2 means left and 3 means down. For each test case we will calculate your raw and normalized scores. If we were unable to receive solution from you (due to time limit, memory limit, crash, invalid return value, etc.), then both your raw and normalized scores are 0. Otherwise, the raw score will be equal to the value of C in your solution. The normalized score for each test is 1,000,000.0 * BEST / YOUR, where BEST is the lowest positive score currently obtained on this test case (i.e., considering the last submission from each competitor). Finally, your total score is equal to the arithmetic average of normalized scores on all test cases. Test cases are generated as follows. N is selected uniformly, at random, between 30 and 100. A parameter A (alphabet size) is chosen uniformly, at random, between 3 and 5. Each character in S is selected uniformly and independently, at random, as one of first A letters of English alphabet. Only lowercase letters are used. An offline tester/visualizer is available.  
Definition  
 
Notes  
  The time limit is 20 seconds (this includes only the time spent in your code). The memory limit is 1024 megabytes.  
  There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB.  
  Some information about hardware and compilers used for this match can be found here.  
  There are 10 example test cases and 100 full submission (provisional) test cases.  
Examples  
0)  
 
1)  
 
2)  
 
3)  
 
4)  
 
5)  
 
6)  
 
7)  
 
8)  
 
9)  

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2020, TopCoder, Inc. All rights reserved.