Before contest

Codeforces Round #687 (Div. 1, based on Technocup 2021 Elimination Round 2)

23:26:47

Register now »

Codeforces Round #687 (Div. 1, based on Technocup 2021 Elimination Round 2)

23:26:47

Register now »

*has extra registration

Before contest

Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2)

23:26:46

Register now »

Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2)

23:26:46

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3687 |

2 | ecnerwala | 3600 |

3 | Benq | 3503 |

4 | ksun48 | 3421 |

5 | Um_nik | 3412 |

6 | Radewoosh | 3382 |

7 | maroonrk | 3323 |

8 | Itst | 3239 |

9 | apiadu | 3238 |

10 | ko_osaga | 3232 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 205 |

2 | SecondThread | 199 |

3 | Monogon | 195 |

4 | vovuh | 190 |

5 | Um_nik | 186 |

6 | pikmike | 185 |

7 | antontrygubO_o | 184 |

8 | Ashishgup | 181 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

**NOT** interactive

I was doing some problems of SlavicG and ssense's Unofficial Div 4 round. This problem was causing me with some weird Idleness Limit Exceeded. 99582268. After being Sherlock Holmes for a few minutes, I fixed the problem and 99582838 is AC. The weird thing is the $$$dbg$$$ macro. After commenting all of the dbg's out, it got AC. I am wondering why is this. Shouldn't it be outputted to the standard error stream? Why am I getting this idleness limit exceeded?

If you ever used AtCoder, you should know about its many features. One of the features is running your program on all of the testcases and then displaying how much WA's, how many AC's, how many RE's, etc. I think that this feature should be implemented in Codeforces. You can have the option to turn it on or turn it off.

I recently saw Errichto use this feature of AtCoder to check if his thought process is right before trying to optimize the code. I think that he was trying to do Problem E from AtCoder Grand Contest 48. I also believe that many people like Errichto would also want to see if their thought process is right before continuing on to optimize the code.

Please share your thoughts in the comments below.

```
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define ll long long
int modmul(int a, int b, int M) {
long long ret = a * b - M * (int)(1.L / M * a * b);
return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
int modpow(int b, int e, int mod) {
int ans = 1;
for (; e; b = modmul(b, b, mod), e /= 2)
if (e & 1) ans = modmul(ans, b, mod);
return ans;
}
bool prime(int n) {
if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
int A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
s = __builtin_ctzll(n-1), d = n >> s;
for (int a : A) { // ^ count trailing zeroes
int p = modpow(a%n, d, n), i = s;
while (p != 1 && p != n - 1 && a % n && i--)
p = modmul(p, p, n);
if (p != n-1 && i != s) return 0;
}
return 1;
}
int pollard(int n) {
auto f = [n](int x) { return modmul(x, x, n) + 1; };
int x = 0, y = 0, t = 30, prd = 2, i = 1, q;
while (t++ % 40 || __gcd(prd, n) == 1) {
if (x == y) x = ++i, y = f(x);
if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q;
x = f(x), y = f(f(y));
}
return __gcd(prd, n);
}
vector<int> factor(int n) {
if (n == 1) return {};
if (prime(n)) return {n};
int x = pollard(n);
auto l = factor(x), r = factor(n / x);
l.insert(l.end(), begin(r), end(r));
return l;
}
struct custom_hash { // Credits: https://codeforces.com/blog/entry/62393
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t a) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(a + FIXED_RANDOM);
}
template<class T> size_t operator()(T a) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
hash<T> x;
return splitmix64(x(a) + FIXED_RANDOM);
}
template<class T, class H> size_t operator()(pair<T, H> a) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
hash<T> x;
hash<H> y;
return splitmix64(x(a.f) * 37 + y(a.s) + FIXED_RANDOM);
}
};
template<class T, class H> using umap = unordered_map<T, H, custom_hash>;
template<class T> using uset = unordered_set<T, custom_hash>;
int n;
vector<pair<int, int>> a;
vector<set<int>> hld;
umap<int, int> cnt;
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
a.resize(n);
for(auto& i: a) {
cin >> i.first >> i.second;
}
for(int i = 0; i < n; ++i) {
vector<int> hld1, hld2;
hld1 = factor(a[i].first);
hld2 = factor(a[i].second);
set<int> se;
for(auto& j: hld1) {
se.insert(j);
}
for(auto& j: hld2) {
se.insert(j);
}
hld.emplace_back(se);
}
for(auto& i: hld) {
for(auto& j: i) {
++cnt[j];
}
}
for(auto& i: cnt) {
if(i.second == n) {
cout << i.first << "\n";
return 0;
}
}
cout << -1 << "\n";
}
```

The factorization algorithm is taken from KACTL, same with the Miller-Rabin and the modmul and the modpow.

