### hocky's blog

By hocky, 5 weeks ago,

Hi Codeforces ଘ(੭*ˊᵕˋ)੭* ੈ♡‧₊˚!

We're delighted to invite you to COMPFEST 13 — Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred) on .

All problems were written and prepared by hocky, steven.novaryo, rama_pang, JulianFernando, Zap, Panji, richiesenlia, Sakamoto, and markus_geger.

I would also like to thank:

• KAN for helping to host the mirror round;
• (AVM.Martin, Ace_02), Berted, ardan, wijayareynaldo, and bukanYohandi for testing the round locally and improved the problems in early phases;
• UWr Kobor 53 (w0nsh, kobor, Fly_37), Almost Retired (KAN, Um_nik, Ekler), and errorgorn for testing the round and their really useful feedbacks;
• Universitas Indonesia, all the local committees, administrators, and managers of the whole COMPFEST event;
• prabowo for observing the contest;
• fushar for the Judgels platform used in the official contest; and finally
• MikeMirzayanov for the great Codeforces and our lovely Polygon!
• Extra thanks for rama_pang and steven.novaryo for working hard night 🌚 and day 🌞 making sure the problems are well-prepared (the contest wouldn't exist without their hands).

The duration will be 5 hours, consisting of 13 problems. You can register individually, but teams are preferred. You may expect relatively easier problems than ICPC Regional Contests. You may code parallely with several computers with your teammates and use prewritten codes and templates.

COMPFEST itself is an annual event hosted by Universitas Indonesia. It is the largest student-run IT event in Indonesia and competitive programming contest is one of the competitions hosted.

We've put great effort into preparing this contest and we hope that you will enjoy it. See you! ありがとう~! 🐾

UPD: Editorial is out!!! Editowial UωU

Congratulations to our top 5!

1. leziren (Retired_MiFaFaOvO, TLE, Miracle03)
2. heno239
3. bubble (riantkb, nuip, mtsd)
4. gisp_zjz
5. We Won it 0 time (aarr, afterall, Amoo_Safar)

• +418

 » 3 weeks ago, # |   +5 How did you add emojis in the blog? Everytime it says:- Emoji (and other unusual UTF-8 characters) are not supported
•  » » 3 weeks ago, # ^ |   +6 🤔
•  » » » 3 weeks ago, # ^ |   +11 How was the contwest UωU? I thought pweople would find K easiew than othews easy pwoblems (ಥ﹏ಥ)
•  » » » » 3 weeks ago, # ^ | ← Rev. 3 →   +8 I would have liked harder problems (what I mean is that the phase of read+routine work+implement lasted a bit longer than I'd've liked, not that there weren't also hard problems).K is probably scoreboard effect (combined with a sneaky special case).
•  » » » » » 3 weeks ago, # ^ |   +24 I see.. Thank you for the feedback!We were trying to fit in such vary skill range in our official contest. Hope you liked the problems ^^🐾~!
 » 3 weeks ago, # |   +31 Looking forward for exciting problemset! °(ಗдಗ。)°
 » 3 weeks ago, # |   -10 Somehow they're all during school :(
•  » » 3 weeks ago, # ^ |   0 wait I'm stupid there's no school on saturday
•  » » » 3 weeks ago, # ^ |   0 Yes you are from childhood
 » 3 weeks ago, # |   0 Very colourful post,indeed:)
•  » » 3 weeks ago, # ^ |   0 More like, LGBT post
 » 3 weeks ago, # |   +29 You guys should have made this rated event like div1,2 combined round etc...
 » 3 weeks ago, # |   +11 You may expect relatively easier problems than ICPC Regional Contests. this gives hope to look farward
 » 3 weeks ago, # |   +40 As a participant of the official contest, i can say that the problemset quality is good with really diverse problems
 » 3 weeks ago, # |   +47 As a tester, I'd say good luck and have fun!
 » 3 weeks ago, # |   0 I support this competition very much and hope to get contributions.
 » 3 weeks ago, # |   -16 The problems in previous round were of the level of div 1.
 » 3 weeks ago, # |   +11 How to solve L ?
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +21 You can formulate the problem as a 2D LIS, that can be solved with CDQ D&C. Implementation#include using namespace std; #define nl "\n" #define nf endl #define ll long long #define pb push_back #define _ << ' ' << #define INF (ll)1e18 #define mod 998244353 #define maxn 200010 ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn]; ll dp[maxn]; vector> v; struct fenwick { vector fn, rb; fenwick(): fn({}), rb({}) { ll i; fn.resize(maxn); for (i = 0; i < maxn; i++) fn[i] = -INF; } void upd(ll p, ll x) { // cout << "upd" _ p _ x << nf; while (p < maxn) { rb.pb(p); fn[p] = max(fn[p], x); p += (p & (-p)); } } ll pm(ll p) { // cout << "pm" _ p << nf; ll r = -INF; while (p > 0) { r = max(r, fn[p]); p -= (p & (-p)); } return r; } void clear() { for (auto u : rb) fn[u] = -INF; rb.clear(); } }; fenwick fn; bool cmp(array a, array b) { if (a[1] != b[1]) return (a[1] < b[1]); return (a[0] > b[0]); } void solve(ll l, ll r) { // cout << "solve" _ l _ r << nf; ll i; vector> v; if (l == r) return; ll mid = (l + r) / 2; solve(l, mid); for (i = l; i <= r; i++) v.pb({i, a[i], b[i]}); sort(v.begin(), v.end(), cmp); fn.clear(); for (auto u : v) { if (u[0] > mid) { dp[u[0]] = max(dp[u[0]], fn.pm(u[2]) + 1); } else { fn.upd(u[2], dp[u[0]]); } // cout << u[0] _ u[1] _ u[2] _ dp[u[0]] << nl; } solve(mid + 1, r); } int main() { ios::sync_with_stdio(0); cin.tie(0); #if !ONLINE_JUDGE && !EVAL ifstream cin("input.txt"); ofstream cout("output.txt"); #endif cin >> n; n++; a[1] = 0; b[1] = 1; for (i = 2; i <= n; i++) { cin >> a[i]; b[i] = -a[i] + i; dp[i] = -INF; } for (i = 1; i <= n; i++) v.pb({b[i], i}); sort(v.begin(), v.end()); for (i = 0; i <= n - 1; i++) b[v[i][1]] = i + 1; solve(1, n); for (i = 1; i <= n; i++) { // cout << dp[i] << ' '; res = max(res, dp[i]); } // cout << nl; cout << res << nl; return 0; } UPD: why downvotes? The solution is overkill, but the implementation is easy.
•  » » 3 weeks ago, # ^ |   +19 Maintain a vector(say track) of pairs {$i-a[i],a[i]$}. Sort it. Make an array b such that $b[i]=track[i].s$ . Find LIS of b.
 » 3 weeks ago, # |   0 How to solve C, F, M?
•  » » 3 weeks ago, # ^ |   +10
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   +10 M: It is just convex hull. We solve each column seperately. Note that the cost are independent for column and row. So we for each row, we find the best pole that minimize the sum for that specific. Then we just put everything inside a convex hull.code: 130595020C: perhaps i overcomplicated but let the sum a single array be $tot$. Then then $pref$ be the prefix sum array, we want some condition like $pref[r]-pref[l]=0$ or $tot+pref[r]-pref[l]=0$ or $2 \cdot tot + pref[r]-pref[l]=0$ etc.Since $k$ is a prime, we can store the prefix in a order that makes $0,tot,2 \cdot tot, \ldots$ appear contiguously.You can probably modify this for non-prime as well using some sort of binary lifting thing. Details left as exercise to reader.code: 130595163
 » 3 weeks ago, # | ← Rev. 2 →   0 will be editorial available?
•  » » 3 weeks ago, # ^ |   +11 The editorial will be posted soon
 » 3 weeks ago, # | ← Rev. 2 →   +8 why K so low accepteds? this fact, as well as useless constraint for r and c, gives me suspicious this solution 130590785 is wrong
•  » » 3 weeks ago, # ^ |   +23 You're overcomplicating it — 130583970.
•  » » » 3 weeks ago, # ^ |   0 oversolver is my second name
 » 3 weeks ago, # |   +10 How do you solve G?
 » 3 weeks ago, # | ← Rev. 2 →   +13 Can't imagine such high ratio of sucessfully hacking on problem D.I hacked 30 codes in total:-)
•  » » 3 weeks ago, # ^ |   0 what case did you use ?
•  » » » 3 weeks ago, # ^ |   0 a string with leading zeros
•  » » » » 3 weeks ago, # ^ |   0 like 0025 what is your expected output ?
•  » » » » » 3 weeks ago, # ^ |   0 0
•  » » » » » » 3 weeks ago, # ^ |   +13 i guess this should have been mentioned in the question that the string is not having leading zeroes by itself its just sad :(
•  » » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Yes i also thought that, because they mentioned it will be given as integer representation. But don't know actually either 00025 is a integer representation or not. Can anyone tell me that?
•  » » » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +16 My intended solution was like this.I've added the fifth sample to solve this ambiguity in the future.(ಥ﹏ಥ)
 » 3 weeks ago, # |   +5 MikeMirzayanovPlease update problem ratings as there is no need for plag-check in this round. Thanks in advance.
 » 3 weeks ago, # | ← Rev. 2 →   0 Retired_MiFaFaOvO came out of retirement?