INVITATION TO CODUO-2021

We are excited to invite you to IIIT Lucknow’s annual team coding event CODUO, which will be organised in two ladders, one is prelims to be held on Codechef 14th April from 8:30 pm IST and the qualified teams will be invited to participate in the finals that will take place during the period of our annual techfest Equinox. Coduo will be a 3-hour contest ( individual participation or Team of 2 members).

Problem set has 8-9 problems of varying difficulty.

PRIZES:

The total prize money (for Winners of Finals) is worth INR 20,000.

Also, the top 3 teams in the Prelims will get 250 Codechef laddus each. We hope that you’ll enjoy the contest just as much as we did preparing it!

Good luck!!!

20 Likes

cutoff rank for finals?

@tamo11 as of now we have decided to invite top 15 teams for the finals. But the number can be increased later if we get more quality participation.

1 Like

Will the problems be arranged in increasing order of difficulty?

1 Like

No :sweat_smile:

The contest is from 8:30 pm IST, right?

1 Like

Yes starting in 5 minutes now

WTH is wrong with this code for SARKARI, I keep getting TLE, although I am quite sure O(4 \cdot N log N) should pass. I find the distance of every new office from each of the four current ones and later do DP with five states - the current new office I am at, and the remaining states describe the number of employees remaining at each of the starting offices. I print dp[0][0][0][0][0] in the end.

Here’s my code if anyone’s willing to help: CodeChef: Practical coding for everyone

BTW I enjoyed the problemset (though I made dumb mistakes in each of the problems, but hey that’s just how it is).

1 Like

You can even bruteforce for instead of doing a dp, that would only be 10^4 operations.
I’d be grateful if someone can tell me the mistake/counter-case in/for this code.
WA_CODE

Solutions Aren't visible
// #include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
#include <cstring>
#include <random>
#include <bitset>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
using namespace std;
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")
typedef long long ll ;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define CS custom_hash
#define vt vector 
#define F first
#define S second
#define pb push_back
#define em emplace_back
#define stoi stoll
#define all(v) (v).begin(),(v).end()                                            
#define mems(x, y) memset(x, y, sizeof(x))
#define sz(x) (int)(x).size()
#define ar array
#define endl "\n" 
#define PI acos(-1) 
#define umap unordered_map
#define gmap gp_hash_table
#define ld long double 
#define seb(n) __builtin_popcountll(n) 
#define LB lower_bound  
#define UB upper_bound 
// debugger credits: https://codeforces.com/blog/entry/68809 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
template <typename T, typename V>
void mdebug(map<T,vector<V>>m){
  for(auto x:m){
    cerr << x.first << " : [ " ;
    for(auto c:x.second)
      cerr << c << " ";
    cerr << "]"<<'\n' ;
  }
}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
//#pragma GCC optimize "trapv"
//template credits :William Lin(tmwilliamlin168)
#define F_OR(i, a, b, s) for (int i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)
template<class T> bool umin(T& a, const T& b) {
	return b<a?a=b, 1:0;
}
template<class T> bool umax(T& a, const T& b) { 
	return a<b?a=b, 1:0;
}
template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class T> void read(T& x) {
	cin >> x;
}
void read(double& d) {
	string t;
	read(t);
	d=stod(t);
}
void read(long double& d) {
	string t;
	read(t);
	d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
	read(h);
	read(t...);
}
template<class A> void read(vt<A>& x) {
	EACH(a, x)
		read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
	EACH(a, x)
		read(a);
}
string to_string(char c) {
	return string(1, c);
}
string to_string(bool b) {
	return b?"true":"false";
}
string to_string(const char* s) {
	return string(s);
}
string to_string(string s) {
	return s;
}
string to_string(vt<bool> v) {
	string res;
	FOR(sz(v))
		res+=char('0'+v[i]);
	return res;
}

template<size_t S> string to_string(bitset<S> b) {
	string res;
	FOR(S)
		res+=char('0'+b[i]);
	return res;
}
template<class T> string to_string(T v) {
    bool f=1;
    string res;
    EACH(x, v) {
		if(!f)
			res+=' ';
		f=0;
		res+=to_string(x);
	}
    return res;
}

