Hello CF!
I have made a meetup group about competitive programming in Barcelona. We're going to have the first meetup next Thursday, 4th of July! If you're from Barcelona and are interested, please join via the link below:
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hello CF!
I have made a meetup group about competitive programming in Barcelona. We're going to have the first meetup next Thursday, 4th of July! If you're from Barcelona and are interested, please join via the link below:
Hi CF community.
I'm registered in Codeforces for more than 6 years. I did ~100 contests, and yet I'm an expert, my max rating is for 4 years ago. I'm not consistent with my training, I train one month before each ICPC regional and then I let it go, after failing to go to world finals I tell myself that I'll train the next year but I don't! I almost never upsolve any problem after the contest ends. I lose my motivation if I do badly in a contest or two (even if it's because of the contest itself).
See, I recognize the problem and I also know the solution: train consistently, upsolve, etc. I always knew the solution and yet I never act on it.
But enough is enough. I have only 2 more years to participate in ICPC. I have decided to train harder and more consistent, but in order to stick to my goal, I want to share it. (although it's not a great idea, I think it works for me)
I want to become an International Master by the end of 2019, meaning I want to have a max rating >= 2300. I know it is a really really hard goal to achieve in a year, but I want to commit, no matter what.
I'm starting with a rating of ~1800, and I want to post contents regularly to update you about my training, my progress and the cool ideas/problems that I come across during my training, so stay tuned.
Any hint, tip or advice is highly appreciated.
Cheers!
There are many style guides for C++ out there, but we can't really use them as competitive programmers. We just want to write our code correctly as fast as possible! Trying to hack people here on codeforces, I realized there is a need for a style guide! Our goal is to write correct, fast, clear and consistent code.
Disclaimer
This is not a rulebook. You can integrate parts of it into your coding style. Don't overthink it, especially during a contest!
I'm going to use this guide for myself and to teach my students. I'm planning to make some good stuff in the future following these principles! Stay tuned!
Make use of C++17. Use -Wall -Wextra -Wshadow
flags for compilation, and try to eliminate all of the warning messages, this will prevent you from having some silly bugs. There are more debugging flags like -fsanitize=undefined
which helps you eliminate bugs such as array out-of-range access and integer overflow during runtime. For more information, check out "Read More" section.
C++ libraries use snake_case for functions and classes, in order to differentiate the user-defined code from the standard library, we will use CamelCase.
Point
, SegTree
someMethod
, someVariable
_
: SOME_MACRO
, MAX_N
, MOD
#define LOCAL
const double PI = 3.14;
struct MyPoint {
int x, y;
bool someProperty;
int someMethod() {
return someProperty ? x : y;
}
};
Note
Using snake_case is fine, but be consistent!
In competitive programming, you usually don't want to write long comments, but in case you do want to write some comments, write them using //
instead of /* */
. Using //
enables you to comment out a chunk of code with /* */
while debugging, and /* /* ... */ */
is a bug!
/* commenting out a block of code - no problem!
// some comment about the function below...
void someFunction() {
// do something
}
*/
Control flow statements are
if / else / for / while / ...
else
should start on the same line after closing brace of if
block.<> [] {}
are a part of their identifier like a[5]
, vector<int>
or pair{1, 2}
.(-a[3] + b) * (c + d)
.public:
or switch cases case 10:
.if (flag)
.func(arg)
.#define SOME_MACRO
and #include <iostream>
.template <typename T>
and a new line.::
is a part of the identifier and should not be spaced.int* ptr
and const string& str
. To avoid bugs, declare only one pointer per line..
and ->
operator should not be spaced. When ->
is used to show return type (like in lambda expressions) it should be spaced from both sides.[](int x) -> int { return x + 1; }
. The return type can be omitted most of the times. Feel free to expand the body exactly like a function if it has more than 1 line of code.bool operator!();
...
should only be spaced from the left side.#include <bits/stdc++.h>
using namespace std;
const int DIFF = 10;
template <typename T>
struct Point {
T x, y;
Point(T _x, T _y) : x(_x), y(_y) {}
friend ostream& operator<<(ostream& os, const Point& p) {
return os << "(" << p.x << ", " << p.y << ")";
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<Point<int>> v;
for (int i = 0; i < 5; ++i) {
v.push_back({i, i + DIFF});
}
for (auto p : v) {
if (p.x + DIFF == p.y) {
cout << p << '\n';
} else {
cout << "huh!?\n"; // will never get printed!
}
}
}
(0, 10)
(1, 11)
(2, 12)
(3, 13)
(4, 14)
#include <bits/stdc++.h>
instead of many includes.using namespace std;
instead of typing std::
every time.using
instead of typedef
, for example using ll = long long;
. Rationale: It's more consistent with the style of modern C++.struct
instead of class
. Rationale: It defaults to public, and you don't need encapsulation in competitive programming!const
for defining a constant instead of #define
. Rationale: consts have a type, and they are evaluated at compile time.switch
statement.auto
to increase readability and decrease code size.emplace
and emplace_back
for containers when dealing with pairs and tuples. Rationale: (elem1, elem2, ...)
instead of ({elem1, elem2, ...})
.sort
. Don't repeat yourself, use lambda functions in your code instead of copy/pasting.nullptr
instead of NULL
or 0
.true
and false
!ios::sync_with_stdio(false);
and cin.tie(nullptr);
for a faster I/O using cin/cout
.__builtin
.gcd
and lcm
.for (auto& elem : vec)
.for (auto& [key, val] : dic)
and auto [x, y] = myPoint;
pair p{1, 2.5};
instead of pair<int, double> p{1, 2.5};
.goto
! But be brave enough to use goto
when you want to break from several nested loops (in case you just can't refactor it)!-DONLINE_JUDGE
to compile your code, this means that you can remove your cerr
s or your debug functions automatically or redirect input/output to file instead of stdin/stdout, etc.#ifdef ONLINE_JUDGE
#define cerr if (false) cerr
#endif
// Alternatively this can be done using a local -DLOCAL flag
// when compiling on your machine, and using #ifndef LOCAL instead.
!, &&, ||, ^, ...
instead of their alternative representations not, and, or, xor, ...
. Rationale: We're not coding in python!Any suggestions are welcome. You can contribute to this post by commenting or using GitHub.
I actually got accepted on most of these problems, but they're shown as "red", why is that?
There are infinite number of people, each one has a whether red or blue hat. Everyone can see everyone's hat but can't see their own. Is it possible that with a strategy, only a finite number of people guess their hat color wrong?
Hi codeforces community.
I thought there is no good 2-SAT tutorial in the internet, so I decided to write one.
2-SAT is a special case of boolean satisfiability.
Good question! Boolean satisfiability or just SAT determines whether we can give values (TRUE or FALSE only) to each boolean variable in such a way that the value of the formula become TRUE or not. If we can do so, we call formula satisfiable, otherwise we call it unsatisfiable. Look at the example below:
f = A ∧ ¬B, is satisfiable, cause A = TRUE and B = FALSE makes it TRUE.
but g = A ∧ ¬A, is unsatisfiable, look at this table:
A | ¬A | A ∧ ¬A |
TRUE | FALSE | FALSE |
FALSE | TRUE | FALSE |
As you can see g is unsatisfiable cause whatever values of its boolean variables are, g is FALSE.
Note: ¬ in ¬X is boolean not operation. ∧ in X ∧ Y is boolean and operation and finally ∨ in X ∨ Y is boolean or operation.
SAT is a NP-Complete
problem, though we can solve 1-SAT and 2-SAT problems in a polynomial time.
Note: This doesn't really exist, I define it cause it help understanding 2-SAT.
Consider f = x1 ∧ x2 ∧ ... ∧ xn.
Problem: Is f satisfiable?
Solution: Well 1-SAT is an easy problem, if there aren't both of xi and ¬xi in f, then f is satisfiable, otherwise it's not.
Consider f = (x1 ∨ y1) ∧ (x2 ∨ y2) ∧ ... ∧ (xn ∨ yn).
Problem: Is f satisfiable?
But how to solve this problem? xi ∨ yi and and are all equivalent. So we convert each of (xi ∨ yi) s into those two statements.
Now consider a graph with 2n vertices; For each of (xi ∨ yi) s we add two directed edges
From ¬xi to yi
From ¬yi to xi
f is not satisfiable if both ¬xi and xi are in the same SCC (Strongly Connected Component) (Why?) Checking this can be done with a simple Kosaraju's Algorithm.
Assume that f is satisfiable. Now we want to give values to each variable in order to satisfy f. It can be done with a topological sort of vertices of the graph we made. If ¬xi is after xi in topological sort, xi should be FALSE. It should be TRUE otherwise.
Some problems:
func dfsFirst(vertex v):
marked[v] = true
for each vertex u adjacent to v do:
if not marked[u]:
dfsFirst(u)
stack.push(v)
func dfsSecond(vertex v):
marked[v] = true
for each vertex u adjacent to v do:
if not marked[u]:
dfsSecond(u)
component[v] = counter
for i = 1 to n do:
addEdge(not x[i], y[i])
addEdge(not y[i], x[i])
for i = 1 to n do:
if not marked[x[i]]:
dfsFirst(x[i])
if not marked[y[i]]:
dfsFirst(y[i])
if not marked[not x[i]]:
dfsFirst(not x[i])
if not marked[not y[i]]:
dfsFirst(not y[i])
set all marked values false
counter = 0
flip directions of edges // change v -> u to u -> v
while stack is not empty do:
v = stack.pop
if not marked[v]
counter = counter + 1
dfsSecond(v)
for i = 1 to n do:
if component[x[i]] == component[not x[i]]:
it is unsatisfiable
exit
if component[y[i]] == component[not y[i]]:
it is unsatisfiable
exit
it is satisfiable
exit
I see lots of programmers write code like this one:
pair<int, int> p;
vector<int> v;
// ...
p = make_pair(3, 4);
v.push_back(4); v.push_back(5);
while you can just do this:
pair<int, int> p;
vector<int> v;
// ...
p = {3, 4};
v = {4, 5};
Name |
---|