i guess Iran isn't a good country to maintain a long codeforces streak.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | maroonrk | 133 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
i guess Iran isn't a good country to maintain a long codeforces streak.

Should i go for a hat-trick in the next div2?
338773322 wa 2144D - Price Tags
338775116 ac 2144D - Price Tags
337836980 wa 2140E1 - Prime Gaming (Easy Version)
337838936 ac 2140E1 - Prime Gaming (Easy Version) (If you use compare, there is another difference between the codes, but that line is only for debugging)
I also have a lot of other stupid mistakes besides these two, but these two were in two Div2s in a row and looked like the same.
it has been a long time since the last rollback when are we getting a rating rollback?
till now a lot of cheaters have been detected and removed from the standing of the last contest (but still not bssss_a), also if you go to status you can see 52 pages of skipped submissions. also my rank grew up by 67 which is quite a lot in the top 200.
i have noticed something weird in the standings of Codeforces Round 992 (Div. 2)(and probably some other ones), if you go to the standings you can see the person who got rank 1 is daniel6202, which AK'ed the contest as an unrated which is suspicious but that is not the full reason, if you go to the account you can see that the user is disabled, and if you go to the contest page, you can see that the user only attended two contests one which was Codeforces Round 992 (Div. 2), and the other Codeforces Round 993 (Div. 4), in the second contest he had all of his submissions skipped, which means probably he cheated, but how can an unrated user, fully AK a div2 contest (he was the only one which fully solved the contest and solved a 2700 rated problem in about 12 minute difference with the last problem which he solved) but get caught cheating in a div4 contest. and after the user is disabled, it is still presented in the standings.
UPD : there are obviously alot more like lequoctran181 which you can read more about him here, but got high ranks in Codeforces Round 1007 (Div. 2),Educational Codeforces Round 174 (Rated for Div. 2),Educational Codeforces Round 172 (Rated for Div. 2),Codeforces Round 984 (Div. 3),... and isn't getting removed from the standing
as said in editorial, to solve 2095C - Would It Be Unrated? you can either brute force or you need another person to get accepted, well the first person who got accepted is AprilFoolsClairvoyant, and if you see the account, the account registered in the middle of the contest, submitted one code for problem C and did nothing else, so who is AprilFoolsClairvoyant?
[EDIT] : i just saw the editorial again, on trivia 2 there is more info about AprilFoolsClairvoyant
[EDIT2] : in contest materials, we can see there are two announcements, announcement 2 is the picture of the profile of AprilFoolsClairvoyant
tourist in the last contest has achieved 1st place and crossed 4000 rating and become the first person on codeforces in the rank Tourist
Backtracking: This algorithm helps you solve problems in a specific way using your skills in recursive programming. It comes in handy whenever you have a set of valid answers to a problem and need to search through them all or construct a suitable answer, this algorithm is a general algorithm for finding all or some solutions in some computational problems. The backtracking method is an algorithmic method to solve some kind of problems in which we need to build and examine all possible situations or a number of good situations of an arrangement(combination), in this algorithm all possible situations are created , and after examining each one, if it is approved based on the request of the problem we will accept it as a answer(kind of like brute force we find each possible combination). Note that this method is useful when we cant use a faster algorithm(like: Greedy or Dp).
the General Backtracking Method is like this(pseudocode):
solve(X):
if X is accepted:
X is answer
exit
while we can change X:
change X
if X is valid:
solve(X)
undo last change from X
The base of the algorithm is in 4 parts: the condition of finding the answer (lines 1 to 3) — finding all the different states of the answer (lines 4 to 6) — recursive call (line 7) — return the last change made (line 8).
Some Backtracking Problems:
1-Print all strings of length n that are made only of letters a, b, and c.
Backtracking method: We perform the same general method, we add one of the letters to the string each round and print it when the length of the string is equal to n, and until the length of the string is less than is n, we repeat this process (if the length of the string is greater than n, we backtrack), code in C++
vector<char> temp;
void print(){
for (int i = 0; i < n; i++) cout << temp[i];
cout << "\n";
}
void solve(int i){
if (i == n) print();
else if (i > n) return;
else {
char chr[3] = {‘a’ , ‘b’ , ‘c’};
for (int j = 0; j < 3; j++){
//changing
temp.push_back(chr[j]);
//recursive call
solve(i+1);
//undo last change
temp.pop_back();
}
}
}
2-A horse is in the cell (0,0) in a n*n chessboard. That is, in the upper-left corner, you have to say the number of cells that the horse can reach with exactly k moves.
Backtracking method: we move till, when the number of moves is equal to k, if a new cells found, we add it to our answers (because we may reach the same cells with two different methods). otherwise, if the moves made were more than k, we go back (we backtrack), and if it was less than k, we move the 8 possible moves of the horse and with the condition that after the move we stay inside the chess board, we do each movement again and... , code in C++(result is saved in ans variable)
int ans;
vector<int> answers;
bool inside(int x , int y){
return x >= 0 && x < n && y >= 0 && y < n;
}
void solve(int x , int y , int i){
if(i == k && !count(answers.begin() , answers.end() , make_pair(x , y)){
answers.push_back(make_pair(x , y));
ans++;
return;
}else if(i > k) return;
else{
//all possible moves by a knight
int dx[8] = {1 , 2 , -1 , -2 , -1 , -2 , 1 , 2};
int dy[8] = {2 , -1 , -2 , 1 , 2 , -1 , -2 , 1};
for(int j = 0 ; j < 8 ; j++){
int new_x = x + dx[j];
int new_y = y + dy[j];
//changing
if(inside(new_x , new_y)) //checking is valid
solve(new_x , new_y , i+1); //recursive call
}
}
}
Backtracking method: in the string each time we reach a '?' , first we will turn it into '-' then into '+' (or reversed) , and when there is no more '?' we count, if it is accepted we will increase the good ways.
#include <bits/stdc++.h>
using namespace std;
string s1;
string s2;
double goods= 0;
double all = 0;
void backtrack(int i , int res){
if(s2[i] == '?'){
//changing
s2[i] = '-';
//recursive call
backtrack(i , res);
s2[i] = '+';
backtrack(i , res);
//undo last change
s2[i] = '?';
}else if(i == s1.length()-1){
int ans = 0;
all++;
for(auto c : s2){
if(c == '+') ans++;
else ans--;
}
if(ans == res) goods++;
return;
}
if(i >= s1.length()){
return;
}
if(s2[i] == '+'){
backtrack(i+1 , res);
}
else if(s2[i] == '-'){
backtrack(i+1 , res);
}
return;
}
int main() {
ios::sycn_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> s1 >> s2;
int res = 0;
for(auto c : s1){
if(c == '+') res++;
else res--;
}
backtrack(0 , res);
cout << setprecision(9) << goods/all;
}
Here are Some easy to intermediate codeforces graph and backtracking problems this problems normally only use some basic knowledge of graphs/trees + basic algorithms , I hope it helps
1944A - Destroying Bridges rate : 800 -> basic of graphs [Very Simple]
1598A - Computer Game rate : 800 -> not so much graph [Very Simple]
1797A - Li Hua and Maze rate : 800 -> not so much graph + edge cases [Very Simple]
1843C - Sum in Binary Tree rate : 800 -> not so much graph or tree [Very Simple]
939A - Love Triangle rate : 800 -> can be solved with graph or not [Very Simple]
115A - Party and 116C - Party rate : 900 -> bfs [Simple]
500A - New Year Transportation rate : 1000 -> dfs [Simple]
727A - Transformation: from A to B rate : 1000 -> backtracking / dfs [Simple]
476A - Dreamoon and Stairs rate : 1000 -> backtracking + some optimization [Simple]
1020B - Badge rate : 1000 -> dfs [Simple]
122A - Lucky Division rate : 1000 -> backtracking [Simple]
1324C - Frog Jumps rate : 1100 -> not so much graph but can be solved with dfs [Very Simple]
445A - DZY Loves Chessboard rate : 1200 -> can be solved with dfs [Simple(simpler than it's rating)]
217A - Ice Skating rate : 1200 -> dfs [Simple/Intermediate]
893C - Rumor rate : 1300 -> dfs [Simple]
476B - Dreamoon and WiFi rate : 1300 -> backtracking [Simple]
1638C - Inversion Graph rate : 1300 -> creativity [Simple/Intermediate]
1970C1 - Game on Tree (Easy) rate : 1300 -> trees + dfs/bfs [Simple/Intermediate]
96B - Lucky Numbers (easy) rate : 1300 -> backtracking [Simple]
1143C - Queen rate : 1400 -> trees + you can use dfs/bfs [Simple]
520B - Two Buttons rate : 1400 -> bfs [Simple/Intermediate]
580C - Kefa and Park rate : 1500 -> trees + dfs/bfs [Intermediate]
977E - Cyclic Components rate : 1500 -> dfs [Intermediate]
377A - Maze rate : 1600 -> bfs [Intermediate]
601A - The Two Routes rate : 1600 -> bfs / matrix [Intermediate/Hard]
1363C - Game On Leaves rate : 1600 -> trees / some edge cases only [Simple/Intermediate]
1144F - Graph Without Long Directed Paths rate : 1700 -> bipartite graphs [Intermediate/Hard]
1093D - Beautiful Graph rate : 1700 -> bipartite graphs [Intermediate/Hard]
1970C2 - Game on Tree (Medium) rate : 1700 -> a little hard + dfs/bfs [Intermediate/Hard]
| Название |
|---|


