### computerbox's blog

By computerbox, history, 4 years ago, translation,

Hello everyone ! Let's discuss problems here . How to solve Problems: Find the Radio Operator, Morse Code , WoodCut ?

• +32

 » 4 years ago, # |   +80
 » 4 years ago, # |   0 Find the radio operator:Let's make 2 queries from the point (-V, -V) where V > 1000 (we choose V = 5000): one where we point the antenna to right and another one with antenna pointing up.If we note with f1 and f2 the angles defined in the statement, we observe that both f1 and f2 are less than 90 degrees and their sum is exactly 90 degrees. By dividing the two equations that we obtain after reading the values, we find the value of tan(f1) (as R is the same for both queries). Now we know that the radio station must be on a line containing the point (-V, -V) and having a known angle.Repeat the process with point (-V, V) and antenna pointing down and to the right and you get another line. The radio station is the intersection of these lines.
 » 4 years ago, # |   0 Morse code:Calculate dp[i] the minimum number of errors such that the suffix of the signal starting at position i represents a valid text formed by words from the dictionary (so there is a word starting at this position).If we fix the first word, we can uniquely identify the position that the next word should start and we can also check if that word can start at position i (just check that the groups of '-' and '+' are the same and that the absolute difference between the corresponding ones from the signal and from the word is at most 1). If the check is done in complexity O(len(word)), then dp[i] can be calculated in complexity O(sum_len(words)).To find the lexicographic smallest answer, pick the lexicographic smallest word (that minimizes the number of errors) at each step.To ease our implementations, we represented both the words and the signal as vector of pairs (char, count) and written the dynamic directly on this.
•  » » 4 years ago, # ^ |   0 thank you cristian1997 !
 » 4 years ago, # |   0 How to solve in Div1: 8 Text Editor 5 Loggers Inc. 2 Antiwaist
•  » » 4 years ago, # ^ |   0
 » 4 years ago, # | ← Rev. 2 →   +10 So, how to do 8 (Text editor) without banging the head against a wall trying to squeeze the solution in both TL and ML?
•  » » 4 years ago, # ^ |   0 I'm wondering the same thing (just from the side that was not able to squeeze it in TL)We encoded the state like: current permutation: $8!$ cursor position: 9 state of the editor: 3 ( with clipboard data OR shift-pressed OR none) size of clipboard data OR where was shift pressed: 9 Then ran dijkstra on top of that graph with transitions computed in $O(1)$. Overall complexity was $O(3 \cdot n! \cdot n^2 \cdot \log(3 \cdot n! \cdot n^2 ))$That was not enough to pass TL.
•  » » » 4 years ago, # ^ |   +10 We had the same solution. We squeezed it in TL by replacing the priority queue in Dijkstra with an array of $100\,000$ vectors (since we could convince ourselves that the required time should never exceed $100\,000$). This gets rid of the $log(3 \cdot n! \cdot n^2)$ factor and is just enough to pass. Of course, you still need to optimize a bunch of other stuff... We had to reimplement the solution from scratch since the first code was just a bit too slow.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Idk, just precalc all transitions and do 0-k bfs instead of dijkstra, works just over 1.5 sec:CodeI even have $O(n! n^{3})$ transitions, and to calculate each transition I used $O(n)$ more, so complexity is $O(n! n^{4})$
 » 4 years ago, # |   0 Editorial on Russian language https://codeforces.com/blog/entry/84262 . I guess on Google Translate ,it will be ok.
 » 4 years ago, # |   0 I did not think O(n^2) would get accepted for #6. I think we can solve single cache in O(n) and unbounded cache in O(nlogn). Did anyone also do so?
•  » » 4 years ago, # ^ |   +8 Actually, I did implement the O(N^2) DP and it worked in ~0.4s.