Show all threads Hide all threads Show all messages Hide all messages |

binary search | Anwar | 1486. Equal Squares | 5 Jun 2020 16:06 | 2 |

Why 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 left-upper 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. |

Tests | FATNOT | 1918. Titan Ruins: Artful Manipulations | 5 Jun 2020 12:35 | 1 |

Tests **FATNOT** 5 Jun 2020 12:35 5000 -> 143882158 4856 -> 977177749 4257 -> 755678035 4000 -> 757298829 3500 -> 997776483 |

памагите help | Богдан | 1877. Bicycle Codes | 5 Jun 2020 12:27 | 2 |

плиз напишите решение задачи 1877. Велосипедные коды please help piton 3.6
*Edited by author 17.12.2018 19:09* Not piton, python ;) Я на Python решил (decide), а на плюсах(C++) то же решение не заходит(don`t work) |

(SPOILER) My solution | Alikhan Zimanov | 1713. Key Substrings | 5 Jun 2020 11:38 | 1 |

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. |

WA4? | Михаил | 2139. Experiment with Juice | 5 Jun 2020 01:14 | 2 |

WA4? **Михаил** 24 Apr 2020 16:42 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* |

My wrong solution got accepted | Nanami_chan | 1078. Segments | 4 Jun 2020 23:11 | 1 |

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* |

Hint | PrankMaN | 1101. Robot in the Field | 3 Jun 2020 22:55 | 1 |

Hint **PrankMaN** 3 Jun 2020 22:55 Solve with Python and use eval() to calculate boolean expression |

Is there actually an O(N^5) solution? | PrankMaN | 1452. Pascal vs. C++ | 1 Jun 2020 14:26 | 1 |

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? |

using sieve method in c++.. | Shuvro Chandra Das | 1086. Cryptography | 1 Jun 2020 10:48 | 1 |

#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[n-1]<<endl; } return 0; } |

Пишите краткое содержание в таких задачах | 👑OmegaLuL230👑 | 1700. Awakening | 30 May 2020 02:23 | 1 |

В задачах с условием, на прочтение которых уходит 10 минут (или более) предлагаю писать краткое содержание в форуме! |

WrongAnswer #28 | GOR ABELYAN | 2102. Michael and Cryptography | 29 May 2020 13:26 | 4 |

*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* |

Hint | Mickkie | 2132. Graph Decomposition. Version 2 | 29 May 2020 00:50 | 1 |

Hint **Mickkie** 29 May 2020 00:50 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 :) |

Some test cases | Smilodon_am [Obninsk INPE] | 2048. History | 27 May 2020 11:32 | 3 |

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* |

WA #17 | Lebedev_Nicolay[Ivanovo SPU] | 1774. Barber of the Army of Mages | 27 May 2020 01:33 | 3 |

WA #17 **Lebedev_Nicolay[Ivanovo SPU]** 29 Dec 2011 01:41 Could anyone help me with 17th test? Re: WA #17 **Lebedev_Nicolay[Ivanovo SPU]** 29 Dec 2011 02:08 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* Re: WA #17 **Toshpulatov (MSU Tashkent)** 27 May 2020 01:33 If use Dinis -> remember that Oriented Graph |

how to solve this problim with geometric way? | vnyemets | 1956. Fire Signals | 26 May 2020 12:19 | 2 |

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(N-1)/2 lines and compute the distance in O(N). A better solution is doing two-pointers 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 point-line 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* |

(to Admin) What correct answer for 1 2 2? 1 10 10? | maslowmw | 1114. Boxes | 26 May 2020 00:06 | 1 |

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* |

WA#13 | nirkhut | 1052. Rabbit Hunt | 24 May 2020 13:57 | 1 |

WA#13 **nirkhut** 24 May 2020 13:57 does anyone know what is this test? thanks |

Hint for checking if two segments are parallel | PrankMaN | 1927. Herbs and Magic | 24 May 2020 04:14 | 1 |

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. |

WA4 pls give test | Andrey Ladeyschikov | 2112. Battle log | 23 May 2020 16:43 | 4 |

You can shoot in dead player |

What's wrong with my Test 2? | Garin | 1036. Lucky Tickets | 23 May 2020 10:15 | 6 |

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* |