Invitation to CodeRed — 2020 by IIIT Allahabad

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Hello everyone !!

After 3 successful editions, Aparoksha is back with flagship coding event — CodeRed.

CodeRed 2020 consists of 2 rounds, Online preliminary round and Onsite final round. The online preliminary round will be a 3-hour long team event with a maximum size of the team being 3 members. The participants need not be from the same college/institution/organization. Problem set has 6/7 problems of varying difficulty. CodeRed 2020 is scheduled at March 11, 2020 at 22:00 IST

Last year CodeRed 2019 had 1271 teams registered, we are expecting higher participation this year. You can register your team here — CodeRed 2020 online preliminary round.

CodeRed, Alkhwarizm (Rated for all CodeChef contest) and Humblefool cup (Which happened a few days ago on Topcoder) are all among flagship coding events of Aparoksha — Techincal fest of Indian Institute of Information Technology (IIIT), Allahabad.

The total prize money is worth INR 125,000. Also, top 3 teams in the online preliminary round will get INR 3000, 2500 and 1500 respectively. The best 40 Indian teams will make it to the onsite round (To be held in IIIT Allahabad). All teams making it to the onsite round will get Aparoksha T-shirts.

Please fill out this Registration form to avail prizes — Register here

Problems have been set and tested by Mridul Gupta — mridul1809, Shivam Garg — shivamg_isc, Vaibhav Srivastava — dbest077, Ravi Chandra — rc_4594 , Ashutosh Kaushik — AK18, Kumar Raju — Eunoia__1729, priyanshu kumar — priyanshupkm.

Editorial will be posted here after the contest.

PS: Please Ignore the timing on the poster.

Upd1: 250 laddus for each member of top 3 teams. 9 hours to go.

Upd2: 30 minutes to go

upd3: the contest has been extended by 30 minutes, filling the registration form is mandatory to qualify for the on-site final

Upd4: Thanks for the overwhelming response. :D

Congratulations to the top 3 winners :D
1. NTT — tempura0224, tatyam, noimi
2. fast_coders — acraider, nitixkrai, fsociety00
3. Minimum Spanking Tree — hitman623, Enigma27, _shanky

Hints for the problems, detailed editorials will be posted later.

Hints :

Kem Party : CORE2006

By rc_4594

Let $$$dp(x,y)$$$ be Minimum Cost Of Reaching $$$(x,y)$$$ and placing a landmark over there.

We need to find value of $$$dp(N,M)$$$.

Consider the sequence of landmarked spots as $$$(x_1,y_1) , (x_2,y_2) ... (x_k,y_k) $$$

$$$dp(x_i , y_i)$$$ = $$$F(x_{i-1},y_{i-1}) \times (x_i - x_{i-1} + y_i - y_{i-1} ) + dp(x_{i-1},y_{i-1}) + T(x_i , y_i)$$$.

This becomes a DP Optimization problem which can be solved using Convex Hull Trick!

Expected Complexity : $$$ O(NM^2 ) $$$ (In case of large $$$M$$$ , transpose the matrix , it wont change the answer )

Solution

#include <iostream>
#include <vector>
#include <string.h>
#include <set>
#include <map>
#include <unordered_map>
#include <assert.h>
#include <algorithm>
#include <queue>
#include <bitset>
#include <stack>
#include <chrono>
#include <random>
#include <climits>
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define ll long long
#define MOD 1000000007 
#define INF 1000000000000000000
#define float double
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define uid uniform_int_distribution <int>
using namespace std;
// Read the question carefully and see all the given sample tests
// Think about the correctness before implementing
    
struct Line {
    mutable ll k, m, p;
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(ll x) const { return p < x; }
};
    
