We hope you enjoyed the contest!
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200'007;
const int MOD = 1'000'000'007;
void solve() {
int a, b, c;
cin >> a >> b >> c;
cout << (a ^ b ^ c) << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
1915B - Not Quite Latin Square
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200'007;
const int MOD = 1'000'000'007;
void solve() {
int cnt[3] = {};
for (int i = 0; i < 9; i++) {
char c;
cin >> c;
if (c != '?') {cnt[c - 'A']++;}
}
for (int i = 0; i < 3; i++) {
if (cnt[i] < 3) {cout << (char)('A' + i) << '\n';}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: SlavicG
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
bool is_square(ll x) {
ll l = 1, r = 1e9;
while(l <= r) {
ll mid = l + (r - l) / 2;
if(mid * mid == x) return true;
if(mid * mid > x) r = mid - 1;
else l = mid + 1;
}
return false;
}
void solve() {
ll n; cin >> n;
ll s = 0;
for(int i = 0, x; i < n; ++i) {
cin >> x; s += x;
}
if(is_square(s)) cout << "YES\n";
else cout << "NO\n";
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}
1915D - Unnatural Language Processing
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200'007;
const int MOD = 1'000'000'007;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
string res = "";
while (!s.empty()) {
int x;
if (s.back() == 'a' || s.back() == 'e') {x = 2;}
else {x = 3;}
while (x--) {
res += s.back();
s.pop_back();
}
res += '.';
}
res.pop_back();
reverse(res.begin(), res.end());
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
void solve() {
int n; cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i) cin >> a[i];
map<ll, ll> m;
ll s = 0;
m[0] = 1;
for(int i = 0; i < n; ++i) {
a[i] *= ((i % 2) ? -1 : 1);
s += a[i];
if(m[s]) {
cout << "YES\n";
return;
}
++m[s];
}
cout << "NO\n";
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set;
int t, n;
vector<pair<int, int>> arr;
long long ans;
ordered_set st;
void solve(){
cin >> n;
arr.assign(n, {});
for(auto &p : arr) cin >> p.second >> p.first;
sort(arr.begin(), arr.end());
ans = 0;
st.clear();
for(auto p : arr){
ans += st.size() - st.order_of_key(p.second);
st.insert(p.second);
}
cout << ans << "\n";
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> t;
while(t--){
solve();
}
}
Idea: SlavicG
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
const int64_t inf = 1e18;
void solve() {
int n, m; std::cin >> n >> m;
std::vector<std::pair<int, int>> adj[n];
for(int i = 0; i < m; ++i) {
int u, v, w; std::cin >> u >> v >> w; --u, --v;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
std::vector<int> s(n);
for(int& i: s) std::cin >> i;
std::vector<std::vector<int64_t>> dist(n, std::vector<int64_t>(1001, inf));
std::vector<std::vector<bool>> vis(n, std::vector<bool>(1001, false));
dist[0][s[0]] = 0;
std::priority_queue<std::array<int64_t, 3>> q;
q.push({0, 0, s[0]});
while(!q.empty()) {
int u = q.top()[1], k = q.top()[2];
q.pop();
if(vis[u][k] || dist[u][k] == inf) continue;
vis[u][k] = true;
for(auto x: adj[u]) {
int v = x.first, w = x.second;
int c = std::min(s[v], k);
if(dist[v][c] > dist[u][k] + 1LL * w * k) {
dist[v][c] = dist[u][k] + 1LL * w * k;
q.push({-dist[v][c], v, c});
}
}
}
int64_t ans = inf;
for(int k = 1; k <= 1000; ++k)
ans = std::min(ans, dist[n - 1][k]);
std::cout << ans << "\n";
}
int main() {
std::ios_base::sync_with_stdio(0);std::cin.tie(0);
int t = 1; std::cin >> t;
while(t--) {
solve();
}
}
This was a standard div 4, I believe previous div 4s were harder than this. Good contest regardless!
For anyone who wants to know more about similar problems like G.
Here is a great blog on shortest path modelling:
https://mirror.codeforces.com/blog/entry/45897
Never thought there is something like that. Thank you !!!
why does this give TLE in E?anyone
I am not sure but in python checking
if f in d:takes enough time to make it TLE, I have encountered this while doing a problem in CSES. Everything else looks fine to me.d is a set, its O(1) to my knowledge
Yeah, actually I also used to assume its O(1) always but I guess a while ago I found out through someone's issue in a CSES problem that it is O(n) in worst case. As sets are implemented trough hash tables in python. So you can expect to lookup/insert/delete in O(1) average. Unless your hash table's load factor is too high, then you face collisions and O(n). You can find further information here.
Lookup and insertion of set can be O(n) if it's filled with values that cause hash collisions. Apparently it's possible to craft a very bad input that makes Python's (or Pypy's) set run very slowly.
int the third question if i put r = sum(the sum of all number) instead of 1e9 then it fails in testcase 3. why is that happening?
The maximum of sum is 2E14, and 4E28 after squared it.
i can't understand? does it mean it cause overflow error?
long long maximum is about 9E18
I kept my promise, I can die with a clear conscience.
Can someone please tell where i am going wrong in this solution wirtten by me for G. 239395920
Can someone tell why is this approach is wrong
Also you are marking nodes as visited and not clearing it when the value is in your hashtable blocking that path until the next test case.
Understood the test case
Can you also give a better explanation why is it failing and why if we do like this it fails for this question
DFS is awkward for shortest paths. In the test case the first time you visit node 3 you've already visited 1 and 2. This doesn't leave any options for continuing from 3 so you cache it's value as INF. Then when you start to follow the shortest path (1->3->2->4) you reach 3 and return the cached value (which is incorrect).
You'll notice that my example test case all the bicycles have the same value making the problem into a very simple shortest path on weighted graph problem.
why my soln of F fails for this test case:
from bisect import * I=lambda:map(int,input().split()) rr=range for _ in rr(int(input())): n,=I() an=0 l=[list(I()) for _ in rr(n)] l.sort() k=[] for i in rr(n): ind=bisect(k,l[i][1]) an+=len(k)-ind k.insert(ind,l[i][1]) print(an)
test case: 1 200000 -999999999 999999999 -999999998 999999998 -999999997 999999997 -999999996 999999996 -999999995 999999995 -999999994 999999994 -999999993 999999993 -999999992 999999992 -999999991 999999991 -999999990 999999990 -999999989 999999989 -999999988 999999988 -999999987 999999987 -999999986 999999986 -999999985 999999985 -999999984 999999984 -999999983 999999983 -999999982 999999982 -999999981 999999981 -999999980 999999980 -999999979 999999979 -999999978 999999978
trying using set
but where i m using set in the code
here is my code for f using binary index tree. https://mirror.codeforces.com/contest/1915/submission/239413594
Why my E's solution got hacked for this testcase? Both the editorial's and my solution is giving "NO" as output.
My code:
I am not sure, but maybe because of unordered map? Here: https://mirror.codeforces.com/blog/entry/62393
Yes, when I used unordered_map it was giving TLE but when I used simple map it got accepted. But why?? Also unordered_map complexity is better as compared to map.
Because average TC of unordered_map is O(1) but in worst case it can be O(n) in case of collisions, test case is specifically created to have collisions, that's why read the above blog and learn from it.
Insert in unordered_map is usually O(N), so your overall complexity goes from O(N) or O(NlogN) to O(N^2). Unordered_map uses hash tables, so if you come up with tests anti-hash tables you’re gonna get hacked because of TLE
Can anyone give the reasoning, on why a normal dijkstra won't work for problem G ? We are asked to find the path that takes minimum time from node 1 to node n.
can't we just update the distance to a node based on this? d[v] > d[u] + min(k, s[u]) * w[u][v]
why are we storing d[v][s] ? why do we need 2d array to calculate shortest distance to node v using slowness s
you might go to a node just to achieve it's slowness factor and then come back from where you came.
Can anyone help in question 6. How is this standard problem
Basically we just want to count how many pair (i, j) that a[i] > a[j] and b[i] < b[j]. Because this is the necessary and sufficient condition when people i and people j meet at the same point.
e can also be solved easily by creating prefix sum array for even and odd indices we need to find even[j]-even[i]=odd[j]-odd[i] which is equivalent to even[j]-odd[j]=even[i]-odd[i] so just store the difference array of even and odd prefix sum if any value repeats answer is "yes" else "no"
Can anyone please explain why the below solution fails for problem G:
Approach: A slight modification of the Dijkstra's Algorithm. We calculate DIS [ i ] [ j ] to be the shortest path to reach from node 1 to node ' i ' with bike of slowness factor ' j ' . Update the DIS array when a new path having shorter distance is encountered with bike of same slowness factor.
Submission link 239402842
You are updating mins. But when going a -> b where mins at a was 10 and b would become 5, you are calculating time using 5 * edge weight. Note that to reach b you should use 10 * edge weight, use updated mins after that.
Edit: code here's mine with the same idea
I can't understand the sentence in the E problem, " Be careful about using hash tables, as they can be hacked.". Could anyone explain this?
Blowing up unordered_map, and how to stop getting hacked on it
Can someone show me how to solve F without ordered_set? Maybe with Fenwick tree or something else?
you can sort by leftmost point (i.e. a[i]) and then iterate from back to front. You will first need to do coordinate compression of b[i] values (for that you can use a map). After that when you are at i , all j > i satisfy a[j] > a[i] and you will query fenwick(map[b[i]]) , to get number the elements which are less than b[i].
https://mirror.codeforces.com/contest/1915/submission/239302718 this is my solution
Why this code for problem c is not working? (https://mirror.codeforces.com/contest/1915/submission/239353207)
The input was upto 10^9 thats why it wasnt working,you should have used LongLong as ModifiedCode
I have tried that earlier it wasn't working.
but i submitted the modified code and it got AC
The input of the array and initialisation fo sum variables are wrong,as
max(int16_t) <10^9so you wont be able to store it in first place.check last reply 239299477
The problem is
float k=sqrt(sum)consider sqrt(sum)=999999.9991 the value of k that will be used is 10^6 and for the same valueint j=floor(k) // == 1e6which will make them equal to each other making the YES but the answer should have been NO,so to correct it usedouble kin the same code,you will get ACTo avoid all this take a look at myCode
Can someone hack this solution for problem G? 239328319
If I get a input for which like everyone gets hacked due to TLE, i can only apply in a contest to a limited people but whosoever i put they get hacked,
Shouldn't there be system testing for all the successful hacks afterwards with those inputs on all users???
Ain't it unfair?
to my knowledge solutions do get retested after the hacking phase with the use of new hack-inspired tests
No, it doesn't atleast what i know for div 3 and 4, you can do as much hack as you can with the same generator code, but even if successful it won't be tested on ohters, me and my friend had same logic my got hacked his not.
last div3 got retested tho. maybe it will be retested a bit later?
Maybe, let's wait and watch
oh, did your solution use unordered_set or unordered_map? it might be the reason you got hacked, average comlexity of it is linear, but if there are too much collisions it can be o(n), people use this to make others solutions get tle, so try not to use it, there was a post about unordered map and etc. so read it if you have free time
upd.: here is a link https://codeforces.net/blog/entry/62393 upd.2: average complexity is constant, not linear, sorry
good contest but some solutions for g should not be accepted due to overflow
look at this one
https://mirror.codeforces.com/contest/1915/submission/239403382
curr is int and it should be long long upd: didn't know system testing hadn't been finished
Can anyone explain why me solution got AC? it has a time complexity of n^3 https://mirror.codeforces.com/contest/1915/submission/239328701
in this Submission,the verdict says wrong answer and the reason is wrong output on the testcase
ABC ?CA CAB (4th case of test 2)
However , my program works exactly well with this testcase as well .
Is there any error from codeforces side?
If you encouter a '?', you are just breaking from the loop
You are not taking the whole input for each testcase...
Don't break, keep the flag if you want, but take the complete input
Damn, my solution for the E got hacked because I was using the unordered_map :( I know how it can be fixed just so funny that I was getting caught on this again
Why does unordered_map get hacked?
You can take a look more in depth in this post https://mirror.codeforces.com/blog/entry/62393
[1st submission][2nd submission]
these are my two submissions to problem F , the only difference between these two submissions is that one has (#define int long long) and in other submission I commented that line , the one with (#define int long long ) got TLE whereas the submission without this got AC, why so and how can we avoid this TLE?
Your solution is O(N^2) due to erasing elements from vector.
Your 1st solution is lucky to barely passed the time limits.
Thanks but why that solution is getting AC everytime when using int and TLE when using long long instead of int , does using long long increase execution time of a programme?
Can we use DP in any way to find the solution for problem G?
I know we can go with some modification of dijkstra's algorithm, but was wondering if any one has done it differently.
can anyone explain how can i find number of pairs of segment such that one completely lies inside anohter , inorder to solve F
sort the input based on the starting position then for segment i all the segments j such that i < j < n and ending position of j is less than i will completely lies inside segment i
For problem F, after sorting, its actually just Kendall tau distance, which can be solved in
O(nlogn)withsegment/fenwick treesor with some divide and conquer techniques, related tomerge sortandquick sortCan someone explain to me why do I get TLE when I use unordered_set in PROBLEM G? When I changed it to set, I got AC.
link to blog. unordered map set work on hashing so it can tle if inputs are intentionally generate to cause large no of collisions it's better to use so it's better to use set and map in contest
We can solve problem F by using merge sort algorithm.
You can count the number that smaller the current number and before it in the second element of pair after sort it by nondecreasing sort.
This is the code: https://mirror.codeforces.com/contest/1915/submission/239384276
Problem-F can also be solved using Fenwick tree? If yes, then can someone please explain the solution using Fenwick tree.
i assume that you know that in problem can be simplified to counting the inversion in an array to do this you can assign each element A[i] to it's index in sorted order like A = {5, 7 3, 2, 9} sorted A = {2, 3, 5, 7, 9} now you assign each element to it's relative index like (5 => 3), (7 => 4) and so on now A becomes A = {3, 4, 2, 1, 5} notice that all the elements in A are now between 1 and n. now assume you have visited array vis and a an array B which stores the prefix sum of vis array now iterate on A in reverse order and add B[A[i]] to you'r ans. why? it's because if you see carefully B[i] stores no. of elements < A[i] that are already visited and update the vis array vis[A[i]] = 1 and recalculate the prefix sum array B. the complexity of this O(n^2) now you can do the same thing in fenwick tree using point updates so it will be O(n*long(n)). you can learn fenwick tree from here hope it helps and sorry for my bad english.
what u did is cordinate compression ?
yes
can u explain please how the problem is transformed into counting the inversion in an array ( and what is inversion in an array exactly )
as everybody is moving with same speed 1 unit / sec relative velocity between any two person is 0. ~~~~~ let 2 person be x (ax, bx), y (ay, by) greeting between x and y happen only when
case 1 :- ax < ay < by < bx
case 2 :- ay < ax < bx < by
no. of greetings will be no. of ordered pairs(x, y) satisfying one of the above condition
now to do this you sort the people based on their starting point
now person i and j (i < j) greet only when b[i] > b[j]
so you just have to calculate no. of pairs (i, j) (i < j) such that b[i] > b[j]
these pairs are called inversion and count of all such pairs called no. of inversions in array
now you can think of solving this simplified problem
hope it help's let me know if you have any other query. ~~~~~
we need an array sorted to count the
no. of pairs (i, j) (i < j) such that b[i] < b[j]?but we don t have that array that s why we used that technique ?
yes we have make an array whose i'th element denotes starting and ending points.
ok thanks bro
please dont freeze the contest need to upsolve it not able to submit code now
after system testing it will be open for practice
Problem C, why sqrt doesn't get TLE?
sqrt is logn
IN problem E. Romantic Glasses TEST case 6: 2 5 10 4 4 9 6 7 8
why answer "YES"
there is no possiblity of equal subarray from (l,r)???????????????????
subarray [4, 4]
Did u mean [4,5]?
ah, yes
In problem E, can someone explain why using a hashtable leads to a TLE/hack?
has anyone solved F without using segement or fenwick tree in python? using bisect insort to keep a sorted list gives TLE on 11
bisect.insort is O(n), because inserting a value into the middle of a list is O(n).
Yeah use merge sort for inversion coutning
what s is inversion counting bro
Need help with C. Took inputs as long long, added them. Take l=0, r=total, k=0. While(l<=r){ m = l+(r-l)/2; if(m*m <= total) k=m, l=m+1; else r=m-1; } At the end if(k*k != total) print No else print Yes
I am getting Wrong Answer at case 3. Please, point out what I did wrong. Submission
I think the upperbound of your binary search is too big. you should change the upperbound to somewhere at
2e7(or sqrt root of 2e14)Why did my F TLE？ https://mirror.codeforces.com/contest/1915/submission/239528521
Insertion for vector is O(N) on average.
Your solution's time complexity is O(N^2) imo.
A-G solutions https://therealchainman.blogspot.com/2023/12/codeforces-round-918-div-4-problem-use.html
Can someone please look at the following code snippet (for problem 1915-F), and tell me why it gives TLE on test case #3: (And please bear with my excessive usage of macros, i hope you understand what the code is doing.)
maybe give full code, impossible to understand anything when everything is #defined
Your solution has worst case $$$O(N^2)$$$ because you use std::distance which is linear for containers that aren't random access. As the example solution in this editorial shows, you can instead use an order statistic tree to solve this problem without TLE.
First of all thanks for the nice problemsetting. SlavicG, mesanu, flamestorm
I have a slightly different solution for problem G, here is how it goes:
In this problem, we have to choose a sequence like this: 1, $$$i_1$$$, $$$i_2$$$, ..., $$$i_k$$$, $$$n$$$.
$$$i_x$$$ means the nodes we have selected as a step, note that the consecutive elements should not necessarily be neighbors, it is enough to go from one to another using some nodes.
We should travel from node $$$1$$$ to node $$$i_1$$$ with the bicycle in node $$$1$$$, after that we should go from node $$$i_1$$$ to node $$$i_2$$$ with the bicycle in node $$$i_1$$$ and so on. Finally, we should go from node $$$i_k$$$ to node $$$n$$$ with the bicycle in $$$i_k.$$$ node. Then we should observe that the slowness factor of the bicycles $$$1$$$, $$$i_1$$$,..., $$$i_k$$$ should be decreasing sequence because we are multiplying the distance with slowness factor so going to a node with a higher slowness factor is an unnecessary step.
After this observation, we can sort the array in descending order by their slowness factors and make dynamic programming. We can either choose a node as a step (i.e. $$$i_x$$$) or not choose the node. We must also remember the last step we have made and find the value by multiplying the slowness factor of the last node we have taken and the distance between our current selected node and the last selected node.
We can precalculate the distance between each node by starting the Dijkstra algorithm from each node.
Here is my solution code: https://mirror.codeforces.com/contest/1915/submission/239421899
In the tutorial of F, the explanation says "for each of them add the number of segments that we have already passed that have an a value larger than the one of the current segment." Shouldn't it be smaller instead of larger as we have B sorted in increasing order ? Edit: I got it
In Problem E can anybody tell why solution gives TLE when I use unordered map and gets accepted when I use map
void solution(){ ll n; cin>>n; vector a(n); unordered_map<ll,ll> mpe; ll sume = 0,sumo = 0; for(auto &it:a) cin>>it; for(ll i = 0; i < n; i++){ if(i % 2 == 0){ sume += a[i]; }else{ sumo += a[i]; }
}
int main(){ ll t; cin>>t; while(t--)solution(); return 0; }
Bad hashing in unordered map can lead to collisions which increases the complexity of map's functions from $$$O(1) - \gt O(N)$$$ hence the TLE.
Find more here:
https://mirror.codeforces.com/blog/entry/62393
A more efficient (and prolly simpler) code for G as it does not require a 2D array: https://mirror.codeforces.com/contest/1915/submission/239576580
It's just Dijkstra with time as the parameter, but when I push cities into the priority queue, I also store the minimum slowness with which I will leave the city, once I visit it (the minimum between the slowness with which I entered the city and the slowness of that city's bike). Instead of a "visited" array, I made an array which stores the minimum slowness with which I have left the city, if I have visited it. So when I visit a city again, I carry on with that iteration only if the slowness with which I am entering the city is strictly lesser than the minimum slowness with which I have exited the city before, otherwise I continue with the next iteration.
Can someoone teach me G in a little more detail I don't know much about creating a new graph with state data.
My G did not withstand system test.
https://mirror.codeforces.com/contest/1915/submission/239379244
Subtle bug in Djikstra implementation, try to find it if you like. (Note: I know what it is and I think it was a great way to learn something through the contest, won't make the same mistake again now.)
why is unordered_map not working but normal map working?
https://mirror.codeforces.com/blog/entry/62393
Can anyone help me to find what's wrong with my solution please? (My code for 1915E — Romantic Glasses). It's getting wrong answer on test case 3. My code is in JAVA. I've tried my best but can't find anything :(
In your last for loop, compare in the following way because on comparing def.get(i)==def.get(i-1), it is comparing the references not the value.
Can someone explain why Dijkstra in G problem is not getting TLE verdict? We have n^2 vertices, for each vertex we traverse m edges, which should be at least O(n^2 * m) yet author's solution's passing with no probs. Where my logic gone wrong? Or I guess don't understand Dijkstra at all LOL
Dijsktra's time complexity, when using priority queue is O(E + VlogV), you can refer to the : proof here
This is a good question, and flamestorm or SlavicG should've presented a more elaborate complexity analysis in the editorial.
We have $$$V = 1000n$$$ vertices, but we do not traverse all $$$m$$$ edges for each vertex. Instead, each edge $$$(u, v, w)$$$ is traversed at most $$$2000$$$ times: once from each of the vertices $$$(u, 1), (u, 2), \ldots, (u, 1000)$$$ and $$$(v, 1), (v, 2), \ldots, (v, 1000)$$$. Hence, the total number of edges is $$$E \le 2000m$$$.
The time complexity of Dijkstra's algorithm as implemented in the editorial is $$$O((E + V) \log V)$$$, which for $$$n = m = 1000$$$ has an upper bound of roughly $$$60 \cdot 10^6$$$.
Wow, that was insightful, thanks!
In tutorial of 1915E what does the author mean by hash map can be hacked?
Check this
In problem F how can we actually solve it without using order_of_key, with some implementations I did try to use lower bound it is still TLE. Here is my code https://mirror.codeforces.com/contest/1915/submission/261686634
Without using order_of_key
I solved this way , it might be helpful
https://mirror.codeforces.com/contest/1915/submission/239333098
Though with the help of order_of_key it is better to understand and easy to implement
My approach for problem E was to create a presum[] which stores the value of both till that index then I can find the is any difference has appeared before then ans is yes else no but I dont know why it is wrong . please help me to find the flaw in my logic .
include<bits/stdc++.h>
using namespace std ; void solve(){ int n ; cin>>n; vector nums(n); map<int,int> mpp; mpp[0] = 1; vector pre(n); cin>>nums[0]; if(n == 1){ cout<<"NO\n"; return ; } cin>>nums[1]; pre[0] = nums[0] ; pre[1] = nums[1]; bool flag = false; mpp[nums[1]-nums[0]] = 1; mpp[-1*nums[0]] = 1; if(nums[0] == nums[1]){ flag = true; } for(int i = 2;i<n;i++){ cin>>nums[i] ; pre[i] = nums[i] + pre[i-2]; if(mpp.find(pre[i]-pre[i-1]) != mpp.end()){ flag = true; } mpp[pre[i]-pre[i-1]] = 1; } // for(int i=0;i<n;i++) cout<<pre[i]<<" "; //cout<<"\n"; if(flag) cout<<"YES\n"; else cout<<"NO\n"; } int main(){ int tt; cin>>tt; while(tt--) solve(); }` ~~~~~ Your code here... ~~~~~
`
The tutorial has the solution, but where can we find the proof of correctness, why can't the solution TLE, meaning why don't we need to compute for all the times a node is reached with all the bikes, so it would be
Times (can be from minimum 0 to maxTime, with slowest bike from 0 to n) * Nodes* bicycles (slowness factors), like how can we prove we are not eventually calculating all states, and pruning works correctly because we pick fastest bike,
I am just asking how to prove the solution to G problem, apart form intuition, is there any mathematical way possible.
I am a little confused about 1915F - Greetings. Why should a segment fully contain another one?
Lets consider this case
Both the first person and the second one will be at index 5 in the 3rd second, so the answer must be 1. But the given solution says 0. Can someone explain if I'm understanding it the wrong way?
in the problem it is given as (a < b). 2nd interval is wrong
can someone tell me more about ordered_set st; specifically about this ~~~~~
include <ext/pb_ds/assoc_container.hpp>
include <ext/pb_ds/tree_policy.hpp>
typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set; ~~~~~
https://mirror.codeforces.com/blog/entry/11080, https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/
For F. Greetings , This is the solution without using the policy based data structure and also manual coordinate compression using map.
This uses inversion Counting.
371322868 -> Fenwick tree
371326004 -> Segment tree