template<class A> void pff(A x) {
	cout << to_string(x);
}
template<class H, class... T> void pff(const H& h, const T&... t) { 
	pff(h);
	pff(t...);
}
void print() {
	pff("\n");
}
template<class H, class... T> void print(const H& h, const T&... t) { 
	pff(h);
	if(sizeof...(t))
		pff(' ');
	print(t...);
}
struct PH{
  size_t operator()(const pair<int,int>&x)const{
    size_t ans=0;
    for(int i=0;i<x.first;i++)
      ans+=x.second;
    return ans;
  }
};
// struct custom_hash {
//   static uint64_t splitmix64(uint64_t x) {
//     // http://xorshift.di.unimi.it/splitmix64.c
//     x += 0x9e3779b97f4a7c15;
//     x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
//     x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
//     return x ^ (x >> 31);
//   }
//   size_t operator()(uint64_t x) const {
//     static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
//     return splitmix64(x + FIXED_RANDOM);
//   }
// };
// void DBG() {
// 	cerr << "]" << endl;
// }
// template<class H, class... T> void DBG(H h, T... t) {
// 	cerr << to_string(h);
// 	if(sizeof...(t))
// 		cerr << ", ";
// 	DBG(t...);
// }
// // #ifdef _DEBUG
// #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
// // #else
// // #define dbg(...) 0
// // #endif

template<class T> void offset(ll o, T& x) {
	x+=o;
}
template<class T> void offset(ll o, vt<T>& x) {
	EACH(a, x)
		offset(o, a);
}
template<class T, size_t S> void offset(ll o, ar<T, S>& x) {
	EACH(a, x)
		offset(o, a);
}
template<class T> void fk(T a) { 
  print(a) ;
  exit(0) ;
}
#define pf(n) return print(n)
#define int ll 
long const M=1e9+7;
const ll INF =1e18;
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).
//Syntax to create a min heap for priority queue
// priority_queue <T, vector<T>, greater<T>>pq ;

//make sure to clear the adjacency list for every test case 
// check mxN size 
//check if numbers are big use powl,sqrtl,builtin_popcountll()...... 
const int mxN=2e5+10,di[4]={1,0,-1,0},dj[4]={0,-1,0,1};
int n,m ,a[mxN],b[mxN],c[mxN],d[mxN],p;
vt<ar<int,2>>adj[mxN] ;
int k;
vt<int>dp[20] ;
void dijktras(int s){
  priority_queue<ar<int,2>,vector<ar<int,2>>,greater<ar<int,2>>> pq ;
  pq.push({0,s}) ;
  memset(d,0x3f,sizeof(d)) ;d[s]=0 ;
  while(pq.size()){
    ar<int,2> u= pq.top() ;
    pq.pop() ;
    if(u[0]>d[u[1]])
      continue ;
    for(ar<int,2> v:adj[u[1]]){
      if(u[0]+v[0]<d[v[1]]){
        d[v[1]]=u[0]+v[0] ;
        pq.push({d[v[1]],v[1]}) ;
      }
    }
  }
}
int find(int P,vt<int>e){
	if(P==p+1)
		return 0 ;
	EACH(x,e){
		if(x<=1)
			return 1e18 ;
	}
	int mn=1e18 ;
	FOR(i,k){
		e[i]-- ;
		umin(mn,dp[P][i]+find(P+1,e)) ;
		e[i]++ ;
	}
	return mn  ;

}
void solve(){		
	read(n,m) ;
	FOR(m){
		int x,y,z ;read(x,y,z) ;
		adj[x].pb({z,y}) ;
		adj[y].pb({z,x}) ;
	}
	read(k) ;
	FOR(i,k){
		read(a[i],b[i]) ;
		
	}
	read(p) ;
	FOR(i,1,p+1)
		read(c[i]) ;
	FOR(i,k){
		dijktras(a[i]) ;
		FOR(j,1,p+1)
			dp[j].pb(d[c[j]]) ;
	}

	vt<int>f ;
	FOR(k)
		f.pb(b[i]) ;
	int ans = find(1,f) ;
	print(ans==1e18?-1:ans) ;
	FOR(i,20)
	  dp[i].clear() ;
	FOR(i,0,n+2)
		adj[i].clear() ;
	mems(a,0) ;
	mems(b,0) ;
	mems(c,0) ;
	
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  //cout << setprecision(20) << fixed ;
  int T=1;
	read(T);
	FOR(_,T){
		// pff("Case #", _+1, ": ");
		solve();
	}
	return 0;
}


2 Likes

How to solve Lucky String?

