Codeforces!
Greetings from NITK. We will be hosting a CP contest, Inscription 2022 as part of our college's annual technical fest Engineer, on September 25th on CodeDrills. We have many more tech events, which you can check out over here.
Contest Details:
- Contest Link — Inscription 2022
- Date & Time — 25th September 2022, Sunday, 12:00 noon IST
- Duration — 2 hours and 30 minutes
- There will be 5-6 problems of varying difficulty.
- Will follow ICPC like scoring system (10 minutes penalty and 1 point per problem)
- Telegram group for clarifications: https://t.me/+SQPJYPL2XwE1OTM1
Registration for prizes:
- Do register here BEFORE the contest begins.
- Only Indian participants are eligible for prizes but everyone can participate.
- 1st rank will receive INR 2000
- 2nd rank will receive INR 1000
- 3rd rank will receive INR 1000
- 4th rank will receive INR 500
- 5th rank will receive INR 500
Panel:
The problem setting panel are:
- Setters: kaolinite, Dragonado, kavbhat, perrytheplatypus
- Testers: kaolinite, nandakishore323, kid-116, sathu.hebbar, rakshith21mohan
- Admin: Dragonado, janmansh
I would like to thank all of them for the round preparation. Along with them, I would also like to thank
- Balajiganapathi, deepa_panwar and Vichitr for developing the amazing CodeDrills platform and allowing us to host our contest!
Good Luck & Have Fun! Hope to see you participating!!
UPD: We have increased the duration of the contest from 2 hrs to 2.5 hrs. We have also increased the cash prize :)
UPD2: The contest is over and thank you everyone for participating! Editorials will published in a few days but feel free to discuss here. Please do upsolve the problems and give your feedback. Final ranklist will be out after some checks and winners will be contacted separately.
Thank you again!
Reminder! The contest starts in 15 minutes. Please do register for the prizes.
Just a doubt, are the samples for Make friends, not enemies correct (2nd output) correct ?
Yes, its correct.
How to solve problem F ?
I had a solution in which we have to find an optimal partition of $$$N$$$ members in which the difference between sizes of friends and enemies is minimum, this can be done by $$$\mathcal{O}(n^2)$$$ knapsack dp, which will obviously TLE.
I think there is a square-root optimization to this, but I don't know it yet, can anyone share their solution to this ?
you can refer it here(3rd technique) https://codeforces.com/blog/entry/100910
Thanks
It is very simple with bitsets
int n, m; cin >> n >> m; DSU go(n + 1); f(i, m) { int u, v; cin >> u >> v; go.merge(u, v); } bitset<N> go2 = 0; go2[0] = 1; f(i, n) { if (go.get_root(i) == i) { go2 |= (go2 << go.comp_size(i)); } } int res = inf; f(i, n) { if (go2[i]) { res = min(res, (n * (n - 1)) / 2 - (i * (n - i))); } } cout << res - m << '\n';Thanks a lot for pretty simple pseudo-code, it is easy to understand how knapsack works here!
What is the time complexity to calculate subset sum dp here ?
What was the intended solution for E: Long Range Query?
I did an implicit lazy segment tree which was a little too close to the memory limit.
https://codedrills.io/submissions/498331