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

5000 -> 143882158
4856 -> 977177749
4257 -> 755678035
4000 -> 757298829
3500 -> 997776483

плиз напишите решение задачи 1877. Велосипедные коды
please help piton 3.6

Edited by author 17.12.2018 19:09

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

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

Edited by author 29.05.2020 13:26

Edited by author 29.05.2020 13:26

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

Could anyone help me with 17th test?

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?

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.

I can get the right answer of 50 500,but I can't AC the second test..What's up? What's the data?