Common BoardWhy use a binary search. How can we say that the value of the hash of 4x4 > 3x3 > 2x2 > 1x1? I don`t understand why to use binary search. plz, help me... Let's call a number k "good" if there are two same squares with side length k in the matrix. I claim that if k is good, then k  1 is good. Indeed, let's look at any pair of same squares with side length k. Now, let's take the leftupper square with side k  1 in each of them. Note that they will be equal, but still won't be in the same place in the matrix, so they will be a good pair of squares with side length k  1. We've just proved that if K is the side length of the optimal pair of squares, then k = 1, 2, ... , K are all good, while k = K + 1, K + 2, ... , min(n, m) are all bad. Hence, we can do binary search to find K. The only thing left is how to check for a given k whether there are two equal squares with side length k or not. This part can be done by using hashing. 5000 > 143882158 4856 > 977177749 4257 > 755678035 4000 > 757298829 3500 > 997776483 плиз напишите решение задачи 1877. Велосипедные коды please help piton 3.6 Edited by author 17.12.2018 19:09 Not piton, python ;) Я на Python решил (decide), а на плюсах(C++) то же решение не заходит(don`t work) My solution is based on string hashing. Let's say that the strings from the input are s[1], s[2], ... , s[n]. First, let's iterate over all possible lengths from 1 to 100 (since the maximal length of a string is 100). Let's fix some length "len" and create a vector "all" which will contain all possible hashes of substrings of length "len" of all the strings s[i]. Additionally, for each i from 1 to n create a vector a[i] which will contain the hashes of substrings of length "len" of only the string s[i]. Now, sort all the vectors we've created so that we could binary search on them. Finally, go through each i from 1 to n and then for each of the substrings of s[i], using binary search count the number of occurrences of its hash in the vector "all" and the vector a[i]. If these numbers are equal, then this substring occurred only in the string s[i] and can be used as a key substring. By changing the base and modulo of the hash, you can pass the WA caused by collision of hashes (I used p = 2313 and mod = 1000000123). The time complexity will be O(max_len * n^2 * log(n)), where max_len is the maximal length of a string. Please, give me some tests 3 100000.000 100000.000 100000.000 100000.000 100000.000 100000.000 100000.000 0.000 0 This one helped me a lot to figure out WA4 (spoiler: int64 overflow) Edited by author 05.06.2020 01:37 3 50 100 50 70 51 70 My accepted solution prints 1 2 While the correct answer should be 2 3 1 Edited by author 04.06.2020 23:13 Solve with Python and use eval() to calculate boolean expression I've tried to come up with solution from the story part of the problem, but the worst algorithm I came up with is O(N^4). Is there an O(N^5) algorithm? #include <bits/stdc++.h> using namespace std; #define MAX_SIZE 1000005 void SieveOfEratosthenes(vector<int> &primes) { bool IsPrime[MAX_SIZE]; memset(IsPrime, true, sizeof(IsPrime)); for (int p = 2; p * p < MAX_SIZE; p++) { if (IsPrime[p] == true) { for (int i = p * p; i < MAX_SIZE; i += p) IsPrime[i] = false; } } for (int p = 2; p < MAX_SIZE; p++) if (IsPrime[p]) primes.push_back(p); } int main() { int t; cin>>t; vector<int> primes; SieveOfEratosthenes(primes); while(t){ int n; cin>>n; cout<<primes[n1]<<endl; } return 0; } В задачах с условием, на прочтение которых уходит 10 минут (или более) предлагаю писать краткое содержание в форуме! Edited by author 29.05.2020 13:26 Edited by author 29.05.2020 13:26 Try to change this for (int i = 3; i <= Convert.ToInt32(Math.Ceiling(BigInteger.Log(n, 2))); i += 2) to this for (BigInteger i = 3; i * i <= n; i += 2) Btw, you do not need BigInteger here, long is enough. Edited by author 30.05.2020 21:39 After this you will receive TLE39, try to handle the case with two big multiplied prime numbers, for example 1000000007*1000000009. Edit: this is even easier, than I thought. Just change your for to for (BigInteger i = 3; i < 10000000; i += 2) Edited by author 29.05.2020 03:42 Edited by author 29.05.2020 03:42 This problem is easier than rating should be if you know the trick. Invariant: graph G is decomposable if and only if all the connected components of G has even number of edges. A tree is very easy to be decomposed. Creating a tree equivalent to each connected component will lead to the answer. Hope this help, Mick :) My accepted program gives below answers for tests: Test: 1919 1000000000 Answer: 0: 0 1: 427499181 2: 424999184 3: 147499717 4: 0 5: 0 6: 0 7: 0 8: 0 9: 0 10: 0 11: 0 12: 0 Test: 100000 2000000 Answer: 0: 0 1: 812251 2: 807500 3: 280250 4: 0 5: 0 6: 0 7: 0 8: 0 9: 0 10: 0 11: 0 12: 0 Have you used info that Gregorian calendar repeated for each 400 years? test: 9876 9876 answer: 0: 0 1: 1 2: 0 3: 0 4: 0 5: 0 6: 0 7: 0 8: 0 9: 0 10: 0 11: 0 12: 0 test: 1234567890 987654321012345678909876543210123456789 answer: 0: 0 1: 422222222232777777733972222221800000004 2: 419753086430246913536697530863777777784 3: 145679012349320987639206790123311111112 4: 0 5: 0 6: 0 7: 0 8: 0 9: 0 10: 0 11: 0 12: 0 Right or wrong? Edited by author 27.05.2020 11:35 Could anyone help me with 17th test? AC now. I forgot the following: when building flow graph we need to set capacity equal to 1 when edge is mage>time and capacity equal to 0 when edge is time>mage. Edited by author 29.12.2011 02:09 Edited by author 29.12.2011 02:09 If use Dinis > remember that Oriented Graph I really like geometric problems. The problem can be solved using LP, PCA, analysis. But how to apply computational geometry (convex hull) to the problem? The optimal line goes through two points; it's not some arbitrary line. This could lead to O(N^3) solution if you enumerate every of N(N1)/2 lines and compute the distance in O(N). A better solution is doing twopointers optimization for every point. For each point you have to sort all the other points according to their polar angle with the fixed point; and then computation of O(N) lines for a fixed endpoint takes linear time with two pointers. Complexity of this solution is O(N^2 log N). Just recall that pointline distance is given by the formula abs(a*X+b*Y)/sqrt(a*a+b*b) (as one of endpoints is treated as an origin there is no constant term in abs()). So you could group points (X,Y) into two groups: those that have a positive sign of (a*X+b*Y) and those that have a negative one — this is precisely what you need two pointers for. Then the answer for each line will be computed as (a*sumX_PositiveGroup + b*sumY_PositiveGroup  a*sumX_NegativeGroup  b*sumY_NegativeGroup)/sqrt(a*a+b*b). Edited by author 26.05.2020 12:21 Is it 6 for all where n=1 and a,b>0? Because my AC solution gives 9 (yes, I implement idea from forum). For test 1 10 10 my solution gives 121 0 x y xx yy xy Edited by author 26.05.2020 00:20 Edited by author 26.05.2020 00:20 does anyone know what is this test? thanks Since input numbers are integers, pseudovector product absolute value will be at least 1 if they aren't parallel, so you can compare it to 0.5 to have bigger margin for double precision error. You can shoot in dead player I can get the right answer of 50 500,but I can't AC the second test..What's up? What's the data? Maybe for test 2 3 answer 0 thanks very much for your advice Than you: for test 2 3 answer 0 > test 2 3 This test is not correct cause S must be even. Update: Sorry, S can be odd! And yes, this is the second test case. Edited by author 23.05.2020 10:20 Edited by author 23.05.2020 10:20 Edited by author 28.09.2007 16:34 