If we take each pair and then prime factorize each of the numbers in the pair. Then take the union of those prime factors and then for each union, we count the number of primes and if there are $$$n$$$ of those primes in the pairs then, at least one number from each pair will be divisible by that number.

Since the prime factorization is $$$O(n^{\frac{1}{4}})$$$, and we are doing $$$O(n)$$$ of them and there are at most 30 prime factors for a number $$$\le 2 \cdot 10^{9}$$$, the complexity is about $$$O(n \cdot n^{\frac{1}{4}})$$$ or $$$O(n^{\frac{5}{4}})$$$. Also, I didn't add in the set's insert which works in $$$O(log(n))$$$, but I don't think that that would matter much. This complexity should suffice for $$$n \le 150,000$$$

Please let me know if there is a section where it is not clear. Thanks for reading the blog.

The title prolly ain't clear at all. You are given a string $$$s$$$ and a string $$$t$$$. For every substring $$$s$$$ of length $$$|t|$$$, you are to find the number of different characters between the substring of $$$s$$$ and $$$t$$$ in $$$O(n \cdot log(n))$$$ or less. It is guaranteed that $$$|t| \le |s|$$$.

Example: s: abac t: ag output: [1, 2, 1]

s: adfjaasd t: asdf output: [3, 4, 4, 4, 3]

Don't just downvote, tell me where I should improve or what the answer to my question is. Pls, my contribution is already too low (-75).

Problem statement: 1196D2 - RGB Substring (hard version)

I very much like $$$cin » $$$ but want to have this fast reading integers function. How to do it? For example, I want to input multiple integers in this $$$cin » a » b » c;$$$ but the reading of integers is using the comment above.

I tried this but it didn't work.

```
istream & operator >> (istream& os, int x) {
bool minus = false;
int result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus = true; else result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
if (minus)
os >> -result;
else
os >> result;
return os;
}
```

But I got this error

```
error: ambiguous overload for 'operator>>' (operand types are 'std::istream' {aka 'std::basic_istream<char>'} and 'int')
124 | os >> result;
| ~~ ^~ ~~~~~~
| | |
| | int
```

KACTL ModMul. It says that it runs around 2x faster than naive

```
(__int128_t)a * b % M
```

When I ran my benchmarks with -O2, the results were similar. Am I mistaken?

Take a look at these two submissions

The only difference between these two was that the data types for variables $$$n, k$$$, and vectors $$$a, hld1, hld2$$$. Instead of having them be long doubles, they were int. Now, look at the execution time! The difference is huge! The one with the ints has around 12 times better time than the one with long doubles! I knew that working with floats led to higher constant factors but didn't know that it would be that big.

You are given a number $$$n$$$ and a number $$$m$$$ and an array $$$a$$$ of $$$n$$$ numbers and 1 type of query. All of the numbers below are 0 based indexing.

1) Given 3 numbers, $$$l$$$, $$$r$$$ , $$$x$$$. You add all the numbers from l to r(inclusive) by x. For example if the initial array was {5, 4, 3, 9, 2} and the query was {0, 2, 5} then the array would become {10, 9, 8, 9, 2}. Also, print the array.

After each query, store the new array as array $$$a$$$.

At the end print the array a.

m describes the number of queries being asked.

Example:

```
4 3
1 9 2 2
2 2 3
0 3 5
2
Output:
10
6 14 10 7
```

Should be less that $$$O(n)$$$

You are given a number $$$n$$$ and a number $$$m$$$ and an array $$$a$$$ of $$$n$$$ numbers and 2 types of queries. All of the numbers below are 0 based indexing.

1) Given 3 numbers, $$$l, r, x$$$. You add all the numbers from $$$l$$$ to $$$r$$$(inclusive) by $$$x$$$. For example if the initial array was {5, 4, 3, 9, 2} and the query was {0, 2, 5} then the array would become {10, 9, 8, 9, 2}

2) Given 1 number $$$y$$$, output $$$a[y]$$$. This should be self explanatory.

At the end print the array $$$a$$$.

$$$m$$$ describes the number of queries being asked.

Example:

```
4 3
1 9 2 2
2 2 3
0 3 5
2
```

Output:

```
10
6 14 10 7
```

Should be less that $$$O(n^{2})$$$

I see this article and at the bottom, it says that modulus operators are expensive so they implemented a slightly faster version of Euclidean Algorithm. Why not make a more efficient mod?

```
int mod(int a, int b) { // computes a % b;
return (a - b * (a / b));
}
```

I know that set doesn't contain duplicates, but it sorts the elements. I want a data structure that doesn't sort the elements and doesn't contain duplicates.

For example if the data structure contains ints,

Input: 5 4 1 2 5 4 9

Elements in data structure

5 4 1 2 9

Please help.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/28/2020 10:38:14 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|