Общий форумIn my AC solution I didn't use the fact that "there is no substrings in the form xyxyx" anywhere. My program even assumes the answer in this problem can be "-1", but I guess there are no such testcases in this problem because of this advanced condition. So, could anybody tell me how this fact helps to simplify the solution? Or, maybe, anybody can prove or deny my hypotesis about "-1"? Thanks in advance! Well, I must admit the fact, that I didn't even notice this strange condition when I was trying to solve this problem, and now, I have passed all tests with simply using Depth First Search. In fact, if this condition holds, let x be 0 or 1 and let y be a null string, so there could not exist a substring with 3 consequent, and same characters. This could do good to the simplification of saying the word. So I guess that, when using this condition, we could not generate any "No solution" cases, so that solutions should exist. So, when using DFS, one could find some acceptable construction of the word easily. Yeah... I also don't understand a couple thing of the statement: Why they are restricting the answer to only 100 moves. Why they aren't asking the minimum number of operations. And finally, why there's the xyxyx restriction. I managed to find the minimum number of operations in O(N log N), so really, the statement just doesn't make any sense to me... I enjoyed the problem though I have always been interested in applied programming (since 9th grade), but less than an year ago I discovered a great hobby - solving competitive programming problems. After the 200th AC, I would say This Online Judge is great, and I wish everyone motivation and good luck! I've used this formula to solve this problem: a(n) = 2^(b(n)-1) + a(n - c(1+b(n))) b(n) = -1+floor(log(((n+0.2)*sqrt(5)))/log((1+sqrt(5))/2)); c(0) = 0, c(1) = 1, c(n) = c(n-1) + c(n-2) I don't want to live in this world anymore. wow!!!! you probably made an easy thing too complicated. Looks like you're using golden ratio to calculate Fibonacci Way too complicated. I solved entirely using bitwise operations and an array with the first 64 Fibonacci numbers. Why this problem has 175 difficulty? I thought it has very hard to implement solution, but to sovle it you should do what exactly said in staitment... It's harder if you have to do it with a minimum number of items in the generating set, but with this statement - I got a very fast AC with random number generation. New tricky tests have been added to the problem. All solutions have been rejudged. 152 authors (62% of all) lost their solved status for the problem. import java.util.Scanner; public class Task_2100 { public static void main(String[] args){ Scanner scr1 = new Scanner(System.in); Scanner scr2 = new Scanner(System.in); int n, counter; n = scr1.nextInt(); counter = n+2; while(n-- > 0){ String guest = scr2.nextLine(); String substring = "+"; if(guest.contains(substring)){ counter++; } } if(counter==13) { counter++; } System.out.print(counter*100); } } If you sort segments according to INCREASING length. Then you can consider all segments one by one consecutively. Find points belong to the current segment. For those points current segment is the answer. Because of the segments are sorted. From all suggested hints, this is the fastest way to do it. Initially I tried with trees, but I was getting TLE on #13. Finally I decided to use a map for the points (with key=point, value=index) It's a very convenient Data Structure, because it provides fast search for the nearest value (lower bound), and allows you to delete that point once its segment has been found. I tried without deleting it, but got TLE #14. Deleting each point from the map after finding it makes the map smaller after each iteration. Finally got an AC in 0.1 Unexpected result: the solution using z-function is O(n) but gives TLA on the 8th test. The solution doesn't pass so I will leave the code with it here. I'm wondering if it really doesn't pass the 8th test because it is too slow though is O(n), or if there's just some kind of error in my algorithm. vi ZFunction(string &p, string &s) { int n = (int) p.size(); vector<int> z(n + 1); for (int i = 0, l = 0, r = 0; i < n; ++i) { if (i <= r) z[i] = min(r - i + 1, z[i - l]); while (i + z[i] < n && p[z[i]] == s[i + z[i]]) ++z[i]; if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } return z; } .... vector<int> z_func = ZFunction(s1, s2); vector<int> z_func2 = ZFunction(s2, s1); for (int i = 0; i < n; ++i) { if (z_func[i] == n - i && z_func2[n - i] == i) { cout << i; return; } } cout << "-1"; Edited by author 13.04.2023 23:25 Edited by author 13.04.2023 23:25 Edited by author 13.04.2023 23:27 Check your "MAXN" constant I`m using vector of segments. Everything is pretty fast, All the tests I could think of work correctly. EDIT: Finally, got a pretty good AC - Time: 0.234, Memory: 5 032 KB. (The problem was that I was not monitoring for segments getting empty) Edited by author 12.04.2023 23:40 Дайте тесты, пожалуйста 7 6 -4 0 -1 -5 7 -10 Answer: 21 I firstly tried to solve it with Ford-Bellman algorithm, but got TL and could not make it pass. Then I found here https://e-maxx.ru/algo/min_cost_flow Levit algorithm, and it passed. A new constraint on the input added: “It is guaranteed that any two distinct intersection or touch points of the cutting circles lay at the distance of at least 10^-3.” The tests not satisfying this constraint were corrected or removed. Some new tests were added at the same time. The time limit was adjusted to 1 sec. All solutions have been rejudged. 23 authors lost, and 13 other authors gained the solved status for the problem. Im an idiot I wrote "Saturtay" instead Saturday Edited by author 10.04.2023 02:46 After some failed attempts with O(n)=n*n/2, finally I found an O(n)=n solution. In plain C, it took 0.09s and 1.5Mb. (just from curiosity tried the same with C# - 14MB used RAM :)) The arrays of X and Y coordinates can be sorted independently from each other. So basically, this input: 3 1 3 2 1 3 2 will have exactly the same result (which is 2) as 3 1 1 2 2 3 3 can you proof it? Assuming a (x1, y1), b (x2, y2), then the distance from c (x3, y3) to (x1, y1) and (x2, y2) is equivalent to the distance from (x1, y2) and (x2, y1) My bad accepted, best Go solution to date Edited by author 06.04.2023 19:36 Try this test: -10 -1 1 -1 8 1 -7 2 1 3 Answer: 14.38 who has ideas, what test it is? |
|