Thank you all for participating in the round! We hope you had fun, as we did thinking of the problems. We would like to again thank our coordinator Vladosiya who made many suggestions for improving all problems here, and rejecting others.
Author: RobinFromTheHood
This problem requires a simple implementation. Set a variable (initially $$$0$$$) to represent the gold Robin has, and update it according to the rules as he scans through $$$a_i$$$, adding $$$1$$$ to answer whenever Robin gives away a gold.
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: list(map(int, input().split()))
###############################################
t = sint()
for _ in range(t):
n,k=mint()
a=aint()
cur=0
ans=0
for ai in a:
if ai >= k:
cur+=ai
elif ai==0 and cur:
ans+=1
cur-=1
print(ans)
#include <iostream>
using namespace std;
void work(){
int n,k;
cin >> n >> k;
int res = 0, gold = 0;
for (int i=0;i<n;i++){
int cur;
cin >> cur;
if (!cur && gold) gold--, res++;
else if (cur >= k) gold += cur;
}
cout << res << '\n';
}
int main(){
int t;
cin >> t;
while (t--) work();
return 0;
}
2014B - Robin Hood and the Major Oak
Author: ChairmanFMao; Developer: Filikec, RobinFromTheHood
The key observation is that $$$i^i$$$ has the same even/odd parity as $$$i$$$. Therefore, the problem reduces to finding whether the sum of $$$k$$$ consecutive integers ending in $$$n$$$ is even. This can be done by finding the sum of $$$n-k+1, n-k+2, ..., n-1, n$$$ which is $$$k*(2n-k+1)/2$$$, and checking its parity. Alternatively, one can count the number of odd numbers in those $$$k$$$ consecutive integers.
Note: Originally, the number of leaves grown was to be $$$i^m$$$ according to the fractal nature of life where $$$m$$$ is set to some integer. Developers decided to replace $$$m$$$ with $$$i$$$ for simplicity, following Filikec's suggestion.
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: list(map(int, input().split()))
###############################################
t = sint()
for _ in range(t):
n,k=mint()
if n&1:
odd=(k+1)//2
else:
odd=k//2
print('NO' if odd&1 else 'YES')
#include <iostream>
using namespace std;
void work(){
int n,k;
cin >> n >> k;
cout << (((n+1)*n/2 - (n-k)*(n-k+1)/2)%2?"NO":"YES") << '\n';
}
int main(){
int t;
cin >> t;
while (t--) work();
return 0;
}
Author: RobinFromTheHood; Developer: Filikec, RobinFromTheHood
If we sort the wealth in increasing order, then the $$$j$$$-th person must be unhappy for Robin to appear, where $$$j=\lfloor n/2 \rfloor +1$$$ if $$$1$$$-indexing or $$$j=\lfloor n/2 \rfloor$$$ if $$$0$$$-indexing. We need $$$a_j < \frac{s+x}{2*n}$$$, where $$$s$$$ is the original total wealth before $$$x$$$ gold from the pot was added. Rearranging the equation gives $$$x>2*n*a_j-s$$$. Because $$$x$$$ is a non-negative integer, we arrive at the answer $$$max(0,2*n*a_j-s+1)$$$.
Of course, this problem can also be solved by binary search, with two caveats. First, one needs to be careful to avoid comparison between integer and float types, as rounding errors could create issues. You can always avoid division by $$$2n$$$ by multiplying it out. Second, one needs to pick the upper limit carefully to ensure it is large enough. Note that $$$2*n*max(a)$$$ can serve as the upper limit for the binary search for $$$x$$$, because that would push the average to be strictly above $$$2*max(a)$$$ and everyone except the one with the pot of gold would be unhappy.
There are $$$2$$$ edge cases, $$$n=1, 2$$$, where the condition for Robin can never be reached, because the richest person will always be happy (at least in this problem, though perhaps not IRL). ChatGPT struggled to identify these edge cases, so it was tempting to leave at least one hidden. Following testing, we decided to give both in samples to reduce frustration.
Note: Wealth inequality is better measured by the Gini coefficient which is too involved for this problem. Our criterion is a crude approximation for the Gini coefficient, and is equivalent to setting the mean to median ratio (a well known indicator for inequality) to $$$2$$$. For a random distribution, this ratio is close to $$$1$$$. Interestingly, this ratio for UK salary distribution is around $$$1.2$$$, so no Robin yet.
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: list(map(int, input().split()))
###############################################
t = sint()
for _ in range(t):
n=sint()
w=aint()
if n<3:print(-1);continue
tot=sum(w)
w.sort()
print(max(0,2*n*w[n//2]-tot+1))
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void work(){
int n;
cin >> n;
long long sum = 0;
vector<long long> v(n);
for (auto &c : v) cin >> c, sum += c;
sort(v.begin(),v.end());
if (n < 3){
cout << "-1\n";
return;
}
cout << max(0LL,v[n/2]*2*n-sum+1) << '\n';
}
int main(){
int t;
cin >> t;
while (t--) work();
return 0;
}
2014D - Robert Hood and Mrs Hood
Author: RobinFromTheHood; Developer: ChairmanFMao; RobinFromTheHood
Since the number of days $$$n$$$ is capped, we can check all possible start day $$$x$$$ in range $$$[1,n-d+1]$$$ (so that the duration of $$$d$$$ days would fit). We would like to find the number of overlapped jobs for each value of $$$x$$$.
A job between days $$$l_i$$$ and $$$r_i$$$ would overlap with the visit if the start day $$$x$$$ satisfies $$$l_i-d+1 \le x \le r_i$$$. Naively, this range update could be potentially $$$O(n)$$$, which is too slow. However, noting the start and end, each job update could be done in $$$2$$$ operations. We add $$$+1$$$ at $$$l_i-d+1$$$ and $$$-1$$$ at $$$r_i+1$$$, and after all jobs are recorded, we will take a prefix sum to work out the number of overlapped jobs for each $$$x$$$. When $$$l_i-d+1$$$ drops below $$$1$$$, we simply use $$$1$$$ to avoid lower values which are not being considered for $$$x$$$.
The time complexity is $$$O(n)$$$.
Note: Robin's risky jobs are generally deemed illegal by the Sheriff of Nottingham. Robert is practical and helpful. Like all good parents, Mrs Hood is a worrier.
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: list(map(int, input().split()))
###############################################
t = sint()
for _ in range(t):
n,d,k=mint()
ct=[0]*(n+2)
for _ in range(k):
L,R=mint()
ct[max(1,L-d+1)]+=1
ct[R+1]-=1
cur=0
mn=10**6;mni=0
mx=-1;mxi=0
for i in range(1,n-d+2):
cur+=ct[i]
if cur<mn:mn=cur;mni=i
if cur>mx:mx=cur;mxi=i
print(mxi,mni)
#include <iostream>
#include <vector>
using namespace std;
void work(){
int n,k,d;
cin >> n >> d >> k;
vector<int> ss(n+1),es(n+1);
for (int i=0;i<k;i++){
int a,b;
cin >> a >> b;
ss[a]++;
es[b]++;
}
for (int i=0;i<n;i++) ss[i+1] += ss[i];
for (int i=0;i<n;i++) es[i+1] += es[i];
int most = 0;
int robert = 0;
int mrs = 0;
int least = 1e9;
for (int i=d;i<=n;i++){
int cur = ss[i] - es[i-d];
if (cur > most) most = cur, robert = i-d+1;
if (cur < least) least = cur, mrs = i-d+1;
}
cout << robert << ' ' << mrs << "\n";
}
int main(){
int t;
cin >> t;
while (t--) work();
return 0;
}
2014E - Rendez-vous de Marian et Robin
Author: RobinFromTheHood; Developer: Filikec, RobinFromTheHood
This problem builds on the standard Dijkstra algorithm. So please familiarise yourself with the algorithm if not already.
In Dijkstra algorithm, a distance vector/list is used to store travel times to all vertices, here we need to double the vector/list to store travel times to vertices arriving with and without a horse. If a vertex has a horse, then it's possible to transition from without horse to with horse there. The Dijkstra algorithm is then run as standard.
What if a horse has already been taken by Marian when Robin arrives, and vice versa? Well, the optimal solution would not require the second person to arrive to use the horse, because the first to arrive could simply wait for the second to arrive, giving an earlier meeting than whatever is possible if the second to arrive had to use the horse and go elsewhere. Therefore, for any vertex, $$$1$$$ horse is sufficient.
We run Dijkstra algorithm twice to find the fastest time Robin and Marian could reach any vertex $$$i$$$ as $$$tR(i)$$$ and $$$tM(i)$$$. The earliest meeting time at a given vertex $$$i$$$ is $$$max(tR(i),tM(i))$$$, and we need to check all vertices.
The time complexity is that of Dijkstra algorithm which, in this problem, is $$$O(n \log n)$$$.
import sys
from heapq import *
input = lambda: sys.stdin.readline().rstrip("\r\n")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: list(map(int, input().split()))
###############################################
def dij(ss):
dis=[[big]*2 for _ in range(n+1)]
dis[ss][0]=0
chkd=[[0]*2 for _ in range(n+1)]
Q=[(0,ss,0)]
while Q:
v,i,ride=heappop(Q)
if chkd[i][ride]:continue
chkd[i][ride]=1
ride|=H[i]
for j,w in g[i]:
nv=v+w//2*(2-ride)
if nv<dis[j][ride]:dis[j][ride]=nv;heappush(Q,(nv,j,ride))
return dis
#################################################
big=float('inf')
t = sint()
for _ in range(t):
n,m,h=mint()
H=[0]*(n+1)
for i in aint():H[i]=1
g = [[] for _ in range(n + 1)] #set up adjacency matrix
for _ in range(m):
u, v, w = mint()
g[u].append((v,w))
g[v].append((u,w))
dM=dij(1)
dR=dij(n)
best,idx=big,0
for i in range(1,n+1):
tmp=max(min(dM[i]),min(dR[i]))
if tmp<best:idx=i;best=tmp
print(best if best!=big else -1)
#include <iostream>
#include <vector>
#include <set>
using namespace std;
void dijkstra(int s, vector<vector<long long>> &d, vector<vector<pair<int,long long>>> &graph, vector<bool> &hs){
auto cmp = [&](auto &a, auto &b){return make_pair(d[a.first][a.second],a) < make_pair(d[b.first][b.second],b);};
set<pair<int,int>,decltype(cmp)> q(cmp);
d[s][0] = 0;
q.insert({s,0});
while (q.size()){
auto [curv,curh] = *q.begin();
q.erase(q.begin());
bool horse = (curh || hs[curv]);
for (auto &[neighv, neighd] : graph[curv]){
long long dist = horse?neighd/2:neighd;
if (d[neighv][horse] > d[curv][curh] + dist){
q.erase({neighv,horse});
d[neighv][horse] = d[curv][curh] + dist;
q.insert({neighv,horse});
}
}
}
}
void work(){
int n,m,h;
cin >> n >> m >> h;
vector<bool> hs(n);
vector<vector<pair<int,long long>>> graph(n);
for (int i=0;i<h;i++){
int c;
cin >> c;
hs[--c]=1;
}
for (int i=0;i<m;i++){
int a,b,c;
cin >> a >> b >> c;
a--,b--;
graph[a].push_back({b,c});
graph[b].push_back({a,c});
}
vector<vector<long long>> d1(n,vector<long long>(2,1e18));
vector<vector<long long>> d2(n,vector<long long>(2,1e18));
dijkstra(0,d1,graph,hs);
dijkstra(n-1,d2,graph,hs);
long long best = 1e18;
auto get = [&](int a){return max(min(d1[a][0],d1[a][1]),min(d2[a][0],d2[a][1]));};
for (int i=0;i<n;i++) best = min(best,get(i));
cout << (best==1e18?-1:best) << '\n';
}
int main(){
int t;
cin >> t;
while (t--) work();
return 0;
}
Author: Filikec; Developer: Filikec
An important observation is that strengthening a base only influences its neighbors, so we can just keep consider adjacent nodes as later ones are not affected. Let's consider induction to solve this problem. Let $$$d[i][0]$$$ denote the most gold from node $$$i$$$ and all its children if we don't strengthen node $$$i$$$ and $$$d[i][1]$$$ if we do strengthen the node $$$i$$$.
Base case: If the current node $$$i$$$ is a leaf, $$$d[i][0] = 0$$$, $$$d[i][1] = a_i$$$.
Induction step: Consider the node $$$i$$$ with children $$$1 \dots m$$$. Assume that all nodes $$$1 \dots m$$$ are already calculated. If we don't strengthen the node $$$i$$$, $$$d[i][0] = {\sum_{j = 1}^m max(d[j][0],d[j][1])}$$$. If the node $$$i$$$ is strengthened, $$$d[i][1] = a_i + {\sum_{j = 1}^m max(d[j][0],d[j][1]-2\cdot c)}$$$.
Time complexity — $$$O(n)$$$.
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: list(map(int, input().split()))
###############################################
T = sint()
for _ in range(T):
n,c=mint()
a=aint()
g=[[] for _ in range(n)] #set up adjacency matrix
for _ in range(n - 1):
u,v = map(int, input().strip().split())
u-=1;v-=1
g[u].append(v)
g[v].append(u)
dp=[[0]*n,a]
kids=[[] for _ in range(n)]
vis=[0]*n
Q=[0]
while Q:
i=Q.pop()
if i>=0:
if vis[i]:continue
vis[i]=1
Q.append(~i)
for j in g[i]:
if vis[j]:continue
Q.append(j)
kids[i].append(j)
else:
i=~i
for j in kids[i]:
dp[0][i]+=max(dp[0][j],dp[1][j])
dp[1][i]+=max(dp[0][j],dp[1][j]-2*c)
print(max(dp[0][0],dp[1][0]))
#include <iostream>
#include <vector>
using namespace std;
void work(){
int n,k;
cin >> n >> k;
vector<long long> v(n);
vector<vector<int>> g(n);
for (auto &c : v) cin >> c;
for (int i=0;i<n-1;i++){
int a,b;
cin >> a >> b;
a--,b--;
g[a].push_back(b);
g[b].push_back(a);
}
vector<bool> vis(n);
vector<vector<long long>> d(n,vector<long long>(2));
auto dfs = [&](auto &&dfs, int cur, int p) -> void {
for (auto &neigh : g[cur]){
if (neigh == p) continue;
dfs(dfs,neigh,cur);
d[cur][1] += max(d[neigh][0],d[neigh][1] - 2*k);
d[cur][0] += max(d[neigh][0],d[neigh][1]);
}
d[cur][1] += v[cur];
};
dfs(dfs,0,-1);
cout << max(0LL,max(d[0][0],d[0][1])) << '\n';
}
int main(){
int t;
cin >> t;
while (t--) work();
return 0;
}
Author: RobinFromTheHood; Developer: Filikec, RobinFromTheHood
The key for this problem is the use of a stack, where last item in is the first item out. As we scan through the diary entries, we will only drink till the day of the next entry. If there is left over milk, we will push them into the stack with number of pints and the day they were acquired. If there isn't enough milk to reach the next entry, we will check the stack for left overs. Careful implementation is required to check for expiry day. It might help to append a fictitious entry with large day number and $$$0$$$ pints. Since every pop from the stack accompanies either the processing of a diary entry or permanently removing a stack item, the number of stack operation is $$$O(n)$$$.
Since diary entries are presented in sorted order, the time complexity is $$$O(n)$$$.
Note: Originally, this problem has an easy version, where Little John drinks the oldest drinkable milk first. However testers and the team were uncertain about the difficulties of the two problems, and there was concern that they are too 'implementation heavy'. For the sake of balance, only the hard version is presented here as G. However, you may wish to try the easy version yourself. I recall my parents telling me to use the oldest milk first, and now I say the same to my children. Has it all been worthwhile?
import sys
input = lambda: sys.stdin.readline().rstrip("\r\m")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: tuple(map(int, input().split()))
###############################################
t = sint()
for _ in range(t):
n,m,k=mint()
a=[]
for _ in range(n):a.append(aint())
#a.sort() #not needed as entries are sorted
####Extravagant
happy=0
stack=[]
a.append((10**12,0))
for pt in range(n):
cur_day,cur_milk=a[pt]
cur_milk=min(cur_milk,m*k)
days,extra=divmod(cur_milk,m)
good=min(a[pt+1][0]-cur_day,days)
happy+=good
cur_day+=good
cur_milk-=good*m
if cur_day==a[pt+1][0] and cur_milk:stack.append((cur_day-good,cur_milk))
while cur_day<a[pt+1][0] and stack and cur_day<stack[-1][0]+k:
old,v=stack.pop()
cur_milk+=v
days,extra=divmod(cur_milk,m)
good=min(a[pt+1][0]-cur_day,days,old+k-cur_day)
happy+=good
cur_day+=good
cur_milk-=good*m
if cur_day==a[pt+1][0] and cur_milk:stack.append((old,cur_milk))
print(happy) #say hello to Wibbles the cat who also likes milk
#include <iostream>
#include <map>
#include <list>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
void work(){
int n,m,k;
cin >> m >> n >> k;
map<ll,ll> days;
for (int i=0;i<m;i++){
int a,b;
cin >> a >> b;
days[a] += b;
}
days[1e18] = 0;
ll curd = 1;
ll got = 0;
ll res = 0;
list<pll> pq;
for (auto &cur : days){
while (pq.size() && curd < cur.first){
auto [d,x] = pq.front();
pq.pop_front();
if (d+k-1 < curd) continue;
else if (d > curd) curd = d, got = 0;
if (n-got > x) got += x;
else{
ll sat = min(curd + (x-n+got)/n + 1,min(d + k, cur.first));
ll newx = x-(sat-curd)*n+got;
if (newx) pq.push_front({d,newx});
res += sat-curd;
got = 0;
curd = sat;
}
}
pq.push_front(cur);
}
cout << res << '\n';
}
int main(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int t;
cin >> t;
while (t--) work();
return 0;
}
Author: Filikec; Developer: Filikec
Sheriff can never win. This is quite obvious as Robin is the first to pick and both just keep picking the current biggest number. This means that Sheriff can at best get a tie — this happens if and only if all elements have even appearance. The segment $$$a_l \dots a_r$$$ is a tie if and only if there's no element that appears an odd number of times.
There are multiple ways to solve this problem. Two are outlined.
Mo's algorithm — offline
We can keep the count of appearances of each element using an array in $$$O(1)$$$ time. Sort the queries into blocks of size $$${\sqrt n}$$$. Keep updating the boundaries of the current segment and the total count of elements that appear an odd number of times. Sheriff can tie iff there is no odd appearance.
Time complexity — $$$O((n+q){\sqrt n})$$$.
Xor hashing
Consider the prefixes of all targets. If the current segment is $$$a_l \dots a_r$$$, there's no element with odd appearance if and only if the set of numbers with odd appearance in $$$a_1 \dots a_{l-1}$$$ is the same as $$$a_1 \dots a_r$$$. We can check if two prefixes have the same set of elements with odd appearance with xor hashing.
Time complexity — $$$O(n+q)$$$.
#xor hashing
import sys
import random
input = lambda: sys.stdin.readline().rstrip("\r\n")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: list(map(int, input().split()))
nmax=1<<64
tmp=random.randint(1,nmax)
T=sint()
for _ in range(T):
n,q=mint()
v=aint()
w=[0]*n
hsh=dict()
rev=dict()
for i in range(n):
if v[i] not in hsh:
while tmp in rev:tmp=random.randint(1,nmax)
hsh[v[i]]=tmp
rev[tmp]=v[i]
w[i]=hsh[v[i]]
psv=[0]
for i in v:psv.append(psv[-1]^i)
psw=[0]
for i in w:psw.append(psw[-1]^i)
for _ in range(q):
L,R=mint()
ans='YES' if psv[R]^psv[L-1]==0 and psw[R]^psw[L-1]==0 else 'NO'
print(ans)
#Mo's algorithm
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;
int K = 500;
int Cnt[1000001];
void work(){
int n,q;
cin >> n >> q;
vector<int> v(n);
for (auto &c : v) cin >> c, Cnt[c] = 0;
vector<array<int,3>> qs(q);
for (int i=0;i<q;i++) cin >> qs[i][0] >> qs[i][1], qs[i][2] = i;
auto cmp = [&](array<int,3> &a, array<int,3> &b){return make_pair(make_pair(a[0]/K,a[1]/K),a) < make_pair(make_pair(b[0]/K,b[1]/K),b);};
sort(qs.begin(),qs.end(),cmp);
int l, r;
l = r = 0;
int odd = 1;
Cnt[v.front()]++;
vector<bool> res(q);
for (auto &c : qs){
c[0]--,c[1]--;
while (r < c[1]){
Cnt[v[++r]]++;
if (Cnt[v[r]]%2) odd++;
else odd--;
}
while (l > c[0]){
Cnt[v[--l]]++;
if (Cnt[v[l]]%2) odd++;
else odd--;
}
while (l < c[0]){
Cnt[v[l]]--;
if (Cnt[v[l++]]%2) odd++;
else odd--;
}
while (r > c[1]){
Cnt[v[r]]--;
if (Cnt[v[r--]]%2) odd++;
else odd--;
}
res[c[2]] = odd;
}
for (bool c : res) cout << (c?"NO\n":"YES\n");
}
int main(){
int t;
cin >> t;
while (t--) work();
return 0;
}
#xor hashing
#include <iostream>
#include <vector>
#include <map>
#include <random>
#include <set>
using namespace std;
void work(){
int n,q;
cin >> n >> q;
vector<unsigned long long> v(n);
for (auto &c : v) cin >> c;
random_device rd;
mt19937_64 gen(rd());
map<unsigned long long, unsigned long long> mapping;
set<unsigned long long> used = {0};
for (auto &c : v){
unsigned long long random;
if (!mapping.contains(c)){
do{
random = gen();
}while (used.contains(random));
used.insert(random);
mapping[c] = random;
}else{
random = mapping[c];
}
c = random;
}
vector<unsigned long long> xor_pref(n+1);
for (int i=0;i<n;i++) xor_pref[i+1] = xor_pref[i] ^ v[i];
for (int i=0;i<q;i++){
int l,r;
cin >> l >> r;
cout << ((xor_pref[r]^xor_pref[l-1])?"NO\n":"YES\n");
}
}
int main(){
int t;
cin >> t;
while (t--) work();
return 0;
}
gigafast editorial 😬 btw for problem H, isn't checking (r — l) odd and number of uniq element is sufficient to answer query? I received WA2 with that approach
the number of unique elements can be greater than 1 and yet the array is not losing.
Here is an example:
[3, 3, 1, 1]
oh now I see, so frequency of element between l to r should be even
Exactly!
If by
number of uniq element
you mean printing YES iff the number of unique elements is 1, this misses other cases where its possible.Consider the following test case:
Robin picks target 4 ($$$a_i = 2$$$). Sheriff picks target 3 ($$$a_i = 2$$$). Robin picks target 2 ($$$a_i = 1$$$). Sheriff picks target 1 ($$$a_i = 1$$$).
The sum of both their targets is $$$3$$$ and no better answer is possible for Robin. So the sheriff can always win.
the only check you need is whether any element appears an odd amount of times. if yes then the answer is no, and otherwise the answer is yes
Lightning fast editorial
Wow , problem G is so simple. Solid Problemset!
Problems are good, except for H which is a bit too common (but still educational
:)
). Fast editorial!I have never seen the H idea before, so it's appreciated
gonna hate myself for the rest of my life for messing up C.... i was sooooo closeeee
Same as you, I used binary search to solve C ,and I was deeply annoyed by the edge situations mentioned in editorials … A so simple problem costs more than 1 hours
I solved C in 19 minutes but wrote r=1e6 unstead of 1e18. It took me until 1h30 to solve it T-T
kesa7 ya Pezzzzz
H should be placed before F imo
We were discussing placing H differently but ended up placing it here as it needs specific algorithms. G could be solved with nothing advanced.
I guess despite the fact that H turned out to be a famous problem, F didn't require any advanced algorithms knowledge. So it has a better chance to be solved by lower rated people
For problem C I used binary search on the possible values of x. When I made the upper bound of
x = n*max_element+1
it gave WA but when I gave it as1e18
it was accepted. Can someone explain this?EDIT: originally wrote
2*max_element+1
. Updated ton*max_element+1
which is the upper bound that gave WA instead of2*n*max_element
I also encountered a similar issue when I solved the "C — Maximum Median" problem. I'd like to understand the story or concept behind this problem .
maximum value of x can be (n * max_element + 1), in the case where all values are equal to max element
Sorry, made a typo. I set the upper bound to n*max_element+1 in my solution but got WA before changing it to 1e18. What is wrong here? Is the division causing problem? Why is
2*n*max_element
the correct upper bound?here is accepted 282332784
and WA version 282330368
F is really nice. Consider a parent and child combination. If parent is not strengthened, then the answer remains unchanged. If the parent is strengthened then there are two cases:
If child is not strengthened, then they lose
c
gold but it doesn't matter as it is not going to be counted anyway.If child is also strengthened, then it costs
c
from the parent, but now the deficit ofc
from the child also counts, so in total we geta[i] - 2*c
in this case.thanks!
This explanation of the key moment should have been included in the editorial for problrm F to be worth its purpose.
Finally understand!thanks!
Glad we have proper anti-wrong-Dijkstra tests on E :)
I'm happy you noticed :)
wdym by "wrong-Dijkstra" ?
Let me introduce this to you :)
I have had this blog starred for weeks. Thanks for reminding me.
its funny how you got hacked on E
I made a few post-contest submissions to see if we have strong tests. It turned out the
inf
test wasn't as strict, so hacked them with the largestinf
tests. My contest submission survived though.Why do we need random numbers for the xor solution in H? Wouldn't the xor always be 0 if every element in a range occurred an even # of times?
If you xor the original numbers instead of random ones, some of them may emit a zero even if not every element occurs $$$2k$$$ times. E.g.
1 2 3
Idk why I didn't think of that lol ty
But it is still possible that the random numbers generated could emit a zero too, even if they don't appear 2k times.
Yes, so the algorithm is not deterministically correct. But we assume that the probability of this situation is very small.
because of that reason, I solved it using segment tree. https://mirror.codeforces.com/contest/2014/submission/282578178
please can you elaborate how probability works on the advanced problems!!
There is a tutorial of xor hashing: link. And in the blog is the detailed elucidation about the probability of hash collision.
thanks a lot!!
hey can you help me with this problem, here are my submissions for the same without map and with map only the without map one got accepted but I used a single prime num to generate hashes so I am afraid that on vast testcases, this might fail due to collision, also I want to solve it by hashing
yes but the XOR can also be zero even though the range has some elements occuring odd number of times.
for example:
[1, 2, 3]
still i didn't understand E :)
it's a famous algorithm called dijikstra
try to learn about it first
A job between days li and ri would overlap with the visit if the start day x satisfies li−d+1 ≤ x ≤ ri
I didn't get this statement. Can somebody explain this?
We can rearrange $$$l_i - d + 1 \le x$$$ to get $$$l_i \le x + d - 1$$$. If a visit starts on Day $$$x$$$ and spans $$$d$$$ days, Day $$$x + d - 1$$$ is exactly the last day of the visit. So $$$l_i \le x + d - 1$$$ means the job starts earlier than or exactly when the visit ends.
Likewise, $$$x \le r_i$$$ means that the job ends later than or exactly when the visit starts.
More intuitively, they overlap when there is at least one day where you would have to do some job while visited by your mother/brother.
Ohk now I got it! Thanks
I don't understand dijkstra probably. How does it get the correct shortest paths from source 1 for the sample test 5.
How does it go to $$$2$$$ and take the horse and come back ? Since
d[source=1] = 0
, I assume it(the source) would not (and should never ?)get relaxed by $$$2$$$. Also, there isn't any edge $$$E(2,3)$$$.You have to calculate two times for each vertex. The fastest time to get there without using a horse and the fastest time to get there using a horse. If you get on a horse at vertex v, then you continue traversing the graph, but you have to start updating the times for when you're on a horse.
So in your example, you get on a horse at vertex 2 then go to vertex 1 since d_with_horse[1] = INF
I see, thanks.
You can define the "graph" as a pair of node, state and do dijkstra on this modified graph. Here, for a node u, the elements in the modified graph are (u, 0) for no horse and (u, 1) for a horse. Sometimes this state can have more values, be bitwise flag etc. as well.
Can someone provide a solution in python for problem B without using import sys, I am getting Time Limit Exceeded error
It is an observation problem. First print sum of i ** i for low range. Then notice the odd-even pattern.
Thanks Bruda
I used same logic in C but still got WA. Can anyone tell my why? Thank you in advance. I did 2 different code but same logic. Still can't understand why it wasn't accepted.
282360605 282336672
Both
a[lastman]
andn
areint
s, soa[lastman]*2*n
can overflow when these are large.Sorry if this is a dumb question, but
ans
is long long. So it shouldn't be a problem?It doesn't matter whether you're assigning the result to a
long long
. You should note that every operation is done with types, anda[lastman]*2*n
is a series of operations that is done only withint
types. The overflow occurs right here, and assining is done after this overflow already happened. Once the overflow happens, there is no way to fix it back — its value is already broken (to be precise, it is already an undefined behavior.)Thanks man. It's solved now. AC
E can also be solved with a different approach Also. My idea is related to binary search the answer
Comment link of Solution : https://mirror.codeforces.com/blog/entry/134087?#comment-1200754
how is editorial even published 4 days ago?!
The blog was private and made public after contest.
OMG round developer's first reply on my comment... happy to see... BTW Can D be solved with the same kind of logic for CSES Movie Festival ?!
Why my solution is getting WA in problem H
Submission: https://mirror.codeforces.com/contest/2014/submission/282384796
The array a has 1e6 + 5 elements, combined with T testcases, that yields a solution with a T * (1e6 + 5) time complexity for that alone, which in itself can exceed 1e10
Yea, just figured it out from a while.
Thanks for help
I'm not sure if this was luck or actually correct
can someone try hacking this code for B
(Edit: having collision doesn't directly lead the solution to fail with high chance, see below comment for details.) For using hash for problem H, one need to use at least 64-bit hash or dual-hash.
Recall the probability for hash collision is $$$1-exp\left(-\frac{n(n-1)}{2d}\right)$$$, where $$$n$$$ is the number of elements and $$$d$$$ is the hash space.
if $$$n=1e6, d=2^{32}$$$, $$$1-exp\left(-\frac{n(n-1)}{2d}\right)\approx 1$$$ and it can be hacked
if $$$n=1e6, d=2^{64}$$$, $$$1-exp\left(-\frac{n(n-1)}{2d}\right)\approx 2.71e-08$$$
Oh no, I woke up after sleeping and found out that my H had been hacked. I just realized that mt19937 only generates integers within int, so mt19937_64 should be used. But I'm still very curious about how you hacked me, constantly submitting random data?
I didn't hack in this round. I originally thought the hacks use collisions, when I read some of the hack generators (and found them interesting!) I realized they are generating adversarial test targeting any deterministic hash functions. Yes
time(0)
as seed is deterministic in the context because one can generate hundreds of tests and the hack will be valid for a few minutes. Should use something less predictable likechrono::system_clock::now().time_since_epoch().count()
(nanosecond)While this estimate is safer in general, you should notice that the solution for H this times only made n comparisons of hashes. Making it (1-2^32)^n, which is not that bad. This would fail with probability of about 0.00005. If were to go against 100 max tests, then there is a non-negligible chance that it fails, (0.5% roughly), but hardly a common thing.
If the error estimate is indeed as bad as you claim, that it should have gotten a wrong answer on literally any random test.
the problem F can be solved by greedy??
Explain?
Can you go through my code. It's little difficult to explain here https://mirror.codeforces.com/contest/2014/submission/282406059
thats WA? I thought you meant you had a greedy sution for F..
Solved H just after the contest ended. QwQ
can resolve test case limitations!
In F, if instead of taking coins from only the neighbours we take coins from all the nodes, then how would we solve the problem?
then xringe ah unworthy prblem, onli save till negative
skibidi kinda fellow...
ig pulling from all breaks down the tree structure and we can just iterate from the back of the sorted array and take elements based on that. This function is also monotonic but that unnecessary.
What I meant that if the influence reaches to more than one level eg. neighbours at a distance <= k will also be reduced by c, then how to solve.
just use dp of size n*k, pls dont waste others' time here asking these simple questions. Thanks.
code pls can't do dp not strong
ngl i dont know why i do a O(10^6) G lol
Can anyone figure out what's wrong with my approach?
Submission: 282417933
your handling of withhorse and found separately seems inappropriate. As if a horse is found once and we decide to sit on it, then we will be sitting on it for the rest of the journey itself.
Guys, can someone tell me why does my submission for D(282372366) get TL?
E was a nice problem. Loved the modified Dijkstra algorithm!
Actually its called Dijkstra state space formulation i guess it is a standard technique for graphs
Blog about State space formulation
For B ,why (n-k+1)+n)*k/2 can't accept,WA in test3;(n-k+1)+n)*k//2 is right,I don't know!Who can help me?
due to float handling, as during calculation of [(n-k+1)+n]*k ; and then dividing it by 2 can lead to a deviation from the actual answer (always an integer btw), and this very small deviation, will return a false when checked for divisibility with 2 without first converting it to a proper integer which it should be(as this small error will also be taken into account).
Nice Contest ! , RobinFromTheHood Orz .
Though this is my feedback :
Perfect D3A , Implementation and enough.
Simulation , each time accumulate $$$\text{sum}$$$ and for each $$$a_i=0$$$ check if $$$\text{sum}>0$$$ increase $$$\text{cnt}$$$ by $$$1$$$ ; finally print $$$\text{cnt}$$$.
Complexity is $$$\mathcal{O}(n)$$$.
B. Nice D3B but harder than D3B imo , Overflow issues (I'd to use python to AC)
Let $$$f(x)$$$ be the sum of first $$$n$$$ squares which is
, or numbers (which works) i.e. $$$f(n)=\frac{n(n+1)}{2}$$$ from this we check if $$$f(n)-f(n-k)$$$ is even then $$$\mathtt{YES}$$$ otherwise $$$\mathtt{NO}$$$.
Complexity is $$$\mathcal{O}(1)$$$.
Nice Problem ! , Really enjoyed it .
to minimize the number of gold , we want to select the first $$$\lceil \frac{n}{2} \rceil$$$ minimum numbers , It's easy to show that $$$n=1,2$$$ are always $$$-1$$$.
since the average is measured as
it's enough add $$$a_{\lfloor \frac{n}{2} \rfloor}$$$ to the sum (in numerator) , this should be translated in form of numerator , thus must have at least $$$a_{\lfloor \frac{n}{2} \rfloor}+1$$$ to make this happen , and there's already $$$\sum a$$$ thus the answer is
and we've to check
Problem B can simply be reduced to counting the amount of odd numbers in [n-k+1,n], if it is odd, its NO, otherwise, its yes
Yeah , I over-complicated it ]:
Can anybody help me, this is giving TLE for E problem
Because the total time complexity is $$$O(n\ log^2\ n)$$$
i tried changing the set to unordered set still didnt work there shdnt be any collisions for 1e5 right ?
I'm not sure, haven't used unordered set before.
I have commented out your code.
changes :
1. used vector horses instead of set horses
2. used vector<array<ll,2>> visited instead of set<pair<int,int>> visited;
3. changed the position where you were checking visited node. Your code was pushing the same node more than once.
optional : you may use priority_queue<array<ll,3>, vector<array<ll,3>>, greater<array<ll,3>>> pq; to reduce overhead. I will improve the code performance.
https://mirror.codeforces.com/contest/2014/submission/282262350
This man managed to add comments and neatly format his code while solving the problem in 4 minutes. truly impressive
All of this while averaging ~10k rank in previous contests. Truly marvelous.
What an inhuman performance
A : ~3 min B : ~6 minutes, C & D & E: ~4 minutes (A-E in ~21 minutes) crazy
Can someone tell me what is wrong with this code and which testcase it will fail. Thanks!!
You need to think again for the logic. Robing goes from 1 to N in order, we are not allowed to rearrage the array. Robin can only help if he has amount > 0.
suppose this case — 1 2 3 0 0 0 0 0 0 0 where n=10 and k=4 in this- result(0, 7) -> result = 0 . Are you talking about this case where robin had zero gold??
this case — 0 0 0 0 0 0 0 5 5 5 where n=10 and k=4
you code will output 7 but answer is 0
WTF is this code, can someone tell me — 282251367 edit — MikeMirzayanov
This is called obfuscation and it is forbidden by rules.
Should we report the user or What ?? He had use this to gain +497 rating.. in last contest
Yes, this one should be reported as contest rules violator.
I think they did it to avoid plag but anyways hiding solutions is not allowed
rules
"It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work."
MikeMirzayanov RobinFromTheHood
Just found out, c++ version can affect the hashing solution. I am used to c++17, but the editorial solution actually fails for c++17, submission: https://mirror.codeforces.com/contest/2014/submission/282483545.
you should use chrono::steady_clock::now().time_since_epoch().count() as seed instead, as it is unpredictable
A notable implementation where std::random_device is deterministic in old versions of MinGW-w64 (bug 338, fixed since GCC 9.2) [1] 7.3 which the submission used is already old. BTW, the link is broken, I need to copy-paste to visit it.
[1] https://en.cppreference.com/w/cpp/numeric/random/random_device
Problem E was really good! I never thought Dijkstra's algorithm could be used in this way.
Actually its called Dijkstra state space formulation
Blog about State space formulation
is it possible to solve D with lazy segtree? I overkilled it straight for 20 mins but I couldn't solve it during contest. If someone knows please tell
Technically the range sum updates in D (as said in editorial) can be mimicked by lazy segtree; i.e. they do the exact work. Though I don't know why you would rely on segtree as your first option...
with range sum updates, how will we identify the distinct overlaps? I wanna know how to solve it with lazy segtree for educational purposes
Edit: I'm not talking about editorial solution in particular. Just if there's one
I think I said bogus just now... now I can't think of any way to explain without clunking up the solution.
Like, what I have in mind is a simple solution, doable in segtree but it just adds unnecessary extra steps.
Thinking again, when writing a slightly related comment just below, I realize you can do segtree if you want to store the numbers of jobs for each range.
Now, index $$$i$$$ in segtree will correlate to range ending at day $$$i$$$. Loop $$$i$$$ in range $$$[d, n]$$$ again:
Of course, the last part means you'd just query a single index for all index in range $$$[1, n]$$$ just to get the min and max you wanted. Pretty tedious there...
IN Problem D
What will be the approach if 1<= l,r <=10^9?
Very hacky solution for D without prefix sum:
Count the number of jobs with the same start dates and end dates, separately. We'll call $$$s_i$$$ as the number of jobs start at date $$$i$$$, and $$$e_i$$$ as the number of jobs ends at date $$$i$$$.
Set a temporal value $$$v = 0$$$, now loop all end dates $$$1 \le i \le n$$$:
Submission: 282518960
I think this can extend to solve D with arbitrarily large $$$n$$$ with compression and a bit of extra tricks, but I'm not too certain.
For problem H, why isn't XORing from l -> r and checking non-zero a sufficient condition? I'm getting WA on test 3...
One easy countertest: a range with elements $$$[1, 2, 3]$$$. You'll see the xor sum being $$$0$$$ but it isn't completely made of pairs of numbers.
Can anyone please help to find why is my solution for problem-C giving integer overflow?
solution
I have used ll as long long and it is giving overflow for val, which will at max be n*2*(max(a[i])) = 2*(2e5)*1e6 = 4e11 which should not give overflow for long long, like I get that there is no need for this long binary search but still I could not find why it is giving overflow
Thanks in advance
Your m can be pretty large (1e18 / 2) and you add it to some array element and then multiply by n causing overflow.
Thanks, I totally missed it
I really like problem E!
I practiced a 2D dijkstra before so I am glad I can catch the idea really quick.
my submissionwhy am I getting tle in problem c ? pls help.
This is my code for Problem H
Why my code is getting WA on test 3 282785052 .
I was trying H, but getting WA on 75th TC. When I changed compiler to G++ 23 (from 17), it got AC. Does this happen usually in in these qns? I also tested locally but locally (with g++ 13), i was getting the right ans. Following submisison got AC by changing compiler, guidance appreciated on what to do in a contest setting. 282807018
can anyone tell why am i getting a tle in problem E 282462349
Hello everybody, i try to solve E so hard, but i get WA and don't understand why. May be some chads can help me?
282818149
P.S. Sorry for this large and bad code. I am ready for criticism and advice!
Yo, as we have two states in the graph, our previous nodes which were once only 1, 2, 3, .., n
But now we have 2d Nodes, {i, 0} or {i, 1}
You haven't used the priority queue correctly Just think in 1d codes you have had priority queue as {dist, node} right So in 2d it should be a tuple as {dist, {node, 0 or 1}}
Also remember this is actually like dynamic programming itself its just that in DP the state space graph is a DAG (acyclic) so we have to let the transition decide the {node, 0 or 1} in your code you have yourself initialized and transitions are also a bit incorrect
General Tip this is State space modelling question so you need to think in DP manner to solve it efficiently
For a good idea on State space modelling look into this Blog about Dijkstra and State Space Modeling
Here is My approach — use state space formulation
total Time Complexity = O( N LOG(N) ) multiplied by 2 as i am using dijkstra a 2 times;
(node, 0) represents we don't have a horse (node, 1) we have the horse
if( node has a horse in it and you are in the state node, 0 ) go to state (node, 1) with 0 cost as mentioned in the question
if we are at (node, 1) then we can only go to (child, 1) with cost edgeWeight / 2
if we are at (node, 0) then we can only go to (child, 0) with cost edgeWeight
run this dijkstra from node number 1 and node number n for all nodes maximise the minimum distance from each node
then for all nodes minimise the distance and find the minimum
Submission Link quite self explanatory 283107392
in Problem E, why have we used comparator lambda function:
make_pair(distance[a.first][a.second], a) <make_pair(distance[b.first][b.second],b)
and not the distances of a and b states:d[a.first][a.second] < d[b.first][b.second];
.Is it because incase of two states having same distances, it will consider them equivalent? and if so, what difference will it make. would appreciate some help here, thanks!
I think it's because when you have two distances that are the same, for example in the input example of the problem test case 5, when maria starts doing dijkstra, she will have two options that has the same distance value; 4. this causes the set to assume that they are the same value thus not inserting it into the set when we actually want it to be inserted.
CMIIW
I have a doubt regarding problem H in this contest. My submission
// ll random_address() { char *p = new char; delete p; return uint64_t(p); } // ll splitmix64(ll x) {
// x += 0x9e3779b97f4a7c15; // x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; // x = (x ^ (x >> 27)) * 0x94d049bb133111eb; // return x ^ (x >> 31); // } // const ll FIXED_RANDOM = splitmix64(chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1)); why we have to use uint_64, i am not able to use ll as long long in the first line , when i am using ll it gives me error , why so could anyone explain please. and also explain how to write this function which randomly generate numbers because in the blog suggested by crystal it is difficult to understand so could you please explain here as i have write above code with the help of code submitted by neal , and actually i myself use some other technique to generate numbers in this solution and the code accepted and i was suprised because i used some random things, so could you please tell me some mathematics behind this that how it is working , and i also submitted two codes ,in one i was increasing x by 1e5 and in another one i was increasing by 1e8, and suprisingly the code with 1e5 accepted and with 1e8 it was giving wrong answer on test 5 . both code links are With x+=1e5 and with x+=1e8. and I have one more doubt when i was using M = 1e9+7 the code with x+=1e5 accepted and in same code i was using M = 999999937 in the code it is giving WA on test 5. So it is humble request to crystaI and RobinFromTheHood and other cf community coders to clear my doubt.
please help me to understand this
jb koi bta nhi rha tujhe to yaha pe chutiya doubt kyo puch rha he bsdk
Mindeveloped and AkiLotus, please help to clear this doubt
what???
I have a doubt regarding problem H in this contest. My submission
// ll random_address() { char *p = new char; delete p; return uint64_t(p); } // ll splitmix64(ll x) {
// x += 0x9e3779b97f4a7c15; // x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; // x = (x ^ (x >> 27)) * 0x94d049bb133111eb; // return x ^ (x >> 31); // } // const ll FIXED_RANDOM = splitmix64(chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1)); why we have to use uint_64, i am not able to use ll as long long in the first line , when i am using ll it gives me error , why so could anyone explain please. and also explain how to write this function which randomly generate numbers because in the blog suggested by crystal it is difficult to understand so could you please explain here as i have write above code with the help of code submitted by neal , and actually i myself use some other technique to generate numbers in this solution and the code accepted and i was suprised because i used some random things, so could you please tell me some mathematics behind this that how it is working , and i also submitted two codes ,in one i was increasing x by 1e5 and in another one i was increasing by 1e8, and suprisingly the code with 1e5 accepted and with 1e8 it was giving wrong answer on test 5 . both code links are With x+=1e5 and with x+=1e8. and I have one more doubt when i was using M = 1e9+7 the code with x+=1e5 accepted and in same code i was using M = 999999937 in the code it is giving WA on test 5.
i have asked in above mentioned comment
I mean to crystaI mistakenly same user name of both ids
Why is this giving TLE I have used Dijkstra Algo total states are 2 * N and number of edges are also of order N i.e M <= N
My approach use state space formulation
The approach seems correct as it is not giving WA, but fails to pass the time limit
here is the submission link Getting TLE on Test case 9 282838495
Inefficient Dijkstra implementation — a same node tuple can exist in the PQ multiple times, and you need to skip the later ones instead of rerunning them as it could bloat the whole process into Bellman-Ford all over again.
Damn lol I forgot to use the vis array which declared globally but i didn't use it in the dijkstra implementation
Problem H , Did anyone solve this with Divide and Conquer?
hey, could you please help me to clear my doubt i mentioned above
I loved problem F
In D , Can someone explain the 5th test case, the job is from 2 to 8, so why my answer can't be 2(brother) and 1(mother) ?
In problem C, we can avoid sorting the input by using the
nth_element
function, thus giving a time complexity of $$$O(n)$$$.would appreciate if u could just go through this post and address my querry related to problem E(https://mirror.codeforces.com/blog/entry/134511) .
what is wrong in my code it is giving TLE on test 2 solution E
Thanks ! I've harvest a lot from problem F.
We should drink the latest milk ~