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.
Yes. just the given N strings.
1 Like
WA_CODE
// #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;
}
Can you check this code too, I think I messed up the bruteforce part. Or if you can share your bruteforce part.
Can someone tell me why in this problem sample output is 2 .
As one of the possible scenarios can be
1st user votes for 5
2nd user votes for 5
3rd user votes for 4
4th user votes for 5
So, it could be 4 .
Actually the question asks for the minimum number of fake users needed
How to solve EAZYE ?
I think instead of X<=1 here X<1 should have been . Because why are you returning if X==1 , the answers could be got by not going with the X which has its value as 1.
1 Like
For some reason it returns 29 intead of 36 on doing this.
It runs correctly now. Cant Submit because upsolving is still not open
I just swapped the position of EACH loop and if(P==p+1) statement
1 Like