# Invitation to CODICTION 2.0 2021 being held on 10th April

Hello everyone,

We would like to invite you to an online Coding contest CODICTION 2.0


This is an unprecedented opportunity for everyone who wishes to incite their mind gears with coding, programming and problem solving; all encompassing, an invaluable learning experience.
We invite you all to Come, Code and Conquer.

3 Likes

I enjoyed the contest, will we be able to upsolve it somehow? I got the 4th problem just one minute after the contest (made a small mistake in my last submission) Could I at least see if it’s right?

And why was the time limit for that one so tight? My lazy prop solution TLE’d, I feel as if increasing the TL to 2s would still not allow N^3 solutions to pass, while allowing this a bit less smart than the intended to pass. Great contest tho! Had a lot of fun solving!

Been late 1.5h for the contest, still made to top 12, so I’m satisfied

UPD: It still fails some test I feel a bit better about myself, it’s now in Practice mode. Thanks again for the contest!

UPD 2: I found the error in my code and fixed by comparing to fellow programmer’s code.

But can anyone tell why this code TLE’s, isn’t the complexity O(N^2 log N), right?

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 2e18;

int t, n;
int ar[1005][1005];
int arr[1005];
int tarr[1005];
int lazy[4005];
int tree[4005];

void build(int v, int tl, int tr) {
lazy[v] = 0;
if (tl == tr) {
tree[v] = arr[tl] - tl;
} else {
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}
}

int query(int v, int tl, int tr, int l, int r) {
if (lazy[v]) {
tree[v] += lazy[v];
if (tl != tr) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
}
if (tl > tr || tl > r || tr < l) return -INF;
if (tl >= l && tr <= r) return tree[v];
int tm = (tl + tr) / 2;
return max(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm + 1, tr, l, r));
}

void update(int v, int tl, int tr, int l, int r, int p) {
if (lazy[v]) {
tree[v] += lazy[v];
if (tl != tr) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
}
if (tl > tr || tl > r || tr < l) return;
if (tl >= l && tr <= r) {
tree[v] += p;
if (tl != tr) {
lazy[2 * v] += p;
lazy[2 * v + 1] += p;
}
return;
}
int tm = (tl + tr) / 2;
update(2 * v, tl, tm, l, r, p);
update(2 * v + 1, tm + 1, tr, l, r, p);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}

signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> ar[i][j];
}
}
if (n == 1) {
cout << ar[0][0] << '\n';
continue;
}
for (int i = 0; i < n; i++) {
tarr[i] = ar[n - 1][i];
}
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (!j) {
for (int k = 0; k < n; k++) {
arr[k] = tarr[k];
}
build(1, 0, n - 1);
}
tarr[j] = query(1, 0, n - 1, 0, n - 1) + ar[i][j];
if (j < n - 1) {
update(1, 0, n - 1, 0, j, -1);
update(1, 0, n - 1, j + 1, n - 1, +1);
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) ans = max(ans, tarr[i]);
cout << ans << '\n';
}
return 0;
}


Since I don’t believe an official editorial will be available, to y’all looking for detailed explanations, I’ll try my best to publish them. I’ve finished writing up the 1st, 2nd, 3rd, and 5th problem (4th will be out tomorrow). I still haven’t tried the remaining 2 problems, but hopefully I’ll be able to solve them.

For now, here are the unofficial editorials:

Hope you enjoy!

1 Like

Hey nichke, we really appreciate that you liked our contest. Please look forward to our future contests
For this question, about the expected time complexity, its O(N^2) and not O(N^2logN).

The official editorials will soon be posted. Please look forward to it.
Thank you

1 Like

I’m definitely looking forward to the next contest organized by your team, it was really a great experience.

I was a bit disappointed O(N^2 log N) solution didn’t fit the constraints, but at the end of the day it was just a lazy implementation, and forced me to think about O(N^2) solution, and I believe I can truly appreciate the problem now that I’ve solved it as it utilizies a much smarter trick instead of typical long algorithm.

Thanks again for such a beautiful problemset!

Here are the official editorials:

1 Like