struct LineContainer : multiset<Line, less<>> {
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    const ll inf = LLONG_MAX;
    ll div(ll a, ll b) { // floored division
        return a / b - ((a ^ b) < 0 && a % b); }
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = inf; return false; }
        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(ll k, ll m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    ll query(ll x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return l.k * x + l.m;
    }
};
    
    
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<ll>> T(max(n, m), vector<ll>(min(n, m)));
    vector<vector<ll>> F(max(n, m), vector<ll>(min(n, m)));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if(n < m)
                cin >> T[j][i];
            else
                cin >> T[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if(n < m)
                cin >> F[j][i];
            else
                cin >> F[i][j];
        }
    }
    if(n < m)
        swap(n, m);
    LineContainer foo[m];
    ll res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if(i == 0 && j == 0) {
                foo[j].add(F[i][j], 0);
                continue;
            }
            ll ans = -INF;
            for (int k = 0; k <= j; k++) {
                if(i == 0 && k == j)
                    continue;
                ans = max(ans, foo[k].query(-i - j));
            }
            foo[j].add(F[i][j], ans + F[i][j] * (i + j) - T[i][j]);
            res = ans - T[i][j];
        }
    }
    cout << -res;
                
}

Bhaang Level Bam Bam Bole: CORE2005

By mridul1809

Given the structure of "graph" , we can move upwards only 1 step at a time.
The cycles are to create extra steps so we can get total number of steps as multiple of required number.
To go from A to B+1 , we can only consider the cycles starting and ending between A and B.
Let the lengths of all such cycles be $$$a_1,a_2,...,a_p$$$. We need to find a solution to the equation $$$x_1a_1 + x_2a_2 + ... + x_pa_p + B+1 - A = kY$$$
rearranging we get
$$$B+1-A = kY - ( x_1a_1 + x_2a_2 + ... + x_pa_p )$$$
$$$B+1-A = kY + z_1a_1 + z_2a_2 + ... + z_pa_p )$$$
we need to find if an integral solution to this equation exists such that
→ $$$k > 0$$$
→ $$$z_i <= 0$$$

If $$$B+1 - A = q \times GCD(k,a_1 , a_2 , .. a_n) $$$ (where $$$q$$$ is any +ve integer) we will always have a solution.

Now the question remains to find the GCD of lengths of all the cycles between A and B.

This can be done using Sorting Queries , Merge Sort Tree , Persistent Segment Tree , etc.

Expected Complexity : $$$ O(MlogM + QlogN) $$$ ($$$M$$$ is the number of cycles)

Solution ( Offline Queries )

