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!gonna hate myself for the rest of my life for messing up C.... i was sooooo closeeee
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.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 :)
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 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
Can someone provide a solution in python for problem B without using import sys, I am getting Time Limit Exceeded error
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://codeforces.net/blog/entry/134087?#comment-1200754
how is editorial even published 4 days ago?!
The blog was private and made public after contest.
Why my solution is getting WA in problem H
Submission: https://codeforces.net/contest/2014/submission/282384796
I'm not sure if this was luck or actually correct
can someone try hacking this code for B
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$$$