I am unable to send message on CF. When i type my message and send, it is sent succesfully but blank, does anyone knows the reason?

**image**

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

1 | tourist | 3565 |

2 | Benq | 3540 |

3 | Petr | 3519 |

4 | maroonrk | 3503 |

5 | jiangly | 3391 |

6 | ecnerwala | 3363 |

7 | Radewoosh | 3349 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

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

1 | 1-gon | 200 |

2 | Errichto | 196 |

3 | rng_58 | 194 |

4 | SecondThread | 186 |

4 | awoo | 186 |

6 | Um_nik | 182 |

7 | vovuh | 179 |

8 | Ashishgup | 176 |

9 | -is-this-fft- | 173 |

9 | maroonrk | 173 |

**Disclaimer**: Not writing this for contribution,so feel free to not hit upvote button, just read n chill.

2020 has been a fantastic year for me. A lot of good things (some bad too) happened:

1) became Candidate Master (never thought it would be possible, but smh it happened)

2) spent a lot of time with family during lockdown.

3) learnt how to drive car & tractor (still learning :))

4) got a chance to interview with some good IT companies.

From next year , i'll be joining as SDE, so not sure if I will be able to participate on CF + i don't enjoy CP as much as I used to do it some months back, so maybe will take a break. I have learnt a lot of things from CF blogs(n i really mean it), so huge to CF community.

If you wish to share your achievements, you are welcome :).

Hi everyone. Ask me anything.

**UPD**: Happy Diwali to all the Indians out there.

Hi everyone.

The title itself has the problem description, but let me describe it once more below.

We are given a tree with $$$N$$$ nodes. 1 <= $$$N$$$ <= 100. We need to find the number of connected subgraphs which has exactly $$$k$$$ nodes and all these $$$k$$$ nodes must be connected.

I came up with a solution which is like:

let's root the tree at node $$$1$$$:

$$$dp[i][j]$$$ = number of ways to choose a subgraph of size $$$j$$$ in the subtree of $$$i$$$ (including node $$$i$$$). Now this can be solved with subset-sum kind of dp.

but the problem here i am facing is that $$$dp[1][k]$$$ will be number of ways to choose a subgraph of size $$$k$$$ rooted at node $$$1$$$. I am unable to figure out a way to calculate this answer for whole tree. If i root every $$$x$$$ (1 <= $$$x$$$ <= $$$N$$$) and then add the answer for every $$$x$$$ then obviously answer will be overcounted.

Can anyone suggest what wrong with my approach or how can it be corrected or any other solution or any relevant link except the one's i mentioned below?

P.S. — I tried asking this in this blog but got no response.

Hello Codeforces community.

Tl;dr: The script is specifically for Ubuntu and can be used to stress test `C++` solutions. It can be easily modified to work with python or java. To use it in windows you can download Ubuntu terminal which is officially available on Microsoft Store and then use it or you can modify the script to work in cmd by changing the .out files to .exe and a bit of syntax for cmd.

**Note**: If you don't want to read this lengthy blog, just go to this repo and follow the instructions of readme.

First let me tell you what stress testing is if you don't know, Stress testing is technique using which we can run our solution (which we think might fail/is failing) on a number of random test cases and match it's output with the output of a solution which is a brute force solution or accepted solution of someone else.

If you don't know why and when to use stress testing you can use this detailed article on Stress Testing by ADJA.

I want to share my script for stress testing your solution.

Requirements:

1) A solution which we want to test.

2) A brute force solution which gives correct solution.

3) A generator for generating test cases according to the problem.

About script:

```
#!/bin/bash
i=1
# You can change the version of C++ or add the compiler flags you wish
g++ -std=c++17 gen.cpp -o generator
g++ -std=c++17 solution.cpp -o original
g++ -std=c++17 brute.cpp -o brute
max_tests=10 # change it accordingly
diff_found=0
# to color the output text in different colours
green=$(tput setaf 71);
red=$(tput setaf 1);
blue=$(tput setaf 32);
orange=$(tput setaf 178);
bold=$(tput bold);
reset=$(tput sgr0);
while [ $i -le $max_tests ]
do
# Generate test_case and save it in input1.txt
./generator > input1.txt
# run original solution, take input from above generated test case i.e. from input1.txt
# and save it in original_output.txt
./original < input1.txt > original_output.txt
# run brute force solution, take input from above generated test case i.e. from input1.txt
# and save it in brute_output.txt
./brute < input1.txt > brute_output.txt
# check if files original_output and brute_output
# differs(we are ignoring spaces and then comparing files)
if diff --tabsize=1 -F --label --side-by-side --ignore-space-change original_output.txt brute_output.txt >
dont_show_on_terminal.txt; then
echo "<p>Unable to parse markup [type=CF_MATHJAX]</p>{bold}$$${green}Accepted$$${reset}"
else
echo "<p>Unable to parse markup [type=CF_MATHJAX]</p>{bold}$$${red}Wrong Answer$$${reset}"
diff_found=1
break
fi
i=$((i+1))
done
if [ $diff_found -eq 1 ]
then
echo "$$${blue}Input: $$${reset}"
cat input1.txt
echo ""
echo "$$${blue}Output: $$${reset}"
cat original_output.txt
echo ""
echo ""
echo "$$${blue}Expected: $$${reset}"
cat brute_output.txt
echo ""
fi
rm input1.txt
rm generator
rm original
rm brute
rm original_output.txt
rm brute_output.txt
rm dont_show_on_terminal.txt
```