//mridul1809
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define s(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define p(x) printf("%d ",x)
#define pl(x) printf("%lld ",x)
#define endl "\n"
#define vi vector <int>
#define pii pair <int,int>
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
#define max5 100005
#define max6 1000005
#define maxlong 20
struct cycle
{
    int l,r,s;
};
vector < cycle > cycles;

bool comp(cycle a , cycle b)
{
    return (a.r < b.r);
}

struct query {
    int a,b,i;
    ll y;
};

bool comp_query(query a , query b)
{
    return (a.b < b.b);
}
vector <query> queries(max5);
vector <string> answers(max5);
vector <int> tree(4*max5);
void update(int l ,int r , int pos , int val , int idx)
{
    if(l == r)
    {
        tree[idx] = __gcd(tree[idx] , val);
        return;
    }

    int mid = (l + r)/2;
    if(pos <= mid)
        update(l , mid , pos , val , 2*idx);

    else
        update(mid+1 , r , pos , val , 2*idx+1);

    tree[idx] = __gcd(tree[2*idx] , tree[2*idx+1]);
}
int query_tree(int l ,int r, int ql, int qr, int idx)
{
    if(ql > r || l > qr)
        return 0;

    if(ql <= l && r <= qr)
        return tree[idx];

    int mid = (l + r)/2;
    return __gcd(query_tree(l,mid,ql,qr,2*idx) , query_tree(mid+1,r,ql,qr,2*idx+1));
}
void solve()
{
    int n,i,m,t,j;
    s(n);
    for(i = 1; i <= n+1; i++)
    {
        s(m);
        for(j = 1; j <= m; j++)
        {
            s(t);
            cycles.pb({t , i , i - t + 1});
        }
    }
    sort(all(cycles) , comp);

    int q;
    s(q);
    for(i = 0; i < q; i++)
    {
        int a , b;
        ll y ;
        cin >> a >> b >> y;
        queries[i].a = a;
        queries[i].b = b;
        queries[i].i = i;
        queries[i].y = y;
    }


    sort(queries.begin() , queries.begin() + q, comp_query);

    int cc = 0;
    int qc = 0;
    while(qc < q)
    {
        while(cc < sz(cycles) && cycles[cc].r <= queries[qc].b)
        {
            update(1 , n , cycles[cc].l , cycles[cc].s , 1);
            cc++;
        }

        int limit = queries[qc].b;
        while(qc < q && queries[qc].b <= limit)
        {
            ll result = query_tree(1 , n , queries[qc].a , n , 1);
            result = __gcd(result , queries[qc].y);
            if((queries[qc].b-queries[qc].a+1)%result == 0)
                answers[queries[qc].i] = "YES";
            else
                answers[queries[qc].i] = "NO";
            qc++;
        }
    }

    for(i = 0; i < q; i++)
        cout << answers[i] << endl;

    return;
}
int main() 
{
    int t = 1;
    // s(t);
    while(t--)
        solve();

    return 0;
}

Cancel Cancel Cancel: CORE2007

Bhand Goggi And GCD : CORE2002

GPL 69: CORE2001

Bhindi Master and Graph : CORE2004

By shivamg_isc , AK18, Eunoia__1729

Here we first use simple bfs to calculate level of each node. Now let us assume that there are no values on the node and we need to find the node with minimum index closest to the root, which can be done by just sorting it and doing binary search. Now when we have values, sorting it by value will change the order of levels. Then, for each level keep the maximum value of the node, building segment tree of maximum of a segment. Now for each query we just find the minimum index idx such that [1,idx] contains the node with value greater than X(which can be done in $$$logN$$$ or $$$(logN)^2$$$. For each level we have pair of (value of node, node) stored in multiset. we can get our answer from that level's multiset. For updates, just erase from multiset and insert the required pair, and also update the segment tree.

Time complexity: $$$O(NlogN)$$$

Solution


#include<bits/stdc++.h>
using namespace std;
 
#define fi                      first
#define se                      second
#define pb                      push_back
#define endl                    '\n'
#define pii                     pair<int,int>
#define fast                    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define SZ(x)                   ((int)x.size())
 
#define FOR(i,a,b)              for(int i = a; i < b; ++i)
 
typedef long long ll;
 
void solve();
 
#define int ll
 
const int N = 1e5+2;
multiset<int> ms[N];
multiset<pii> dd[N];
std::vector<int> adj[N];
std::vector<int> dis(N,-1);
int t[4*N];
int a[N];
int n; 
 
 
void upd(int node, int x) {
        t[node] = x; // change
        return;
}
 
void build(int node = 1,int tl = 0,int tr = n - 1) {
        if(tl > tr) {
                return;
        }
        if(tl == tr) {
                t[node] = a[tl]; // change
                return;
        }
        int mid = (tl + tr) / 2;
        build(2 * node, tl, mid);
        build(2 * node + 1, mid + 1, tr);
        t[node] = max(t[2 * node] , t[2 * node + 1]); // change
}
 
void updateRange(int pos,int val, int node = 1, int tl = 0, int tr = n-1) {
        if(pos < tl or pos > tr) {
                return;
        }
        if(tl == tr) {
                upd(node,val);
                return;
        }
        int mid = (tl + tr) / 2;
        if(tl <= pos and pos <= mid)
            updateRange(pos, val, 2 * node, tl , mid);
        else
            updateRange(pos, val, 2 * node + 1, mid+1, tr);
        t[node] = max(t[2 * node] , t[2 * node + 1]); // change
}
 
int query(int val,int node = 1, int tl = 0, int tr = n-1) {
        if ( tr < tl) {
                return 0; // change
        }
        if(tl == tr) {
                return tl; // change
        }
        int mid = (tl + tr) / 2;
        int p = t[2*node];
        int q = t[2*node+1]; // change
        // debug(val,node, tl,tr, p ,q);
        if(p > val) {
            return query(val,2*node,tl,mid);
        }
        else if(q > val){
            return query(val,2*node+1,mid+1,tr);
        }
        return -1;
}
 
 
int32_t main()
{
        fast;
        solve();
}
 
int val[N];
 
void solve() {
        cin >> n;
        FOR(i,1,n+1) {
            cin >> a[i];
            val[i] = a[i];
        }
        FOR(i,0,n-1) {
            int A,b;
            cin >> A >> b;
            adj[A].pb(b);
            adj[b].pb(A);
        }
        queue<int> Q;
        Q.push(1);
        dis[1] = 0;
        ms[0].insert(a[1]);
        dd[0].insert({a[1],1});
        while(SZ(Q)) {
            int top = Q.front();
            Q.pop();
            for(auto i:adj[top]) {
                if(dis[i] == -1) {
                    dis[i] = dis[top] + 1;
                    ms[dis[i]].insert(a[i]);
                    dd[dis[i]].insert({a[i],i});
                    Q.push(i);
                }
            }
        }
        FOR(i,0,n) {
            if(SZ(ms[i])) {
                a[i] = *ms[i].rbegin();
            }
            else {
                n = i;
                break;
            }
        }
        build();
        int q;
        cin >> q;
        while(q--) {
            int T;
            cin >> T;
            if(T == 1) {
                int x,y;
                cin >> x >> y;
                ms[dis[x]].erase(ms[dis[x]].find(val[x]));
                ms[dis[x]].insert(y);
                dd[dis[x]].erase(dd[dis[x]].find(make_pair(val[x],x)));
                a[dis[x]] = *ms[dis[x]].rbegin();
                val[x] = y;
                updateRange(dis[x],*ms[dis[x]].rbegin());
                dd[dis[x]].insert({val[x],x});
            }
            else {
                int x;
                cin >> x;
                int p =  query(x);
                if(p == -1) {
                    cout << p << endl;
                    continue;
                }
                auto it = dd[p].upper_bound(make_pair(x+1,-1));
                cout << (*it).se << endl;
            }
        }
}

Scinist issue : CORE2003

Комментарии (19)

Показать архивные | Написать комментарий?

sanskarp

5 лет назад, # |

Looking forward to it.

→ Ответить

shivamg_isc

+14

The participants need not be from the same college/institution/organization.

thunderbird001

+11

Hope this is as exciting as last year's.

just2

Is it from 9pm or 10pm?

AK18

5 лет назад, # ^ |

10 pm. Ignore the timing on the poster. sorry for the inconvenience.

dunjen_master

← Rev. 2 →

Was $$${O(q*\sqrt{n}*log(n))}$$$ the intended complexity for Bhindi Master and Graph ?

AryaPawn

nope

BohdanPastuschak

Most likely there is $$$O(nlog(n))$$$ solution, however $$$O(nlog^2(n))$$$ passes easily.

Here is O(nlog(n)) solution. https://www.codechef.com/viewsolution/30325628

Can you briefly explain your solution ?

lets put all the vertices in the new array in order of distance from root. i.e. all vertices with distance 1 will come first, then all vertices with distance 2 and so on. now for finding minimum distance from root we need to query minimum index in the new array such that value at this index> value of query. We can do this with binary search + query on segtree in O(log^2(n)). we can also do this by doing binary search query on segtree. the rest part of the problem can be solved with just a set.

mkitkat

← Rev. 3 →

I brute forced but it didn't gave me TLE but I was getting WA.

Can you please explain what I was doing wrong.

Approach : I listed nodes at each level in a array of vector.

I made an array which contains the smallest element value at among the nodes at that level using the indexes.

https://pastebin.com/ymNdB9Z3

Here's the code

vi adj[N], b(N, -1);

int bfs(int n){
	int visited[n +1] = {0}, lev = -1;
	b.resize(n +1);
	b[1] = 0;
	deque <int> q;
	q.push_back(1), visited[1] = 1;
	while(!q.empty()){
		int cur = q.front();
		q.pop_front();
		for(auto itr:adj[cur]){
			if(!visited[itr]){
				visited[itr] = 1;
				b[itr] = b[cur] +1;
				q.push_back(itr);
			}
		}
	}
	for(int i = 1; i <= n; ++i)
		lev = max(lev, b[i]);
	return lev;
}

int32_t main()
{
	int n, q, u, v, c;
	cin >> n;
	vi a(n +1);
	scnarr(a, n); // input array
	for (int i = 0; i < n -1; ++i){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int lev = bfs(n);
	vi level[lev +1];

	// at each index of Level array : elements at that level are pushed
	for(int i = 1; i <= n; ++i){
		level[b[i]].push_back(i);
	}

	vi  _min(lev +1, 1000000000000000005);

	//finding min elem in each level and save to the _min array
	for(int i = 0; i <= lev; ++i){
		for(auto itr:level[i]){
			b[itr] = i;
			_min[i] = min(_min[i], a[itr]);
		}
	}

	cin >> q;
	while(q--){
		cin >> c;
		if(c == 1){
			cin >> u >> v;
			a[u] = v;
			_min[b[u]] = 1000000000000000005;
			for(auto itr:level[b[u]]){
				_min[b[u]] = min(_min[b[u]], a[itr]);
			}
		}else{
			cin >> u;
			int i = 0, ans = 1000000000000000005;
			for(; i <= lev; ++i){
				if(_min[i] > u){ //found the level closest to root 
					for(auto itr:level[i]){
						if(a[itr] == _min[i]){ //if multiple answers exists take the one with lowest index
							ans = min(ans, itr);
						}
					}
					cout << ans << endl;
					break;
				}
			}
			if(i == lev +1){
				cout << -1 << endl;
			}
		}
	}

}

Why did you store min elem at each level? You should have stored max at each level.
There may be a case as follows —
Level 1 values — { 3 }
Level 2 values — { 5, 11 }
Level 3 values — { 6, 7, 8}

If the query is 10, answer should be stored at level 2, but storing min as you have done will return -1.

goyalnikhil064

I submitted using square root decomposition and it worked for me :)

+12

How to solve Kem Party problem fast? My solution complexity is $$$O(n * m * min(n, m) * log n)$$$ with dynamic convex hull trick, which seems to be overkill...

acraider

← Rev. 4 →

+18

I too used 2D-Fenwick Tree + Convex Hull Trick to solve in O(N*M*log^3n ). [Quite same in runtime i guess].

With random weights, i don't think that the lines will follows some property allowing any offline processing.

geckods

+10

Great contest! Enjoyed the problems, even though I only solved 3. Can somebody explain the convex hull optimization trick used to solve Ken Party? Or show me a link that explains it? TIA

nubidy

Can anyone please explain why I am getting WA in Bhindi Master And Graph, I store the nodes at each level and the max value at each level and then if max value of a level is greater than X, I print the smallest node with value>X.

First of all, the complexity of your solution is Q*N which is not in the time limit :/

now while you are updating the value of the node, you are changing the max if the current update is larger than max at that level, which is wrong, as there might be multiple nodes with same value at a certain level or maximum value at that level might decrease etc.

keep values available at each level to update the maximum (to correct the logic of your code still it will exceed the time limit), to improve the complexity you may refer to hint posted above :)

Блог пользователя AK18