What do you mena by brute-force? My DP is 10^4, you’d have like 4^10 operations if you did brute-force. Right?

1 Like

Does the tests of EZEY are really collect…? I think this problem can be solved just use multipoint evaluation, but I got WA (instead of TLE) and there are no solutions passed the task…

1 Like

yes…4^10=2^20 which should pass…mine did
how to solve crazy and lucky strings??

1 Like

Oh yeah, that’s still 100th of a second. But what is causing the issue in my code then?! It’s even faster in theory than both of your solutions. :slight_smile:

solutions aren’t visible yet…so i couldnt see ur code…maybe there has been some error in the distance calculation?

Oh, guess I’ll wait then. In case you can you can analyze it, here’s the code:

CODE
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int, int>
#define mp make_pair

const long long INF = 1e16;

priority_queue<pii, vector<pii>, greater<pii>> pq;
int t, n, m, k, p;
vector<pii> adj[200005];
vector<pii> vpp;
long long dist[200005][4];
vector<int> vi;
long long dp[30][30][30][30][30];

long long dfs(int cur, int a, int b, int c, int d) {
	if (cur == p) return 0;
	if (dp[cur][a][b][c][d] != -1) return dp[cur][a][b][c][d];
	long long res = INF;
	if (a < vpp[0].se - 1) res = min(res, dfs(cur + 1, a + 1, b, c, d) + dist[vi[cur]][0]);
	if (b < vpp[1].se - 1) res = min(res, dfs(cur + 1, a, b + 1, c, d) + dist[vi[cur]][1]);
	if (c < vpp[2].se - 1) res = min(res, dfs(cur + 1, a, b, c + 1, d) + dist[vi[cur]][2]);
	if (d < vpp[3].se - 1) res = min(res, dfs(cur + 1, a, b, c, d + 1) + dist[vi[cur]][3]);
	return dp[cur][a][b][c][d] = res;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	while (t--) {
		memset(dp, -1, sizeof dp);
		cin >> n >> m;
		for (int i = 0; i < m; i++) {
			int u, v, w; cin >> u >> v >> w;
			u--; v--;
			adj[u].push_back({v, w});
			adj[v].push_back({u, w});
		}
		cin >> k;
		for (int i = 0; i < k; i++) {
			int a, b; cin >> a >> b; a--;
			vpp.push_back({a, b});
		}
		cin >> p;
		for (int i = 0; i < p; i++) {
			int x; cin >> x; x--;
			vi.push_back(x);
		}
		for (int i = 0; i < n; i++) {
			dist[i][0] = dist[i][1] = dist[i][2] = dist[i][3] = INF;
		}
		for (int i = 0; i < k; i++) {
			pq.push(mp(0, vpp[i].fi));
			dist[vpp[i].fi][i] = 0;
			while (!pq.empty()) {
			int u = pq.top().se;
			int dd = pq.top().fi;
			pq.pop();
			if (dd > dist[u][i]) continue;
			for (auto it : adj[u]) {
				int v = it.fi;
				int w = it.se;
				if (dist[v][i] > dist[u][i] + w) {
					dist[v][i] = dist[u][i] + w;
					pq.push(mp(dist[v][i], v));
				}
			}
			}
		}
		for (int i = k; i < 4; i++) {
			vpp.push_back({0, 1});
		}
		long long res = dfs(0, 0, 0, 0, 0);
		if (res >= INF) cout << -1 << '\n';
		else cout << res << '\n';
		vpp.clear();
		vi.clear();
		for (int i = 0; i < n; i++) adj[i].clear();
	}
	return 0;
}

Anyways, I believe I found my mistake. Using int instead of long long in priority_queue :frowning: Can’t check right now, but I belive that would fix it… :frowning_face:

You can use DP also, your solution is not visible yet, for now you can see my solution for reference.
Link

1 Like

Build an aho-corasick automaton on the given N ‘bad’ strings, and then let dp[state][i] be the maximum answer you can get using the first i characters of S, and when you’re at state in the automaton. There are two transitions - either you use the i-th character, or you don’t.
Use the automaton to check whether any state corresponds to the end of some bad string and don’t consider the dp at such states.
The answer is the maximum of dp[state][n] over all valid states.

My submission

3 Likes

yes

not entirely sure how ints and longs work in cpp…but here, are you sure no overflow takes place?
i mean your pii is pair<int,int>, so…

2 Likes