Go through the code once, i have added comments and you will understand most of the part. To understand the script all we need is just basics of the language `bash`

. So we have three `.cpp`

files:

1) gen.cpp // our cpp solution for generating test cases
2) solution.cpp // our orignial solution
3) brute.cpp // our solution which uses brute force and guaranteed to give correct output

About test case generator:

For generating test cases you can either use "testlib.h" here (i personally don't use it because it takes 6-7 seconds on average to compile in my pc(idk there might be ways to reduce it) and also i need to remember the methods to generate things.) or write your own since most of the time you just need arrays, strings, trees or simple graphs or simple some integers.

I use the below code for generating test cases most of the times(file gen.cpp):

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define accuracy chrono::steady_clock::now().time_since_epoch().count()
#define rep(i,a,n) for (int i = a; i <= n; ++i)
const int N = 1e6 + 4;
int32_t permutation[N];
mt19937 rng(accuracy);
int rand(int l, int r){
uniform_int_distribution<int> ludo(l, r); return ludo(rng);
}
const int inf = 1LL << 31;
using pii = pair<int,int>;
namespace generator {
string gen_string(int len = 0, bool upperCase = false, int l = 1, int r = 26) {
assert(len >= 0 && len <= 5e6);
string str(len, (upperCase ? 'A' : 'a'));
for (char &ch: str) {
ch += rand(l, r) - 1;
}
return str;
}
vector<int> gen_array(int len = 0, int minRange = 0, int maxRange = inf){
assert(len >= 0 and len <= 5e6);
vector<int> a(len);
for (int &x: a) x = rand(minRange, maxRange);
return a;
}
vector<pair<int, int>> gen_tree(int n = 0){
assert(n >= 0);
vector<pii> res(n ? n - 1 : 0);
// if you like to have bamboo like tree or star like tree uncomment below 8 lines
/*if (rng() % 5 == 0) { // bamboo like tree
for (int i = 1; i < n; ++i) res[i-1] = {i, i + 1};
return res;
}
if (rng() % 7 == 0) { // star tree
for (int i = 2; i <= n; ++i) res[i-2] = {1, i};
return res;
}*/
iota(permutation, permutation + 1 + n, 0);
shuffle(permutation + 1, permutation + 1 + n, rng);
for(int i = 2; i <= n; ++i){
int u = i, v = rand(1 , i-1);
u = permutation[u], v = permutation[v];
res[i-2] = minmax(u, v); // u < v, just for convenience while debugging
}
shuffle(res.begin() , res.end() , rng);
return res;
}
vector<pair<int, int>> simple_graph(int n = 0, int m = 0) {
assert(n > 0 && m >= n);
int max_edges = n * (n - 1) / 2;
assert(m <= max_edges);
vector<pii> res = gen_tree(n);
set<pii> edge(res.begin(), res.end());
for (int i = n; i <= m; ++i) {
while (true) {
int u = rand(1, n), v = rand(1, n);
if (u == v) continue;
auto it = edge.insert(minmax(u, v));
if (it.second) break;
}
}
res.assign(edge.begin(), edge.end());
return res;
}
}
using namespace generator;
template<typename T = int>
ostream& operator<< (ostream &other, const vector<T> &v) {
for (const T &x: v) other << x << ' ';
other << '\n';
return other;
}
ostream& operator<< (ostream &other, const vector<pair<int,int>> &v) {
for (const auto &x: v) other << x.first << ' ' << x.second << '\n';
return other;
}
// comment the just below line if test cases required
#define SINGLE_TEST
const int max_tests = 10;
// complete this function according to the requirements
void generate_test() {
int n = rand(1, 40);
cout << n << '\n';
cout << gen_array(n, 1, 20);
}
signed main() {
srand(accuracy);
int t = 1;
#ifndef SINGLE_TEST
t = rand(1, max_tests), cout << t << '\n';
#endif
while (t--) {
generate_test();
}
}

You can use above code and modify it according to your needs. Just go through the code once and everything is self explanatory(i have added some comments too). Usage of above gen.cpp code:

1) to generate an array calling:
gen_array(10, -5, 10);
it will return an array(vector more specifically) with length 10 and elements in the range [-5, 10].
2) to generate a tree calling:
gen_tree(10):
will return a tree with 10 nodes.
3) to generate a simple graph calling:
gen_simple_graph(10, 12);
will return a simple connected graph with 10 nodes and 12 edges.
You can add things as you need them or use testlib which is the best if you know how to use it.

Usage:

Download this repository manually or by using git clone on terminal.

- Copy your original solution which you expect might fail in the file
`solution.cpp`

. - Copy your brute force solution which is expected to give correct output in the file
`brute.cpp`

. - Change the
`gen.cpp`

file so as to generate test cases according to the question.

Now open your terminal in the directory where file `s.sh`

