Solving problems in CodeForces usually never works out as expected somehow – if I tend to overestimate the problem, I am able to solve it within 10 minutes and if I underestimate it, I stay about 1 hour on a simple one.
Something similar happened today as well – I have taken a look at the second problem of round 410.
The problem looked a bit trivial:
Mike has n strings s1, s2, …, sn each consisting of lowercase English letters. In one move he can choose a string si, erase the first character and append it to the end of the string. For example, if he has the string “coolmike“, in one move he can transform it into the string “oolmikec“.
Now Mike asks himself: what is minimal number of moves that he needs to do in order to make all the strings equal?
The first line contains integer n (1 ≤ n ≤ 50) — the number of strings.
This is followed by n lines which contain a string each. The i-th line corresponding to string si. Lengths of strings are equal. Lengths of each string is positive and don’t exceed 50.
Print the minimal number of moves Mike needs in order to make all the strings equal or print - 1 if there is no solution.
From the very beginning I was quite sure what to do – simply to compare the strings in 3 nested loops and then to take the lowest score or -1 if it appears. However, it was not that easy, due to two things – first – I was ashamed to forget, that strings are given by reference and I lost some 15 minutes on that looking for my mistakes. The second error was where I lost most of the time. In my code I am using a function named GetMoveables, where I calculate the number of movements needed for String A to become String B, if possible. However, I have somehow not paid attention to the way the parameters were called. Thus, I was calling intRes = GetMoveables(liStr[i], liStr[k]); which was giving me wrong result in only one of the sample tests. I did not find the problem easily and I thought that I had made some kind of an error in the string comparison. However, after lots of printing on the console, I have managed to find it and the code passed all the tests from the first submission.
Here comes the code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; class CF002 { static void Main() { int intRes; int intTotal = int.Parse(Console.ReadLine()); List liStr = new List(); Dictionary<int,int> dictResult = new Dictionary<int,int>(); for (int i = 0; i < intTotal; i++) { liStr.Add(Console.ReadLine()); } for (int i = 0; i < liStr.Count; i++) { dictResult.Add(i, 0); for (int k = 0; k < liStr.Count; k++) { if (i != k) { intRes = GetMoveables(liStr[k], liStr[i]); dictResult[i] += intRes; if (intRes==-1) { Console.WriteLine(-1); return; } } } } Console.WriteLine(dictResult.Values.Min()); } public static int GetMoveables(string strA, string strB) { string a = new StringBuilder(strA).ToString(); string b = new StringBuilder(strB).ToString(); string strSmall; for (int i = 0; i < a.Length; i++) { if (a.Equals(b)) { return i; } else { strSmall = a.Substring(0, 1); a = a.Substring(1, a.Length-1); a = string.Concat(a, strSmall); } } return -1; } } |
Quite ok.