Hi, I collected the solutions for the problems of April Fools Day Contest 2023. Before the official editorial being posted, we can discuss about the problems here.
P/s: The editorial was published.
1812E - Not a Geometry Problem
# | User | Rating |
---|---|---|
1 | Radewoosh | 3759 |
2 | orzdevinwang | 3697 |
3 | jiangly | 3662 |
4 | Benq | 3644 |
5 | -0.5 | 3545 |
6 | ecnerwala | 3505 |
7 | tourist | 3486 |
8 | inaFSTream | 3478 |
9 | maroonrk | 3454 |
10 | Rebelz | 3415 |
# | User | Contrib. |
---|---|---|
1 | adamant | 173 |
2 | awoo | 166 |
3 | nor | 165 |
4 | SecondThread | 162 |
4 | maroonrk | 162 |
6 | BledDest | 161 |
6 | Um_nik | 161 |
8 | -is-this-fft- | 149 |
9 | Geothermal | 146 |
10 | ko_osaga | 142 |
Hi, I collected the solutions for the problems of April Fools Day Contest 2023. Before the official editorial being posted, we can discuss about the problems here.
P/s: The editorial was published.
I tried to submit NO
, but what we all need is to submit security
It's about the first $$$25$$$ contest ever, the $$$15^{th}$$$, $$$20^{th}$$$ and $$$21^{th}$$$ one was unrated.
The first test case has $$$3$$$ numbers, the second has $$$1$$$, and the third has $$$4$$$. Yes, they are following the order of number pi.
314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745
Take this string into your code and you will be fine. Multiply all number in a test and get the answer.
Just try number 0
.
The conjecture is called "Collatz Conjecture". After about $$$300$$$ — $$$400$$$ steps, a positive number will be decreased down to $$$1$$$.
1812E - Not a Geometry Problem
Just try number 0
again.
The statement says $$$10^6$$$, not $$$10^{-6}$$$.
The color of the image is #01722B
. Just copy the editorial for problem 1722B and submit.
The statement said the number are generated randomly, and $$$624$$$ is how we crack mt19937.
abcdefghijklmnopqrstuvwxyz
The letters bdfhklt
are taller, and gjpqy
have a "foot". Replace them with (
and )
. Check if the sentence is balanced or not.
We need to say something with Please
.
The first time I cannot participate officially in a Div.2.
Not long ago ToxicPie9 posted a blog explaining common mistakes in competitive programming and how to avoid them. I was greatly inspired by that post so I decided to write an episode on my own.
Today I will mention four topics that I learned why practicing Competitive Programming and I will also mention how to build them. Also, in most cases, I will give you a chance to find out what the hard part is before I reveal the culprit as I tried to make this blog interactive. The codes that I have used in this blog have been written in Python as it is the most powerful language for CP.
Definition:
A Segment Tree is a data structure that stores information about array intervals as a tree. This allows answering range queries over an array efficiently, while still being flexible enough to allow quick modification of the array. This includes finding the sum of consecutive array elements $$$a[l \dots r]$$$ , or finding the minimum element in a such a range in $$$O(\log n)$$$ time. Between answering such queries, the Segment Tree allows modifying the array by replacing one element, or even changing the elements of a whole subsegment (e.g. assigning all elements $$$a[l... r]$$$ to any value, or adding a value to all element in the subsegment).
So how to build a segment tree?
Using pip:
Basic usage:
from segment_tree import *
array = [3, 1, 5, 3, 13, 7, 2, 7, 2]
tree = SegmentTree(array)
t.query(1, 3, "sum") # 9
t.update(0, 10) # [10, 1, 5, 3, 13, 7, 2, 7, 2]
t.query(0, 8, "min") # 0
t.update(2, -1) # [10, 1, -1, 3, 13, 7, 2, 0, 2]
t.query(0, 2, "min") # -1
Update on range:
from segment_tree import *
array = [1, 2, 3, 4, 5]
t = SegmentTree(array)
t.update_range(0, 2, 6) # 6 6 6 4 5
t.update_range(1, 4, 2) # 6 2 2 2 2
t.query(0, 3, "min") # 2
Definition:
A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.
So how to build a Fenwick tree?
Using pip again:
Basic usage:
fenwick_tree = FenwickTree(n)
for x in range(n):
fenwick_tree.add(x, x + 1)
More functions:
from __future__ import print_function
from fenwick import FenwickTree
n = 10
print('Note: Indexing is 0-based.')
print()
print('*******************************************')
print('* Initialize FenwickTree and update ')
print('* frequencies one at a time. ')
print('*******************************************')
print()
fenwick_tree = FenwickTree(n)
for x in range(n):
fenwick_tree.add(x, x + 1)
print('*******************************************')
print('* Initialize FenwickTree using existing ')
print('* frequencies. ')
print('*******************************************')
print()
fenwick_tree = FenwickTree(n)
f = range(1, n + 1)
fenwick_tree.init(f)
print('*******************************************')
print('* Calculate and print sum of all ')
print('* frequencies ')
print('*******************************************')
print()
sum_all = fenwick_tree.prefix_sum(n)
print(sum_all)
print()
print('*******************************************')
print('* Calculate and print sum of frequencies ')
print('* 2 through 8. ')
print('*******************************************')
print()
sum_2_8 = fenwick_tree.range_sum(2, 9)
print(sum_2_8)
print()
print('*******************************************')
print('* Calculate and print frequencies 5 ')
print('* through 9. ')
print('*******************************************')
print()
for x in range(5, 10):
print(fenwick_tree[x])
print()
print('*******************************************')
print('* Retrieve and print all frequencies. ')
print('*******************************************')
print()
print(fenwick_tree.frequencies())
Definition:
This data structure provides the following capabilities. We are given several elements, each of which is a separate set. A DSU will have an operation to combine any two sets, and it will be able to tell in which set a specific element is. The classical version also introduces a third operation, it can create a set from a new element.
So how to build a Disjoint Set Union?
Yes, you are right! We are using pip again:
Basic usage:
>>> from disjoint_set import DisjointSet
>>> ds = DisjointSet()
>>> ds.find(1)
1
>>> ds.union(1,2)
>>> ds.find(1)
2
>>> ds.find(2)
2
>>> ds.connected(1,2)
True
>>> ds.connected(1,3)
False
>>> "a" in ds
False
>>> ds.find("a")
'a'
>>> "a" in ds
True
>>> list(ds)
[(1, 2), (2, 2), (3, 3), ('a', 'a')]
>>> list(ds.itersets())
[{1, 2}, {3}, {'a'}]
Definition:
A treap is a data structure which combines binary tree and binary heap (hence the name: tree + heap $$$\Rightarrow$$$ Treap).
More specifically, treap is a data structure that stores pairs $$$(X, Y)$$$ in a binary tree in such a way that it is a binary search tree by $$$X$$$ and a binary heap by $$$Y$$$. If some node of the tree contains values $$$(X_0, Y_0)$$$ , all nodes in the left subtree have $$$X \leq X_0$$$ , all nodes in the right subtree have $$$X_0 \leq X$$$, and all nodes in both left and right subtrees have $$$Y \leq Y_0$$$.
A treap is also often referred to as a "cartesian tree", as it is easy to embed it in a Cartesian plane.
So how to build a Disjoint Set Union?
Again, as I mentioned, Python is the most powerful language for CP, we will use pip again:
Basic usage:
>>> import treap
>>> t = treap.treap()
>>> import random
>>> for i in range(20):
... t[random.random()] = i
...
>>> list(t)
[0.011795687154763312, 0.0695864396266509, 0.15741892655439682, 0.18718082546304682, 0.1910965922423038, 0.22849105220538402, 0.276078590851345, 0.3166512089228003, 0.3456516881327997, 0.3543869818366584, 0.4022879538597536, 0.4519316126668157, 0.46329639459896466, 0.4873225275394878, 0.5866856381825849, 0.6403758625610735, 0.6936888466959068, 0.7843975080768091, 0.8888622013819216, 0.9047894146828958]
>>> t.find_min()
0.011795687154763312
>>> t.find_max()
0.9047894146828958
Although Python is the most powerful language in CP, there are some data structures that we cannot install through pip
like sparse table
or sqrt decomposition
. If such case, we should:
Develop a pip
package on your own. Since people, including me, are indiscriminately using C/C++
just for compiling speed, they don't know how powerful Python
is and just reject it while doing CP. This is why there are a lack of necessary libraries for Python
. Your contribution is priceless.
Implement you own library. If pip
does not solve the problem, you can just implement your own version. Whenever a contest starts, just copy and paste them in. Voila.
Convert the current problem to another problem using a library that is solvable by using pip
. This requires a lot of experience in Competitive Programming, since it is a hard job to do.
Give up Find another way to solve it, don't give up.
Thanks for reading the blog. Feel free to add more mistakes that are common in CP in the comment section.
See you on a later episode, friend!
P.S. Although this is mostly a joke post, I tried to be accurate about the facts and did not intentionally put incorrect information in it (which means you may treat it as a somewhat educational blog). It also aims to showcase some features of Python that helps you avoid some common CP mistakes in languages like C++.
Igorfardoc, Vladithur, Alexdat2000, gluchie, DeMen100ns, SPyofgame and me (spelling "thanh-chau-n-s-2") are delighted to invite you to participate in Codeforces Round #842 (Div. 2). This round will be rated for all participants with a rating lower than 2100.
Special thanks to:
Edit: there will be $$$2$$$ packages for two participants in Vietnam, the highest score and the luckiest. You have to set your region to Vietnam to be qualified.
The score distribution is $$$500-1000-1500-1750-2250-3250$$$.
Hope to see you in the final standings!
Editorial is out.
Congratulations to the winners:
Div.1+2 | Div.2 | |
---|---|---|
1 | arvindf232 | drizzlo |
2 | Hyperbolic | jiangly_fan_fan_fan_fan |
3 | drizzlo | BedzieMagikZa2Lata |
4 | jiangly | BeautifulChicken |
5 | Um_nik | AE-3803 |
And the first solver for each problem:
A | B | C | D | E | F | |
---|---|---|---|---|---|---|
Div.1+2 | dapingguo8 | tourist | youknowiknowyouknow | A_G | nok0 | jeroenodb |
Div.2 | celestialcoder | 1024mb | youknowiknowyouknow | MIOC69 | cmk666 | drizzlo |
Ladies and gentlemen, 2023 is near. Lots of things happened to us in 2022, both achievements and disappointments. This is just a list of what I have done and haven't yet in 2022, and my goals for 2023.
I'm just in the mood to write something, don't take it seriously.
Successful tasks:
What I haven't done:
My goals for 2023:
There may be many more things that should be on the lists, I'll add them later, as I cannot remember all of them.
Anyway, 2023 is near. Merry Christmas, and Happy New Year.
gluchie, DeMen100ns, SPyofgame and I are delighted to invite you to participate in Codeforces Round #812 (Div. 2).
Special thanks to:
The score distribution is 500-1000-1750-2000-2500-3000
Hope to see you in final standings!
UPD: We have a small gift for a Vietnamese participant who have the highest score, so if it is you, please DM me after contest. Good luck everybody!
UPD2: Editorial
UPD3: Congratulations to the winners!
Div.2:
Div.1 + 2:
In this blog I would like to share some of the code snippets that can shorten your time in future contests. Of course, I'll ignore the "international snippets"
#define SZ(a) (ll)a.size()
#define FOR(i,a,b) for (ll i=(ll)a; i<=(ll)b; i++)
#define f first
#define mp make_pair
#define s second
#define p pair
#define all(C) C.begin(), C.end()
Sometimes you may find typing the identical thing again and again is boring, this blog is about some method that a few people use to get rid of them (or just only me).
So, let's get started.
std::cin/std::cout
template<typename T> istream& operator>>(istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};
vector<int> a(10);
cin >> a;
cout << a << endl;
10 is just a random number. It works for any size of the vector.
std::pair
template<typename T1, typename T2> ostream& operator<<(ostream& out, const p<T1, T2>& x) {return out << x.f << ' ' << x.s;}
template<typename T1, typename T2> istream& operator>>(istream& in, p<T1, T2>& x) {return in >> x.f >> x.s;}
pair<int, int> a;
cin >> a;
cout << a;
template<typename T> using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template<typename T> using ordered_multiset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
ordered_set<int> OS;
ordered_multiset<int> OMS;
template<typename T> using matrix = vector<vector<T> >;
template<typename T> using rubik = vector<vector<vector<T> > >;
rubik<int> a; // instead of vector<vector<vector<int> > > a;
template<typename T> void Unique(T &a) {a.erase(unique(a.begin(), a.end()), a.end());}
vector<int> a;
Unique(a);
ll powermod(ll a, ll b, ll m)
{
if (b == 0) return 1;
ull k = powermod(a, b / 2, m);
k = k * k;
k %= m;
if (b & 1) k = (k * a) % m;
return k;
}
// Prime test for large numbers
bool isPrime(ull n, int iter = 5)
{
if (n < 4) return n == 2 || n == 3;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 0; i < iter; i++)
{
ull a = 2 + rand() % (n - 3);
if (powermod(a, n - 1, n) != 1) return false;
}
return true;
}
multiset<ll> LIS(vector<ll> A)
{
ll a = A.size();
multiset<ll> S;
multiset<ll>::iterator it;
FOR(i, 0, a - 1)
{
S.insert(A[i]);
it = S.upper_bound(A[i]);
if (it != S.end()) S.erase(it);
}
return S;
}
multiset<ll> LSIS(vector<ll> A) // a.k.a Longest Strictly Increasing Sequence
{
ll a = A.size();
multiset<ll> S;
multiset<ll>::iterator it;
FOR(i, 0, a - 1)
{
S.insert(A[i]);
it = S.lower_bound(A[i]);
it++;
if (it != S.end()) S.erase(it);
}
return S;
}
Some snippets are mine, some are taken from the internet. If you want to add some snippets on the blog, please let me know in the comment section.
You can read more about ordered_set and ordered_multiset here: https://codeforces.com/blog/entry/11080
Thanks for reading! Hope this can help you.
About 18 months ago I started to learn CP, from then I usually practice the problems 6 hours a day while listening to my favourite song via discord. I used the Maki discord bot:
The quality was good, but I cannot shuffle or pause the music, which is a bit uncomfortable for me. And I found out that every music bot out there is lack of some purpose, as they are premium features.
It is a fully-functional discord for playing music. And it does not just play music!
The music functions are all-free, as well as other functions, which is in developing. As my purpose is to make a free bot for everyone, there will be no premium features.
Closed
Closed
If you like the product, buy me a coffee via
4665849150760898
Sorry for my bad English, hope you will enjoy it.
From Hanoi with a little wind.
Best regards,
thanhchauns2
Hi everyone,
The story is, I published my proposion on 28th August 2021, and it haven't been any contributor attached to it yet. Since 8 months is a long time, I'm wondering some questions here:
How long did other authors have waited until some coordinators attached to their round?
Is the queue really long?
If there are any admin reading this, is my round rejected for some reasons? I have written for about ~20 problems, I would really sad if it is not in your plan.
The ID of the our contest is: 1303.
Thanks for reading.
UPD: It's now round Codeforces Round #812.
Hi, this is the first time I write such a blog like this. All is because of my excitement that for the first time I can solve all problems, not because I am worshiping myself or something. I know this is just a Div-3 contest, so there are many people who can solve it. But if you are stuck with some problems, feel free to read my solutions.
This is not an official editorial, so the solutions might not be the best of all solutions out there, so if you have something to discuss, feel free to leave something below. Thanks for all.
The first two numbers cannot be produced by a sum operation, so we have $$$2$$$ of $$$3$$$ numbers we must find. How to find the last one? Subtract these two from the largest one.
vector<ll> a(7);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
ll ttl = a[6];
cout << a[0] << ' ' << a[1] << ' ' << a[6] - a[0] - a[1] << '\n';
We need to create an empty answer string.
Starting from the first substring, for each substring follows, if the first character of it equals the last character of the currently answer string, add the last character, otherwise, append the whole string.
In the end, check if the answer string has the length n or not. If not, repeat the last character.
Be careful of the case we didn't add any whole substring.
ll n;
cin >> n;
string s = "";
ll h = 0;
FOR(i, 0, n - 3)
{
string t;
cin >> t;
if (s.empty() || t[0] != s.back())
{
s += t;
h = 1;
}
else s += t[1];
}
if (!h) s += 'a';
while(s.length() < a) s += s.back();
cout << s << '\n';
The most likely answer for each case is the gcd of all odd-indexed elements or the gcd of all even-indexed elements.
Our work now is to check if it is divisible by some "neighbor index" or not.
ll n;
cin >> n;
vector<ll> C(a);
for (auto &x: C) cin >> x;
ll g = 0;
for (ll i = 0; i < a; i += 2)
{
g = gcd(g, C[i]);
}
for (ll i = 1; i < a; i += 2)
{
ll t = gcd(g, C[i]);
if (t == g) g = 1;
}
if (g != 1)
{
cout << g << '\n';
return;
}
g = 0;
for (ll i = 1; i < a; i += 2)
{
g = gcd(g, C[i]);
}
for (ll i = 0; i < a; i += 2)
{
ll t = gcd(g, C[i]);
if (t == g) g = 1;
}
if (g != 1) cout << g << '\n';
else cout << 0 << '\n';
We need to optimize two things: the numbers we use in $$$k$$$ operations must be as large as possible, and the total result of $$$k$$$ operations must be as small as possible.
Thus, we will use $$$2k$$$ largest numbers.
ll a, k;
cin >> a >> k;
vector<ll> C(a);
for (auto &x : C) cin >> x;
REVERSE_SORT(C);
ll ttl = 0;
FOR(i, 0, k - 1)
{
ttl += C[i + k] / C[i];
}
FOR(i, k * 2, a - 1) ttl += C[i];
cout << ttl << '\n';
We have a system of equations, it goes like this:
If we add all of them, we will have something like:
Moreover, if we subtract two neighbor equations, for example, the first from the second equation, we will get something like this:
Using this we can calculate all numbers from $$$a_1$$$ to $$$a_n$$$. Of course, we will have to check the exceptions: $$$n*(n+1)/2$$$ is not divisible from the sum of all elements from $$$b$$$, or some $$$a[i]$$$ is non-positive.
ll n;
cin >> n;
vector<ll> b(n);
for (auto &x : b) cin >> x;
ll ttl = 0;
FOR(i, 0, n - 1)
{
ttl += b[i];
}
ll k = n * (n + 1) / 2;
if (ttl % k != 0)
{
cout << "NO" << '\n';
return;
}
ttl /= k;
vector<ll> ans(n, 0);
FOR(i, 0, n - 1)
{
ll x = (i + n - 1) % n;
ans[i] = (ttl + b[x] - b[i]) / n;
if (ttl + b[x] < b[i])
{
cout << "NO" << '\n';
return;
}
if ((ttl + b[x] - b[i]) % n != 0)
{
cout << "NO" << '\n';
return;
}
if (ans[i] == 0)
{
cout << "NO" << '\n';
return;
}
}
cout << "YES" << '\n';
printVector(ans);
cout << '\n';
If $$$x = y$$$, the answer is YES.
Else if $$$y$$$ is divisible by $$$2$$$, the answer is NO.
Else we have to check if the binary string $$$s$$$ of $$$x$$$ can convert into the binary string $$$t$$$ of $$$y$$$ or not, with $$$s$$$ we can convert into several "starting strings":
Itself.
Itself, with one extra '1' at the end.
Itself but erase all '0's at the end.
Itself, erase all '0's, reversed.
Clearly, the operation is to choose to keep the string or erase all the '0's at the end then add some '1's (maybe zero) to the beginning or the end of the string.
The work now is to check each case if we can obtain $$$t$$$ by adding '1's to the beginning or the end of the current string.
ll x, y;
cin >> x >> y;
if (x == y)
{
cout << "YES" << '\n';
return;
}
if (y % 2 == 0)
{
cout << "NO" << '\n';
return;
}
function<string(ll)> convert = [&](ll a)
{
string s = "";
ll n = 1;
while (a)
{
if (a & n) s += '1';
else s += '0';
if (a & n) a ^= n;
n <<= 1;
}
revrs(s);
return s;
}
string s = convert(x);
string t = convert(y);
function<bool(ll, ll)> check = [&](ll m, ll n)
{
FOR(i, m, n) if (t[i] == '0') return false;
return true;
};
function<void()> extract = [&]()
{
ll len = s.length();
FOR(i, 0, t.length() - 1)
{
if (i + len > t.length()) break;
if (t.substr(i, len) == s)
{
if (!check(0, i - 1) || !check(i + len, t.length() - 1)) continue;
cout << "YES" << '\n';
exit(0);
}
}
if (s.back() == '0') return;
revrs(s);
FOR(i, 0, t.length() - 1)
{
if (i + len > t.length()) break;
if (t.substr(i, len) == s)
{
if (!check(0, i - 1) || !check(i + len, t.length() - 1)) continue;
cout << "YES" << '\n';
exit(0);
}
}
revrs(s);
};
s = s + '1';
extract();
s.pop_back();
extract();
while (!s.empty() && s.back() == '0')
{
s.pop_back();
}
if (!s.empty()) extract();
cout << "NO" << '\n';
A simple way to solve: use two sets, both store vectors of four elements: the leftmost index of the segment, the rightmost index of the segment, how many numbers we take from it, and the distance between it and the next segment on the array. The first set will sort by the distance, the second set will sort by their first elements.
So how to use them? At first, merge the two arrays a and b into 1 array, let's call it TTL, use a map to save if we are currently have something or not. Then for each element, we will make a segment based on them: the leftmost and rightmost is their index, the number of elements we will take is either 1 or 0 depending on the map I described above, the distance will be the difference between it and the next number in TTL.
What will we do now? Solve the problem offline, for each query merge some of the segments which have the smallest "distance" into some other segments, so there will be no more than N merges. Since we are using sets, the complexity is O(NlogN).
To calculate the sum efficiently, use a prefix array.
ll a, b, q;
cin >> a >> b >> q;
vec(ll) ttl;
map<ll, ll> C, first, last;
ll cnt = 0;
FOR(i, 0, a - 1)
{
ll x;
cin >> x;
cnt += x;
ttl.pb(x);
C[x]++;
}
FOR(i, 0, b - 1)
{
ll x;
cin >> x;
ttl.pb(x);
}
SORT(ttl);
FOR(i, 0, ttl.size() - 1) last[ttl[i]] = i;
FORD(i, ttl.size() - 1, 0) first[ttl[i]] = i;
vector<ll> PREF = ttl;
FOR(i, 1, PREF.size() - 1) PREF[i] += PREF[i - 1];
set<vector<ll> > SORT_BY_DIST; // DIST -> TAKEN_ELEMENTS -> LAST_ELE -> FIRST_ELE
set<vector<ll> > SORT_BY_FIRST_ELEMENT; // FIRST_ELE -> LAST_ELE -> TAKEN_ELEMENTS -> DIST
FOR(i, 0, ttl.size() - 2)
{
if (ttl[i] == ttl[i + 1]) continue;
ll x = ttl[i];
SORT_BY_DIST.insert({ttl[i + 1] - ttl[i], C[x], last[x], first[x]});
SORT_BY_FIRST_ELEMENT.insert({first[x], last[x], C[x], ttl[i + 1] - ttl[i]});
}
SORT_BY_DIST.insert({(ll)1e18, C[ttl.back()], last[ttl.back()], first[ttl.back()]});
SORT_BY_FIRST_ELEMENT.insert({first[ttl.back()], last[ttl.back()], C[ttl.back()], (ll)1e18});
vec(ll) ans(q);
vector<p<ll, ll> > QUERIES(q);
FOR(i, 0, q - 1)
{
cin >> QUERIES[i].f;
QUERIES[i].s = i;
}
SORT(QUERIES);
function<ll(ll, ll)> SUB = [&](ll LAST, ll TAKEN)
{
ll l = LAST - TAKEN;
ll tmp = 0;
if (l == -1)
{
tmp += PREF[0];
l = 0;
}
tmp += PREF[LAST] - PREF[l];
return tmp;
};
for (auto x : QUERIES)
{
vector<ll> K = *SORT_BY_DIST.begin();
while (K[0] <= x.f)
{
vector<ll> Q = K;
revrs(Q);
vector<ll> T = *SORT_BY_FIRST_ELEMENT.upper_bound(Q);
vector<ll> P = T;
revrs(P);
SORT_BY_DIST.erase(K);
SORT_BY_DIST.erase(P);
SORT_BY_FIRST_ELEMENT.erase(Q);
SORT_BY_FIRST_ELEMENT.erase(T);
cnt -= SUB(Q[1], Q[2]);
cnt -= SUB(T[1], T[2]);
cnt += SUB(T[1], Q[2] + T[2]);
T[2] = Q[2] + T[2];
T[0] = Q[0];
SORT_BY_FIRST_ELEMENT.insert(T);
revrs(T);
SORT_BY_DIST.insert(T);
K = *SORT_BY_DIST.begin();
}
ans[x.s] = cnt;
}
printVector(ans);
cout << '\n';
Hope that my defines are not difficult to understand.
Yes, I'm a fan of neal_wu.
Hi everyone, recently I came across this problem in the problemset, which I have came up with a solution like this: 125580675, which turned out to be RTE on test 7 in the system tests. I managed to copy the test to run and debug it locally, but it gave a correct answer and didn't help me anything.
The #7 test looks like this:
? - ? + ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? - ? = 57
My solution on local IDE output this solution:
Possible
57 - 40 + 57 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 = 57
For everyone who is reading this, excuse me, can you help me find the bug? I couldn't find it however I try.
Thank you so much for reading this! Hope you have a great standing in the next contests ^_^
I just want to share something to community, after I found this problem in the problemset (which the answer cannot be display as long long integer). Here is my class to calculate on strings (including add, substract, multiply, divide (as two strings), modulo and take gcd, I will add bitwise operators later if possible).
Hope you will find it useful. If you find this incomplete, I would love to read any feedback.
class STRO
{
public:
bool bigger(string a, string b) // check if a is strictly bigger than b or not
{
if (a.length() > b.length()) return true;
if (a.length() < b.length()) return false;
for(int i = 0; i < a.length(); i++)
{
if (a[i] > b[i]) return true;
else if (a[i] < b[i]) return false;
}
return false;
}
string add(string str1, string str2) // add strings, took this from geekforgeeks
{
if (str1.length() > str2.length())
swap(str1, str2);
string str = "";
int n1 = str1.length(), n2 = str2.length();
int diff = n2 - n1;
int carry = 0;
for (int i=n1-1; i>=0; i--)
{
int sum = ((str1[i]-'0') + (str2[i+diff]-'0') + carry);
str.push_back(sum%10 + '0');
carry = sum/10;
}
for (int i=n2-n1-1; i>=0; i--)
{
int sum = ((str2[i]-'0')+carry);
str.push_back(sum%10 + '0');
carry = sum/10;
}
if (carry) str.push_back(carry+'0');
reverse(str.begin(), str.end());
while(str.size() > 1 && str[0] == '0') str.erase(0, 1);
return str;
}
string sub(string str1, string str2) // substract strings, also from geekforgeeks
{
if (bigger(str2, str1)) swap(str1, str2);
string str = "";
int n1 = str1.length(), n2 = str2.length();
reverse(str1.begin(), str1.end());
reverse(str2.begin(), str2.end());
int carry = 0;
for (int i = 0; i < n2; i++)
{
int sub = ((str1[i] - '0') - (str2[i] - '0') - carry);
if (sub < 0) {
sub = sub + 10;
carry = 1;
}
else
carry = 0;
str.push_back(sub + '0');
}
for (int i = n2; i < n1; i++)
{
int sub = ((str1[i] - '0') - carry);
if (sub < 0) {
sub = sub + 10;
carry = 1;
}
else
carry = 0;
str.push_back(sub + '0');
}
reverse(str.begin(), str.end());
while (str.size() > 1 && str[0] == '0') str.erase(0, 1);
return str;
}
string mul(string A, string B) // multiply strings
{
reverse(A.begin(),A.end());
reverse(B.begin(),B.end());
string C;
C.resize(A.length() + B.length(),'0');
for (int i = 0; i < A.length(); i++)
{
int c = 0;
FOR(j, 0, B.length()-1)
{
c += ((A[i] - '0') * (B[j] - '0') + C[i + j] - '0');
C[i + j] = (char)(c%10 + '0');
c/=10;
}
if (c > 0) C[i + B.length()] += c;
}
reverse(C.begin(),C.end());
while (C.size() > 1 && C[0] == '0') C.erase(0, 1);
return C;
}
string div(string number, ll divisor) // divide 1 string with 1 number, the version for divide two strings in down below
{
string ans = "";
ll idx = 0;
ll temp = number[idx] - '0';
while (temp < divisor) temp = temp * 10 + (number[++idx] - '0');
while (number.size() > idx)
{
ans += (temp / divisor) + '0';
temp = (temp % divisor) * 10 + number[++idx] - '0';
}
while (ans.size() > 1 && ans[0] == '0') ans.erase(0, 1);
if (ans.length() == 0) return "0";
return ans;
}
bool bigger2(string a, string b) // check if a >= b, not strictly greater
{
if (a.length() > b.length()) return true;
if (a.length() < b.length()) return false;
FOR(i, 0, a.length() - 1)
{
if (a[i] > b[i]) return true;
else if (a[i] < b[i]) return false;
}
return true;
}
string dv(string a, string b) // divide as two strings, use binary search
{
if (bigger(b, a)) return "0";
if (a == "0") return "0";
string l = "0";
string r = a;
string mid, mid2;
while (bigger2(r, l))
{
mid = add(r, l);
if ((mid[mid.length() - 1] - '0') % 2 == 1) mid[mid.length() - 1]--;
mid = div(mid, 2);
if (mid == "0") break;
mid2 = mul(mid, b);
if (bigger(mid2, a)) r = sub(mid, "1");
else l = add(mid, "1");
}
return r;
}
string md(string a, string b) // find a % b
{
if (bigger(b, a)) return a;
if (a == "0") return "0";
if (b == "1") return "0";
string l = "0";
string r = a;
string mid, mid2;
while (bigger2(r, l))
{
if (mid == "0") break;
mid = add(r, l);
if ((mid[mid.length() - 1] - '0') % 2 == 1) mid[mid.length() - 1]--;
mid = div(mid, 2);
mid2 = mul(mid, b);
if (bigger(mid2, a)) r = sub(mid, "1");
else l = add(mid, "1");
}
mid = mul(r, b);
mid = sub(a, mid);
while (mid.size() > 1 && mid[0] == '0') mid.erase(0, 1);
if (mid == b) return "0";
return mid;
}
string strgcd(string a, string b) // find gcd(a, b)
{
if (a == "0") return b;
return strgcd(md(b, a), a);
}
};
STRO STR;
Hope you will find this helpful ^_^ Thanks for reading.
Or I will shave my hair.
I tried to add the 100s and 0s one by one, since $$$n$$$ does not exceed $$$10^6$$$, solving it by using heaps does not cost so much time. Here it is: 122955494.
Have a nice day! Please don't downvote me :(
Hi, I'm just wonder how much time the people here need to reach CM. I have stuck with this 1700-1750 elo for 2 weeks, maybe it'll be more. Could you please share your story and your experience of how you you gone so far and achieve such high ratings? I would love to learn from any.
Thanks for reading this dumbsh*t blog.
P/s: I hope to reach CM in less than 5 months, is it possible or just illusory?
P/s 2: Sorry if this blog makes you feel inconvenient. My English is bad :(
It's literally resubmit everyone's code. My latest submission for practice has been in queue for 30 minutes lol.
Still submitting.
I am current looking for some Discord servers which has been built for CP community, but I haven't found any. Can anybody suggest me some? Thank you!
Sorry for my bad English T-T
P/s: I wonder why posting searching for a learning community on codeforces is badly downvoted :/ Is it a hated topic? If it is, I will remove it :(
He told my whole family, I don't know whether to laugh or to cry :(
Given a map of a dungeon, your task is to take all TWO diamonds in the dungeon.
Find the minimum number of gates you have to open to take all the diamonds.
Note: It can be more than one gate to go into the dungeon from the outside.
You can move up, down, left, right.
About the map:
The letter '.' means blank space, you can move on it
The letter '*' means blockade, you have to go around it
The letter '#' means there's a gate at that place, you need it opened to go through it
The letter '$' means the diamond.
Input format:
First line is two number N and M — the dungeon has the size N*M. (2 ≤ N,M ≤ 100)
N lines following, represent the map of the dungeon.
Output format:
Example input:
5 9
****#****
..#.#..
****.****
$$$#.#.#$$$
Sorry for the input, you can see read the input here : https://ideone.com/EXk0Wh
Example output:
4
Thank you guys, hope you have a great standing in the next contest.
Magnus is the youngest chess grandmaster ever. He loves chess so much that he decided to decorate his home with chess pieces. To decorate his long corridor, he decided to use the knight pieces. His corridor is covered by beautiful square marble tiles of alternating colors, just like a chess board, with n rows and m columns. He will put images of knights on some (possibly none) of these tiles. Each tile will contain at most one knight.
The special thing about his arrangement is that there won’t be any pair of knights can attack each other. Two knights can attack each other if they are placed in two opposite corner cells of a 2 by 3 rectangle. In this diagram, the knight can attack any of the Xs.
Given the dimension of the long corridor, your task is to calculate how many ways Magnus can arrange his knights. Two arrangements are considered different if there exists a tile which contains a knight in one arrangement but not in the other arrangement (in other words, rotations and reflections are considered different arrangements).
Input
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will consist of a single line with two integers n and m (1≤n≤4, 1≤m≤10^9) representing the dimensions of the carpet. There will be a single space between n and m.
Output
Output a single line with a single integer representing the number of possible arrangements, modulo (10^9+9).
Sample Input 1
1 2
Sample Output 1
4
Sample Input 2
2 2
Sample Output 2
16
Sample Input 3
3 2
Sample Output 3
36
He said I need to Divide and Conquer, however I got no idea about that.
Given an array with N elements and a number P (P ≤ N). Pick randomly P elements from the array, let's call T the product of these elements. Find the largest x that T % 10^x = 0
Example:
Input
3 2
26 5 96
Output
1
Input
3 2
25 4 90
Output
2
Name |
---|