resides and run command:

$ `bash s.sh`

or

$ `./s.sh`

If it shows permission denied then give it execute permission using:

$ `sudo chmod +x s.sh`

.

In file `s.sh`

you can change the value of variable `max_tests`

as you wish on how many random test you want to run the solution.

Verdict: the verdict of running file `s.sh`

on every test case is either `Accepted`

if your solution's output matches the brute solution output or `Wrong Answer`

and will show the input on which the solution failed, the output of your solution and expected output according to the brute force solution on terminal and the script will be terminated.

If you wish to terminate the script at any moment you wish use the command `ctrl + c`

in terminal.

quick demo: Here the output of first 3 test cases matched with the brite and as soon as it didn't, it printed the test case, output, and expected output to the console and terminated. Now you can debug your original solution and check where it goes wrong.

()

You can watch this video by Errichto to understand more about stress testing.

Any suggestions or corrections are welcomed.

Apologies for my poor english.

`tab_width-4`

, but when i submit the code on Codeforces it's indentation changes to 8 and makes the code look ugly like this. I tried turning editor mode off while submitting on codeforces and also tried changing tab width while submitting but it didn't helped.

Can anyone help me how can i fix this bcz i hate looking at my own ugly code with messy indentation?

**UPD** : using `"translate_tabs_to_spaces": true`

worked for me. Thank you everyone for the help.

My initial solution was if there exists a subarray with size > 1 and median k than answer is yes.

But, afer getting a lot of WA on pretest 10, at the last moment i realized that the solution is yes if there exists any subarray of size > 1 with median >= k and i didn't have time so i just submitted my solutin which uses 6 iterations to check if there exists a subarray with size atleast two and median >= k. It passed pretests + system testing.

```
1
26 2
2 1 1 1 3 1 4 1 1 5 1 1 6 1 1
7 1 1 8 1 1 9 1 1 10
The answer should be yes but my solution gives no.
```

Given $$$N$$$ strings, we need to count how many pairs $$$1$$$ <= $$$i$$$, $$$j$$$ <= $$$N$$$ exists such that s[i] + s[j] is a Palindrome. Can anyone suggest an efficient approach for solving this problem?

1 <= $$$N$$$ <= 2000

1 <= |s_{i}| <= 1000

The lengths of all strings are not necessarily same and all the strings may not be unique.

My approach is to precompute hashes of the given strings and iterate over all pairs i, j now we want to concatenate the two strings $$$s[i] + s[j]$$$. For simplicity let's say $$$length(s[i]) <= length(s[j])$$$

1) if $$$length(s[i]) == length(s[j])$$$ then $$$hash(s[i])$$$ should be equal to $$$hash(reverse(s[j]))$$$.

2) otherwise take suffix of $$$s[j]$$$ of length equal to $$$s[i]$$$ and check if it's reverse is equal to $$$s[i]$$$ and also remaining prefix of $$$s[j]$$$ excluding the previous suffix should be palindrome.

Any approach other than hashing or any link if it's solution is already published somewhere?

^{31}-1 and was using % operator while calculating hash. It took $$$540ms$$$. Then i tried using unsigned int for calculating hash which implicitly uses modulo $$$2$$$^{32} if the calculation overflows or underflows and the runtime reduced to 240ms. So, i want to know if i can use my Rolling hash with unsigned int(and is it safe to use) in CF rounds(because i am always afraid of getting hacked while using Rolling Hash).

I uses Rolling Hash more often than string algorithms(if problem can be solved by Rolling hash). Even i use Rolling Hash + binary search to find longest palindromic substring because i don't really understand Manacher's Algorithms.

So, can anyone hack my solution or tell me how much probability this hash has of being hacked during a CF round?

Solution using $$$mod$$$ = $$$2$$$^{32}.

Solution using $$$mod$$$ = $$$2$$$^{31}-1.

Hello Everyone. I want to share a list of contests which were held in our college.

People from rating 0 to 1800 will find the problems interesting as well as challenging. The interested one's can upsolve.

Thank You.

Given a simple undirected and connected graph with $$$N$$$ nodes and $$$M$$$ edges. Also two different nodes are given $$$a$$$ and $$$b$$$. We have to answer $$$q$$$ queries. Each query contains an integer $$$v$$$(i.e. a node) from $$$1$$$ to $$$N$$$, we need to answer if we remove node $$$v$$$ and all of it's adjacent edges from the given graph, do nodes $$$a$$$ and $$$b$$$ lies in the same connected component or not? All queries are independent.

$$$ 3 \le N,M \le 10^6 $$$

$$$ 1 \le a,b,v,q \le N $$$

$$$ v \ne a $$$ and $$$ v \ne b $$$

If v is a not a cut vertex (articulation point) then the answer is always YES.

PS: This problem is not from any contest.

Any hints to solve the above problem are appreciated. Thanks.

I am getting TLE on last test case of this problem Link to the problem, i used Big mod Link to Big mod implmentation for multiplication while calculating power as we need last ten digits so we have to modulo it by 1e10 which will overflow in C++.

Any type of help is appreciated. Thanks in advance.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/02/2021 09:57:12 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|