C137's blog

By C137, history, 7 months ago, , World finals was yesterday, and I am sure you all got excited to take part in 2020 WF, so What are you waiting for? Start training hard :D

I would like to invite you all to take part in NCD 2019 qualification contest, NCD ( National Center of Distinguished students) is a high school in Syria, the best students in Syria study in NCD and they receive special programs. Every year top teams from NCD compete with university students in ACM contests and achieve great results.

The onsite contest will be held tomorrow you can check your timezone Apr/06/2019 18:30 (Moscow time), however the contest might be delayed for some time due to some delays from onsite event, you will be given 10-13 problems to be solved in 5 hours, the contest will be held on Codeforces gym, registration will be open 6 hours before the start of the contest.

The contest was prepared and tested by me Hasan, Math_Master, engineer_z, massoud8032000, Hash, Ghaffar_Daher and others.

We hope you find the problems interesting, see you on the standings page :D

Due to some unexpected events, the round was delayed 9 hours after the system testing of global round.

UPD the contest is over thank you for your participation, please share with us your feedback, and if you have any questions leave them in the comments below, and we will do our best to answer them.

Finally, congratiolations for TooNewbie who solved all the problems :D ncd, Comments (14)
 » The Link of the contest ?
•  » » Codeforces gym.
 » Auto comment: topic has been updated by C137 (previous revision, new revision, compare).
 » How i can solve m
•  » » Compare the numbers by taking logarithm on both sides and handling 0 valued corner cases. Code
 » How to solve A, E, G and J?
•  » » SpoilerA binary search + line sweepE Hashing + BITJ prefix sum
•  » » » Can you explain in more detail how it solves question A?
•  » » » » SpoilerWe will use binary search to solve the problem.While checking if there is an answer for some value $l$, It's clear that the center of the plus sign must have at least $l$ to the right, left, up and down of it. So what we do is for every horizontal segment we take $l$ from it's end and beginning, and for every vertical segment we take $l$ from up and down, leaving you with some vertical and horizontal segments in the middle, using line sweep, just check if there is intersection of at least one point between this segments.
 » The difficulty of the topic is very suitable for me. But how to solve the problem B?
•  » » SpoilerLet's solve the problem for a tree.The answer for a tree will be $n-1-l$ where $l$ is the length of the two farthest nodes in the tree, we can see that $l$ is the diameter of the tree.To solve the problem, we take any tree in the graph, and solve the problem for the resulting tree, with one difference that while calculating the diameter we consider only the bridges.
 » 5 months ago, # | ← Rev. 2 →   I have a $O(T * 90000 * log(90000))$ solution for problem G, my submission is here 54345315.I think it may can get the correct answer, but the time cost is about $1$ sec for $T = 1$ scenario.So if $T > 1$, I will get TLE.Do you guys know what the correct solution is?
•  » » There is no need for doing binary search. You can use some formulas. Codeconst long double EPS = 1e-6; const long double pi = 3.14159265359; long double get(long double a, long double b, long double x, long double y) { return max((long double)0, min(b, y) - max(a, x)); } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios_base :: sync_with_stdio(0); cin.tie(0), cout.tie(0); int T; cin >> T; while (T --) { int n, v, l, r; cin >> n >> v >> l >> r; long double x, y; for (int i = 1; i <= n; i++) { cin >> x >> y; cout << fixed << setprecision(4); if (x * 10 > 1.0 * v * v) { cout << "0.0000" << endl; continue; } if (l == r) { long double pos = 1.0 * v * v / 10 * sin(2.0 * r / 180 * pi); if (x - EPS <= pos && pos <= y + EPS) { cout << "1.0000"; } else { cout << "0.0000"; } cout << endl; continue; } long double lf = asin(10.0 * x / (1.0 * v * v)) * 180.0 / pi; long double rg = asin(min((long double)1.0, 10.0 * y / (1.0 * v * v))) * 180.0 / pi; long double llf = 180.0 - rg, rrg = 180.0 - lf; lf /= 2, rg /= 2; llf /= 2, rrg /= 2; long double total = get(lf, rg, l, r) + get(llf, rrg, l, r); cout << 1.0 * total / (r - l) << endl; } } return 0; }
•  » » » Thanks for your help!