Общий форумСпасибо, будем знать Edited by author 25.09.2023 01:13 tell me the hint, i want to solve this problem. Always extract squares that you know can be valid to extract at that point in time. Also, another hint, even if you extract a square, you could reuse its grid to extract other squares, and the characters under the extracted square's grid can be anything you want them to be. First off in your text editor switch from utf8 to cp437 (for example I use vscode and there's a tab in the bottom left that I can click to change the encoding). Only then, go to another comment on this problem (template for msvs 2010) and copy-paste the table from there. For anyone struggling with this problem, here's how I did it: segment trees with lazy updates for the dp O(sqrtN) updates for the string itself (the logN retrieval with the segment trees instead of the O(1) with the sqrt blocks retrieval was too big of a hog it seems, maybe I messed something up) Manacher for the edge cases and dp[i] = dpEven[i] + dpOdd[i] from Manacher So I used the segment trees to do most of the work, and then for the edge cases I used Manacher, so on average I'd get O(sqrt(N) + log(N) + K) for updates and O(log(N) + K) for queries. Does anyone have a less ugly solution? My source code is aroung 15kb (although I used long names for clarity) and around 550 lines long. Also I've seen people's code run a lot faster, under a second (mine ran in 2.7 s) and I was wondering how they did it. Thanks! rt TL 11 I did it with sqrt(N) blocks, and got tl on 11 too How it can be solved with disjoint sets? Anybody help me please. This is my mail: quvondiq.otajonov.tuit@gmail.com. I'll wait for answer! Thanks for advance!!! ??????? I know it's an old thread, but it's how I solved it. So spoilers and all. if l->r is even, then s[r] and s[l - 1] have the same parity (where s[x] is the partial sum of bits from 1 to x) if l->r is odd, then they have opposite parities We add l-1 and r to a dsu. So a dsu is just a tree of all dependencies, no matter if odd or even (see how I differentiate between the two below). I used dsu with an added property that is only available for dsu roots: sons[root][0] is the "representative" of all elements that have the same parity of root, sons[root][1] is the "representative" of all elements that have opposite parity of root. Anything else besides the root->representative edges will only have 0s, codifying that entire subtrees have the same parity. So first off when you do find, I haven't really bothered with path compression. And instead of just saying what is the dsu root for a node, you also say which side it came from (0 if it came from sons[root][0] and 1 for sons[root][1]) - so (0, root) means it has the same parity as root and (1, root) means it has opposite parities. So now when you do union, you first have a small case, if the two nodes are already in a tree, you have to verify that the sides they're on match the parity of s[r] - s[l - 1] otherwise you stop at the current test. Now, if they're not yet united, you have 4 cases that are basically just 2: if l-1 and r are on the same side of their respective dsus with s[r]-s[l-1] even, then this is one case if l-1 and r are on opposite sides of their respective dsus with s[r]-s[l-1] odd, then this is one case(identical with the previous one) And of course you have the opposite cases as well, which form another case you have to treat separately. So now you just have to move the left and right sides from one tree to the other so that they all match up correctly. You can do this however you like, just make sure that the property we've added to the dsu (sons is a unique property of the root of a dsu) is kept. Here's how I did it (let's treat just the case where l->r is even and l-1 and r are on the 0 sides of their respective dsus), and let's say l - 1 has root T1 and r root T2, we want to join the tree T2 into tree T1. T1 T2 0/ \1 0/ \1 a b c d | | | | A B C D (l - 1 comes from A, r comes from C) a, b, c, d are representatives of A, B, C, D. And this is how the finalized tree will Look:
T1 0/ \1 T2 d 0|\0 |\ a c D b | | | A C B As you can see, since T2 is no longer a root, sons[T2] becomes redundant since it's gonna have 0's on the edges which is what keeps the property. For the opposite case, you do something similar, just that T2 will be on the 1 side of T1 and you play around with the representatives. Of course there are some cases where some roots don't yet have both/any sons, but it's not too ugly to deal with them. Also for implementation, I normalized values but I think you could just use unordered_map/map. I've solved this problem using set (so a bst). I've thought of a method of using a segment tree. How would you come about using a heap, I'm curious? It's ambiguous to me at least whether you can change the order of the sequence or not. like {a3, a1, a5, a7}, {a6, a2, a4, a8} Read the problem again. Set is given. so ordering is not taken into account. However WA34 now :( n = int (input()) cnt = 0 for i in range (n+1) : a = input() if a[-4:] != "+one" : cnt += 1 if a[-4:] == "+one" : cnt += 2 if cnt != 11 : print ((cnt * 100) + 200) if cnt == 13 : print ((cnt * 100) + 300) Runtime error,what's wrong? Edited by author 02.03.2022 22:29 To solve the problem, you can use the inclusion-exclusion principle. The intersection of two arithmetic progressions can be found by solving the Diophantine equation. If the difference in the new progression is too large, you can replace it with n+1. It should be noted that the first element of the new progression must be no less than the first elements of the intersecting progressions. You should also consider possible type overflows. My implementation uses int128, but I think it is possible to solve it using int64. Edited by author 15.07.2024 15:28 In the example outputs there's no third line containing the geometric progression like the problem states there should be. WA#29 ant hint for this tricky test case? I make lots of random cases but still no help :-( For this particular problem I think the input size matters. It allows getting 0.001 sec on every test after few retries. But it makes it hard to get 0.001 sec on all tests in a single try. When K = 1 , removed a single cell from line? If that right, K = 1 very simple case: n1 % 2 = 0 lost, n%2 =1 win position (with index=1). For K= 2, seems there only 2x2 rectangle Bob is win :) Try 12 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 1 9 9 10 10 11 11 12 2 6 there are 15 ms sols on the status?? so I guess there is O(log) maybe constraint is too small,and there need another version... There O(10^6) solution :) See min(row,col) <= 10^6 The test case contains some unexpected symbols, I don't sure which one, but if you're trying read line by yourself, you're quite likely to get Output limit exceeded. Just try below code to read from stdin BufferedReader bis = new BufferedReader(new InputStreamReader(System.in)); String line = bis.readLine(); If you are using C# and running out of memory somewhere at test 36 think how to gracefully call the GC because the heap is full of strings u read from console. Thanks a lot. I thought that I need to use some other algorithm, because I just created a dictionary with the bill key and value counter++ then did sorting through the Linq and it's definitely inefficient, but in I still succeeded. I inserted a GC.Collect() for every 1000 iterations of reading and I passed all the tests. Edited by author 24.10.2021 18:54 Thank you, i get tired of this problem <3 try to figure out how sorting in Japanese differs from regular sorting, there really isn’t such a big difference, but there will also be one trick with which you will need to suffer |
|