Will the problems be arranged in increasing order of difficulty?
1 Like
No 
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. 
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 
Can’t check right now, but I belive that would fix it… 
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.
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
The intended complexity of the solution was m^2+nlogm,multi point evaluation should give TLE on later test cases ,did you use NTT with the 2^23 root of 1 mod p for multipoint evaluation?
Yeah, yeah I found that mistake 2 minutes ago… At first I didn’t return value in dfs, than I changed long long’s for int’s and when I fixed it, I forgot to return it back to long long… Thanks for your help though. It probably is the mistake.
Thanks!! What is the defination of the bad string? Do you want to mean given N string or something else.