### _HossamYehia_'s blog

By _HossamYehia_, 2 months ago,

Hello, Codeforces!

I am glad to invite everyone to participate in Codeforces Round #837 (Div. 2) , which will be held on Dec/11/2022 18:35 (Moscow time)

Please note the unusual time!

The round will be rated for participants of Division 2 with a rating lower than 2100. Division 1 participants can participate unofficially in the round.

You will be given 6 problems and 2 hours to solve them. This round was prepared by me and 4qqqq.

I'd especially like to thank:

This is my first official round on Codeforces. We are sincerely looking forward to your participation. We hope everyone will enjoy it.

The score distribution : 500 — 1000 — 1750 — 2250 — 2750 — 3500

We wish you good luck and high rating!

UPD1: We know about problem with C task. Now we are trying to fix it.

• -547

 » 2 months ago, # |   +7 waiting for the round.
•  » » 2 months ago, # ^ |   +12
 » 2 months ago, # | ← Rev. 2 →   +24 Egyptian Russian alliance. Hope it's gonna be a great round!But where is "As a tester,...." comments XD
•  » » 2 months ago, # ^ |   0 As a participant, I wish all positive delta and that there is NO XOR problems..
•  » » » 2 months ago, # ^ |   +24 there is NO XOR problemsSo you want XNOR problems?
•  » » » » 2 months ago, # ^ |   +22 xD NO. I meant that usually Egyptian rounds imply incoming XOR missiles.
•  » » 2 months ago, # ^ |   +4 As a author... So, now "As a author" comment here. Wait for testers
•  » » » 2 months ago, # ^ |   +11 Finally, a 4qqqq round! Can not wait for it <3
•  » » 2 months ago, # ^ |   0 Heap_OverFlow Also as a author, You will enjoy the problems xD.
•  » » » 2 months ago, # ^ |   0 cap
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +4 I did A and B only they were kinda good. FSTed on C. I think pretests were very weak? But I rewrote it and barely pass the timelimit, also many submissions following same approach of sieving then factorizing barely pass the TL. I wonder what is the intended solution for this problem? When will the editorial be published ?
•  » » » » 2 months ago, # ^ |   0 How did you approached B can you explain here please. It would be very helpful.
 » 2 months ago, # | ← Rev. 3 →   +7 WOW .. Egyptian round . Good luck bro
•  » » 2 months ago, # ^ |   +6 Thanks AhmedYahia, Hope you will enjoy the problems.
 » 2 months ago, # |   0 As a division 5 participant, I can participate unofficially in the round.Hope you'll prepare more interesting rounds.
•  » » 2 months ago, # ^ |   +15 As a divison 2 participant,I worship Tom66.
 » 2 months ago, # |   0 Good Luck EVERYONE! (◠‿◠)
 » 2 months ago, # |   +49 CAN ANYONE RELATE ;)
•  » » 2 months ago, # ^ |   0 NO
•  » » » 2 months ago, # ^ |   +106 I mean
•  » » » » 2 months ago, # ^ |   0 lol
•  » » 2 months ago, # ^ |   0 Seriously?
•  » » 2 months ago, # ^ |   0 Yeah bro-,-.. 1. My semester finals are from 12 December
•  » » » 2 months ago, # ^ |   0 Cheers Mate.
•  » » 2 months ago, # ^ |   0 Cant relate more. The day after tomorrow is my exam and here I am.(Though couldn't solve sintgle problem)
 » 2 months ago, # | ← Rev. 4 →   +8 After a long time. Best of luck Everyone.
 » 2 months ago, # |   0 After a long long break. Missed the rounds badly.
 » 2 months ago, # |   0 It's a long time for an Egyptian round ..
 » 2 months ago, # |   +3 No interactive problems?
 » 2 months ago, # |   +3 After a long time, 7 contests in 9 days. Great!
 » 2 months ago, # |   0 finally a contest
•  » » 2 months ago, # ^ |   0 +
 » 2 months ago, # | ← Rev. 2 →   0 An Egyptian round !!(❁´◡❁) I am so excited ❤❤
 » 2 months ago, # |   0 Good luck everyone ;)
 » 2 months ago, # |   0 As an Egyptian, I hope this round isn't all about bit masks
 » 2 months ago, # |   0 After a long day...
 » 2 months ago, # |   +3 This is the most anticipated contest for me, keep up _HossamYehia_ :DDD
•  » » 2 months ago, # ^ |   0 Thanks Yossef.
 » 2 months ago, # |   0 My first Egyptian round (My lovely country), so i'll memorize this round, i hope +ve delta for me and everyone.
•  » » 2 months ago, # ^ |   0 love from Egypt
 » 2 months ago, # |   0 Egyptian Russian alliance. Hope it's gonna be a great round!
 » 2 months ago, # |   0 long time no see kiddo, _HossamYehia_
 » 2 months ago, # |   0 Egypt <3
 » 2 months ago, # |   0 Morocco famous win and now Egyptian contest... African vibes coming
 » 2 months ago, # |   0 Finally after a long time..YAY!!!
 » 2 months ago, # |   0 As Egyptian I love how we are here.
 » 2 months ago, # |   0 I am best
•  » » 2 months ago, # ^ |   0 ok
 » 2 months ago, # |   0 Can't wait for the contest. The codeforces contest creators had enough vacation :)
 » 2 months ago, # |   0 The contest will start at 23:35 in China:(
 » 2 months ago, # |   0 If I'm beginning in programmation. Should I participate or it will be too difficult for me?
•  » » 2 months ago, # ^ |   +4 It will never be difficult. You will not Learn running unless you start walking. So participate in this contest and try to solve atleast one or two problem. Best wishes.
 » 2 months ago, # |   +11 Can't wait to see wangzheng2008's performance.
 » 2 months ago, # |   0 I hope this African Round is as good as they are performing in FIFA World Cup with Morocco.
 » 2 months ago, # |   0 Hope to become pharaon this round
 » 2 months ago, # |   +13 Codepairses
 » 2 months ago, # |   -11 Why does this feel like a Div 1 round or maybe it's just tough for me.
•  » » 2 months ago, # ^ |   0 It's nothing compared to div1 rounds. You need more practice
 » 2 months ago, # |   0 E has a strong ROI 2015 in Arkhangelsk problem 6 vibe
 » 2 months ago, # |   +7 Bloody Hell. What a pairful round!
•  » » 2 months ago, # ^ |   0 Congrats man for solving 3 questions
 » 2 months ago, # |   +6 let me guess, you forced online version of F because $O(mlog^2n)$ parallel_bs + BIT is faster than $O(mlogn)$ persistent_tree? :D
•  » » 2 months ago, # ^ |   +18 I think it's also because of easy Mo's algorithm solution.
 » 2 months ago, # | ← Rev. 3 →   +20 Why only 1 second limit for problem D? Java barely passes after optimizations & 3 TLEs...
•  » » 2 months ago, # ^ |   -21 Cuz why not ?My solution had a complexity of $\mathcal{O}(n^2\log{n})$, using LCA and dp.
•  » » » 2 months ago, # ^ |   +20 Because it screws Java users... My solution is O(n^2) and it might fail on system tests.
•  » » » 2 months ago, # ^ |   -28 My n^2 solution for D runs very slowly, can you tell why #pragma GCC optimize("unroll-loops") #pragma GCC optimize("O3") #pragma GCC target("avx2") #include #include #include #define ll long long #define mod 998244353 #define mod1 998244353 #define PI 3.14159265359 using namespace std; vector>adj; vector>dp; vector>>paths; void dfs(int v,int par, int vert, int startv, int&len) { len++; if(len>2) { paths[len].push_back({startv,vert,par,v}); } for(auto it:adj[v]) { if(it==par) continue; dfs(it,v,vert,startv,len); } len--; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout<>t; int tx = t; while(t--) { int n; cin>>n; adj.clear(); paths.clear(); dp.clear(); adj.resize(n+1); dp.resize(n+1,vector(n+1)); paths.resize(n+1); string vals; cin>>vals; int i; int ans = 1; for(i=1;i<=n;i++) { dp[i][i]=1; } for(i=1;i<=n-1;i++) { int a,b; cin>>a>>b; adj[a].push_back(b); adj[b].push_back(a); if(vals[a-1]==vals[b-1]) { dp[a][b]=dp[b][a]=2; ans =2; } else { dp[a][b]=dp[b][a]=1; } } for(i=1;i<=n;i++) { for(auto it:adj[i]) { int len=1; dfs(it,i,it,i,len); } } int cnt=0; for(i=3;i<=n;i++) { for(auto &it:paths[i]) { int lef = it[0]; int ri = it[3]; int l1 = it[1]; int r1 = it[2]; if(vals[lef-1]==vals[ri-1]) { dp[lef][ri]=dp[l1][r1]+2; } dp[lef][ri]=max(dp[lef][ri],dp[lef][r1]); dp[lef][ri]=max(dp[lef][ri],dp[l1][ri]); ans = max(ans,dp[lef][ri]); } } cout<
 » 2 months ago, # |   0 How to solve B?
•  » » 2 months ago, # ^ |   0 i was thinking in the direction that ith and (i+1)th friend must not be connected in the given m queries, though kept failing 3rd pretest
•  » » » 2 months ago, # ^ |   0 bro you leave the case of all number are same in an array, eg; 1 1 1 1 1 if n=5, 6 6 6 6 if n=4 in this case the ans = n*(n-1).(becoz for every element there in (n-1) combination for 1 there is n-1 then for n it is n*(n-1)).
•  » » 2 months ago, # ^ | ← Rev. 2 →   +7 I will try my best to explain what I did, So a few observations first, The permutation is 1,2,3,4....n 1) Number of subsequences starting from 'i' are n-i+1.2) If we have a pair (1,2) that means that it includes all pairs (1,2),(1,3),(1,4)...(1,n) are included in it (because if we take any pair they will have (1,2) always). So if we have 2 inputs given as (1,2) and (1,4) so we can ignore (1,4) and take only (1,2) in consideration for calculation. 3) Now take a case like this we have only (2,3) as the pair, So when we consider subsequences starting from 1, They are: {[1],[1,2],[1,2,3],[1,2,3,4]}. Now as we have (2,3) as a pair we have to stop before 3. So we have to consider the effects of the number after 1 to get its stopping point.(once read code comments to be more clear) 4) if we only consider the pair (1,4), lets say n is 5. so the possible subsequences are 1,{1,2}, {1,2,3} == 4-1 {or b-a for a pair (a,b)} Code With comments Spoilerint n, m; cin >> n >> m; vector v(n + 1, INT_MAX); (This vector denotes that where we have to stop next, like for (1,2), i have to stop my subsequence before 2) for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; if (a > b)swap(a, b); v[a] = min(v[a], b); //Observation 2 } for (int i = n - 1; i >= 1; i--) { v[i] = min(v[i], v[i + 1]);//observation 3 } int ans = 0; for (int i = 1; i <= n; i++) { if (v[i] != INT_MAX) { v[i] = v[i] - i; } else { v[i] = n - i + 1;//observation 1 } } for (int i = 1; i <= n; i++) { ans += v[i];//finally adding contribution from each number. i.e number of possible subsequences starting from that number } cout << ans << endl;Sorry If I complicated in explaining something.
•  » » 2 months ago, # ^ |   +6 Some observations: If $[a, b]$ is a good subsegment, then all subsegments of $[a, b]$ are also good subsegments. If the non-friend list contains a pair $(a, b)$, then any good subsegment that contains $a$ will not contain $b$. If $[a + 1, b]$ is not a good subsegment, then $[a, b]$ is not a good subsegment. If $[a + 1, b]$ is a good subsegment, and $a$ is friends with all $x$ satisfying $a < x \leq b$, then $[a, b]$ is also a good subsegment. If the largest good subsegment that begins with $a$ is $[a, b]$, then there are exactly $b - a + 1$ good subsegments that begin with $a$ (all prefixes of $[a, b]$). Individually, these observations should be obvious, but this leads to the following solution: First, for each person $i$, find the earliest person after $i$ who is not friends with $i$, i.e., find the number $j$ such that $i$ is friends with everyone in the interval $(i, j)$ but $i$ is not friends with $j$. We can prepare this by simply maintaining a 1D vector nextstranger, such that when we read a non-friend pair $a, b$ with $a < b$, we set nextstranger[a] = min (next_stranger[a], b). Suppose we know that the largest good subsegment that begins with $a + 1$ is $[a + 1, b]$. If $a$ is friends with everybody in the range $(a, b)$, then the largest good subsegment that begins with $a$ is $[a, b]$ (cannot extend to $b + 1$ because there must be somebody within that that doesn't know $b + 1$). But if there is at least one person that $a$ is not friends with in the range $[a + 1, b]$, then the largest good subsegment that begins with $a$ is $[a, nextstranger[a] - 1]$, since $a$ knows everyone afterwards up until nextstranger[a]. In other words, the largest good subsegment that begins with $a$ is $[a, \min (b, nextstranger[a] - 1)]$. If we now iterate $i$ from $n$ to $1$ (descending order), we can now find the largest good subsegment that begins with $i$. The base-case is when $i = n$, where the largest good subsegment is obviously $[n, n]$. My submission: 184766262I used non to refer to nextstranger and cut to represent the person right after the longest good subsegment ends, i.e., for a given value of $i$, cut becomes the minimum of nextstranger[i] and the previous cut (i.e. the cutoff point for the largest good subsegment that begins at $i + 1$).
•  » » » 2 months ago, # ^ |   0 can you please explain the variable cut? I couldn't understand it clearly.
•  » » » » 2 months ago, # ^ |   0 When considering the largest good subsegment that begins with $a$, the variable cut represents the cutoff point, i.e., the largest good subsegment that begins with $a$ is $[a, cut - 1]$ and it has length $(cut - a)$.How do we calculate the current value of $cut$? Let $cut'$ represent the cutoff point for the largest good subsegment that begins with $a + 1$, i.e. the subsegment is $[a + 1, cut' - 1]$. Now, if $a$ knows everybody in the range $[a + 1, cut' - 1]$, then $cut = cut'$. But if not, then we should set $cut$ to be the first person in this range that $a$ does not know (which we already calculated as $non[a]$). We can cover both of these cases by simply setting $cut = \min (cut', non[a])$.
•  » » » » » 2 months ago, # ^ |   0 Understood thankyou!
•  » » 2 months ago, # ^ |   0
 » 2 months ago, # |   +19 Worst contest of my life, i hate it :( T_T
•  » » 2 months ago, # ^ |   0 me frfr.. A- easy B- meh cool C- easy, done, submitted----why does it not work!!!!! D- okay can do this, coded, submitted---- might just pass the TC,- TLE,TLE,TLE,TLE
•  » » 2 months ago, # ^ |   0 Yeah same for me, for me, I found C difficult. WA x4 and the memory limit exceeded. Quite painful since I was expecting to solve C :(
•  » » 2 months ago, # ^ |   0 I can't solve 1 problemIn first one I did 10 wrong submissions which takes all the time, then I realize one case of all same number was missingHope so To perform well enough in the next contest
•  » » 2 months ago, # ^ |   0 +1
 » 2 months ago, # |   -6 TL on problem C
 » 2 months ago, # |   -37 Really upset about problem C. I had a beautiful Python/PyPy solution but it kept timing out on pretest 3 :/ import math for _ in range(int(input())): input() a = list(map(int, input().split())) # https://cs.stackexchange.com/questions/93030/ if math.lcm(*a) == math.prod(a): print("NO") else: print("YES") 
•  » » 2 months ago, # ^ |   +3 This solution is too long, because lcm(a) and prod(a) can be ~ 10^(n * 9).
•  » » » 2 months ago, # ^ |   -22 The included link says that that calculating the LCM this way can be O(n k), with n being the amount of numbers (10**5) and k being the amount of digits (9). So it should really pass, unless the Python implementation is inefficient.
•  » » » » 2 months ago, # ^ | ← Rev. 4 →   +5 I think the problem is doing math.prod(a). I think the Python implementation of this function is inefficient because according to this forum thread, Python uses Karatsuba algorithm to multiply big numbers instead of a Fast Fourier Transform-method like Schönhage–Strassen algorithmThe link about LCM you used also assumes multiplication is $O(1)$ time, which is not true when your numbers are this big, so taking the LCM of the whole array like this may also be slow.
•  » » 2 months ago, # ^ |   +3 math.prod(a) is so huge number... power(10, 9 * 1e5)
•  » » 2 months ago, # ^ | ← Rev. 2 →   +60 It's actually possible to get AC with your formula with some constant factor (and some other) improvements.for example: 184805714
 » 2 months ago, # |   +9 How was the round? I personally found it a bit hard.
 » 2 months ago, # |   0 Is there eratosphen's sieve solution of C?
•  » » 2 months ago, # ^ |   0 find first 3400 prime numbers and rest is easy.
•  » » » 2 months ago, # ^ |   0 i did the same but it still failed on pretest 2 184795451
•  » » » » 2 months ago, # ^ |   0 silly me,
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 Yes, but it will probably FST (184750417). IdeaFind all the primes below $\sqrt{10^9}$ and factorize each $a_i$. Check if some prime occurs more than once.UPD. It passed
•  » » » 2 months ago, # ^ | ← Rev. 4 →   0 Daaamn, I did exactly the same, but got TLE, so gave up on this idea: 184746680
•  » » » » 2 months ago, # ^ |   0 It was a typo.
•  » » » » 2 months ago, # ^ |   0 Nevermind, got the most stupid mistake ever there
•  » » » 2 months ago, # ^ |   0 if (x > 1) { cnt[x]++; if (cnt[x] > 1) good = true; }What's the significance of this part of the code? How do we know for sure that this remaining part of x (if(x>1)) will be the prime number
•  » » » » 2 months ago, # ^ |   +1 actually never mind
•  » » » » 2 months ago, # ^ |   0 There can be at most one prime divisor > $\sqrt{n}$.Proof. Let's prove it by contradiction. Let $p$ be the first such divisor and $q$ be the second. Then the least number divisible by both $pq > \sqrt{n} \cdot \sqrt{n} = n$. Contradiction.So this part of code is only needed if $x$ is a big prime number.
•  » » » » » 2 months ago, # ^ |   0 Yeah I didn't considered that case initially BTW Thanks
•  » » » 2 months ago, # ^ |   0 i did same but got tle? my solution https://codeforces.com/contest/1771/submission/184811896
•  » » » » 2 months ago, # ^ |   0 I think it's because you keep all primes in map, so every incrementing of prime's count works for logn. Try to count primes under sqrt(1e9) in vector, and over sqrt(1e9) — in map, should help (Also, I would check if m[v[i]] > 1 after the prime decomposition)
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 Hey can you tell me the idea/proof as to why this approach works?It would be a great help!.[UPD : nevermind i got it, thanks.]
•  » » » 2 months ago, # ^ |   0 plz show me calculate the time limite Find all the primes below 109−−−√ and factorize each ai. Check if some prime occurs more than once. this idea
 » 2 months ago, # |   0 Why am i getting TLE. What's the time complexity of my code. Please tell. code#include set primeFactors(int n) { // Print the number of 2s that divide n setv; while (n % 2 == 0) { v.insert(2); n = n/2; } // n must be odd at this point. So we can skip // one element (Note i = i +2) for (int i = 3; i <= sqrtl(n); i = i + 2) { // While i divides n, print i and divide n while (n % i == 0) { // cout << i << " "; v.insert(i); n = n/i; } } // This condition is to handle the case when n // is a prime number greater than 2 if (n > 2) v.insert(n); return v; } void myfunc() { int n; cin >> n; int a[n]; for(int i=0; i> a[i]; // sort(a, a+n); // int cnt = 0; setalf; for(int i=0; if = primeFactors(a[i]); setnx; for(auto &j: f) { if(alf.find(j)!=alf.end()) { cyes; return; }else nx.insert(j); } for(auto &j: nx) alf.insert(j); }cno; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int t=1; cin >> t; while(t--) { myfunc(); } return 0; } 
•  » » 2 months ago, # ^ | ← Rev. 2 →   +5 If $n$ is a large prime or a product of two primes $p, q$ such that $|p-q|$ is small, your factorization algorithm degenerates into $O(\sqrt{n})$ which is unable to pass.I am so dumb that I have to nuke it with the Pollard Rho algorithm after failing 7 times, sigh~. Look my submission 184795924 when available.
•  » » » 2 months ago, # ^ |   0 I thought there are 10^8 operations at most. which can be done in 3 seconds. :/
•  » » 2 months ago, # ^ |   0 Since you iterating over the whole array (max $10^5$) and on every iteration you are finding out the prime factors of $a_i$ (max $10^9$) in square root time.Therefore the total time complexity is $O(n \sqrt{a_i})$, which in worst case would be over the allowed limits.
 » 2 months ago, # | ← Rev. 2 →   0 i don't no why,but i think B was Harder than C . :+(
 » 2 months ago, # |   +50 Tfw you nuke C with Pollard's rho algorithm and Miller-Rabin because you're too stupid to solve it normally. :cry:
•  » » 2 months ago, # ^ | ← Rev. 3 →   +5 Not sure of system tests though but the basic solution passed. pseudo codevector seivePrimes() { vector prime(35001); vector nums; for(ll i = 2; i <= 35000; i ++) { if(prime[i] == 0) { nums.push_back(i); for(ll j = i; j <= 35000; j += i) { prime[j] = 1; } } if(nums.size() >= 3410) return nums; } return nums; } void solve(vector & primes) { ll n, x; cin >> n; vector v(n); ll ans = 0; for(ll i = 0; i < n; i ++) { cin >> x; v[i] = x; } for(auto it: primes) { ll count = 0; for(auto &i: v) { ll p = 0; while (i % it == 0) { i /= it; p ++; } count += p > 0; } if(count > 1) { cout << "YES\n"; return; } } sort(v.begin(), v.end()); for(ll i = 1; i < v.size(); i ++) { if(v[i] == v[i — 1] && v[i] > 1) { cout << "YES\n"; return; } } cout << "NO\n"; } 
•  » » » 2 months ago, # ^ |   0 I don't think that'd work, what about this input: Spoiler1 2 50021 100042 
•  » » » » 2 months ago, # ^ |   -8 I also think so it should not work.But let's see system tests are on now.Also A very bad problem in a cp contest who expects one to know these heavy math number theory algorithms. It is a very bad problem
•  » » » » » 2 months ago, # ^ |   0 No, I'm wrong, it does pass on this input.
•  » » » » » » 2 months ago, # ^ |   0 Oh cool!
•  » » » » » 2 months ago, # ^ |   0 i don't think A is that bad and also this problem doesn't require "heavy math number theory" at all
•  » » » » » » 7 weeks ago, # ^ |   0 I meant C is A very bad problem :(
 » 2 months ago, # |   0 I feel in B, i'm trying to solve B in div1.
•  » » 2 months ago, # ^ |   0 It really exhausted mind I guess it will not be less than *1400
•  » » 2 months ago, # ^ |   0 I need the roadmap !!
•  » » 2 months ago, # ^ |   +4 Soooo, True This is one of the worst DIV 2
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Although this was a harder div2 B, it most certainly is not on the same level as a div1 B.
•  » » » 2 months ago, # ^ |   0 I realized that it's not hard, but i didn't take it easy "D
 » 2 months ago, # |   +70 You need to fix your contest i guess? :)https://codeforces.com/contest/1771/submission/184796886
•  » » 2 months ago, # ^ |   0 Any idea why Runtime error for such a code?I also got it for few of my submissions. Still couldn't find out why !
•  » » » 2 months ago, # ^ |   +9 assert(condition) terminates the program with exit code = 3 which results into runtime error if the condition is not true.
•  » » 2 months ago, # ^ |   +3 sample explanation in B also does not have latex
•  » » » 2 months ago, # ^ |   +13 Even worse than the incorrect constraints
 » 2 months ago, # |   +44 Problem B was stolen from 652C - Foe Pairs
•  » » 7 weeks ago, # ^ |   0 Btw I found editorial for 652C to be much more readable
 » 2 months ago, # | ← Rev. 2 →   +102 Probably the worst contest I've ever seen.Glanced at all problems and know how to solve them in one minute with no any interesting points.C: know how to factorize large numbers with pollard or things?D: very obvious and classical dp from one dimension to tree. though I dont know what's wrong with my code.E: standard dp -- crafting the largest H C F O I D .... F: also very standard online ds problem. I didnt get time to solve it bcz of D.Also A and B is very terrible. It's not beginner friendly and it introduces some tricky cases to let many newbies to fail.I can't remember the last contest with such bad quality was — I assume it should be on 2015 or before. Anyway I did not AK this contest but I got a very bad impression on the whole problemset. That's it.
•  » » 2 months ago, # ^ |   +7 I used sieve for C — worked well within the time limit.
•  » » 2 months ago, # ^ |   0 I disagree.. The contest was good. B was very good. (It required a bit more thinking unlike usual Div 2 B where you just see the problem and start coding, also no tricky edge cases were there for me least).Even though I wasn't able to solve C. I guess that's what makes the problem good. Must have missed some observation.
•  » » » 2 months ago, # ^ |   0 can you share your approach of B?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 i was not able to implement it on time but i think we had to subtract all subarrays starting from 1 to n contianing x and y from n * (n + 1) / 2, for all unique pairs and after that we have to add those subarrays which were counted more than once. it was a question of permutation and combination i guess! i hate it :(
•  » » » » » 2 months ago, # ^ |   0 when you're trying to solve an A or B problem in a div2 contest, try not to make it complicated, think it in an easier way
•  » » » » 2 months ago, # ^ |   0
•  » » » 2 months ago, # ^ |   -12 If you think problem C is good bcz it checked if people with good factorization tools or not, then you should check other problem Cs in past contest rounds.Please improve your taste before improve your rating.
•  » » » » 2 months ago, # ^ |   +1 I'm pretty sure that intended solution DOES NOT involve those weird factorization methods. (Although people overkilled it..but I don't care about "other" people). It has to be simple and elegant, and such problems are really good, whose solution is actually simple yet it doesn't strike easily.
•  » » » » » 2 months ago, # ^ |   0 YEs exactly. Don't say a problem bad by just seeing it. There is a solution which passes within 100 ms. Try to find it rather blaming that problem man. Though I personally think time limit should have been more restricted to filter out this factorization solution. This factorization solution is seems pretty straight forward for me. Just personal opinion.
•  » » » » » » 2 months ago, # ^ |   0 Yea within 100ms you mean these totally wrong submissions which got accepted due to the weak tests?Just let you know, all < 100ms submissions have been hacked. I cannot learn anything from here.
•  » » » » » 2 months ago, # ^ |   +13 The problem is if you know some fast factorization tools (like pollard-rho), you can just use it with 0 minute of thinking.So it become kind of knowledge checking problem, if you know it, you kill it instantly, and if you don't, you will need to making observation and have more penalty then the other.
•  » » » 2 months ago, # ^ |   +1 if they wanted intended to be sieve, then they should have lowered the limits, my sol just uses a extra set and doesnt pass
•  » » » 2 months ago, # ^ |   0 It was "good" because you solved it, let me guess! Segments for a B with some corner cases to think of is an utter shit for B div 2
•  » » » 2 months ago, # ^ |   +5 b was also very https://codeforces.com/contest/652/problem/C
•  » » 2 months ago, # ^ |   0 this basically sums this contest up
•  » » 2 months ago, # ^ |   +1 can't agree more... I didn't see any interesting problems in this contest
 » 2 months ago, # |   0 Not bad for today! Thanks _HossamYehia_!!
•  » » 2 months ago, # ^ |   0 What was not bad ? Round has 3 nice problems with more or less short statements — A, C, F. Everything else is shit on a stick
•  » » » 2 months ago, # ^ |   0 Could have gone worse. For me, it was my first contest
 » 2 months ago, # |   +11 How to do C? :(
 » 2 months ago, # |   +20 Contests like these always bring my little bit hope left down, i just don't know what to say.. feeling so sad right now
 » 2 months ago, # |   +7 Why this solution (184800271) for C gives WA???I am generating all prime numbers up to $\sqrt{10^9}$ because if $xy=z$ then $min(x,y)\leq{\sqrt{z}}$.Then I am looking for two multiples of every prime number generated.
•  » » 2 months ago, # ^ |   +3 It's not enough to check until 10**4.5, you do need to check until 10**9. For example, you might have 2*192763567 and 3*192763567 in the data set (192763567 being prime).
•  » » » 2 months ago, # ^ |   0 Just check and factorize every number until sqrt(n). The number remaining would be the remainding prime!
 » 2 months ago, # | ← Rev. 2 →   +12 If only F were 512MB instead of 256MB. I'm depressed... My solution using sqrt decomposition.
•  » » 2 months ago, # ^ |   0 can u explain ur sqrt decomposition logic ?
•  » » » 2 months ago, # ^ |   +3 Sory, I have just found out it's wrong.
•  » » 2 months ago, # ^ | ← Rev. 3 →   +16 I managed to write a solution using sqrt decomposition that passes, but just barely. I had to implement range paint using a vEB tree instead of DSU (which turned out to have a better constant factor than making the log log n faster than the inverse_ackermann n for this problem).Explanation of the solution: Divide the array into B blocks. Then process each block individually like this: Look at each value that occurs in the array, but not in the block. Assume the left bound of some query is inside the block, and the right bound is outside the block. Then if the answer is a value that isn't in the block, it must occur an odd number of times outside the block. And which is the smallest of these for a given right bound does not depend on the left bound, since the left bound is inside the block, and the block doesn't contain the value. So by range-"painting" values you can compute the answer for every right bound, assuming the left bound is inside the block and that the answer is not a value inside the block. Range painting can be done in O(n log log n) with good constant factor using a vEB tree.Then to answer a query, you can look only at the block corresponding to the left bound of the query. Brute force count how many occurrences there are in the range of each value that appears in the block. There are n / B values in the block, so this can be done in O(n / B * log n) time by binary searching in arrays of positions of occurrences.Then take the minimum of this answer and the pre-computed answer for the right bound in the block.Total running time is O(qn / B * log n + Bn log log n). Code: 184822603Had to steal some fast IO from nor and vEB tree from mango lassi and nor to make it pass.
 » 2 months ago, # |   +1 It was hard :D
 » 2 months ago, # |   +1 Entire contest I was searching for some efficient solution of C, at last tried brute force and it worked. Do the brute force really for C or am I gonna get FST?
•  » » 2 months ago, # ^ |   0 What brute force did you think of?
 » 2 months ago, # |   +4 Weird round. D was easier than C ;_;
•  » » 2 months ago, # ^ |   0 I came up with the solution of D, but it got the WA.
•  » » 2 months ago, # ^ |   0 Can you please explain your logic for problem -D ?
 » 2 months ago, # |   +6 It's midnight in most of Asia and I'm regretting my sleep.
 » 2 months ago, # |   +7 problem a is just same as https://codeforces.com/contest/459/problem/B but with *2
 » 2 months ago, # |   0 When approaching problem A, if the maximum and minimum values were different, i multiplied the number of maximum and the number of minimum and multiplied by 2, and if the same, i gave n * (n — 1). Why is A wrong? https://codeforces.com/contest/1771/submission/184799055
•  » » 2 months ago, # ^ |   0 Use long long
•  » » » 2 months ago, # ^ |   0 you mean when print the answer, 1LL * answer? the contest is closed now so i cant submit revised code.. I'm so upset. I want to raise my score but I don't know what to do
 » 2 months ago, # |   0 C is way too standard, but its hard to optimise your solution
•  » » 2 months ago, # ^ | ← Rev. 2 →   +3 got it
•  » » » 2 months ago, # ^ |   0 I guess because of overflow
•  » » » 2 months ago, # ^ |   0 I can assume, if you are working with C++ the set of numbers can be of arbitrarily large primes, thus the lcm can be as much of 10^40(each of the ~10^5 numbers are different ~10^9 primes). I don't know if this can work in python due to the bignumbers
 » 2 months ago, # |   0 For A if the smallest number != largest number the number of occurrence of the smallest element * the number of occurrence of the largest element * 2 ;else if all elements are same nC2 . why won't this work .
•  » » 2 months ago, # ^ |   0 for the second case nC2 will actually divide the answer by 2 but answer must be n*(n-1)
•  » » » 2 months ago, # ^ |   0 nc2 is if all elements are same . 2nd example case the elements were different right
•  » » » 2 months ago, # ^ |   0 no, it's not nc2 because you're not selecting two elements independently, you're choosing the second number on the basis of the constraints imposed by the first number, simply said, the first number's index could've been one of n, and the second number's index could be one of n-1, (all except the first number's index since they can't have the same index)
•  » » 2 months ago, # ^ |   0 If all elements are same the answer is $n(n-1)$.
•  » » » 2 months ago, # ^ |   0 same as n*(n-1) == nC2
•  » » » » 2 months ago, # ^ |   0 Wait, what does nC2 actually mean?
•  » » » » » 2 months ago, # ^ |   0 yes (* 2) for permutation . nC2 * 2 i missed this in the contest
•  » » » » 2 months ago, # ^ |   0 n*(n-1) == nP2
•  » » » » » 2 months ago, # ^ |   0 What is nP2/nC2?!
•  » » » » » » 2 months ago, # ^ |   0 permutations and combinations search for it
 » 2 months ago, # |   +22 I feel that constraints on problem C should have been either tighter or looser because solutions using Sieve and then factorizing each number using a list of primes and storing number of occurrences of each factor are barely passing and even failing for a few submissions depending on how the code has been written, which isn't fair to everyone
•  » » 2 months ago, # ^ |   0 can u share ur solution plz ? :)
•  » » » 2 months ago, # ^ |   0 I generated the list of primes up to 31622 (sqrt of 1e9), and 3401 primes are less than 31622 (I checked this after generating).After this, I created a map, facs, to store the number of times each prime factor has occurred in the prime factorisations of the elements of the array (this will require roughly 3400 operations at max to check for each prime number less than sqrt(ai)) and then if anytime, we get that a prime p divides ai and after doing facs[p]++ if facs[p]==2, then we are done and can output yes else if we have finished traversal then we can output no.You can check code here
•  » » » » 2 months ago, # ^ |   0 How do you estimate time complexity of this? I thought of same thing but I assumed no. of operations as 3*10^3 * 10^5 (correct me if I'm wrong here). I thought that's not the number of intended operations for given Time Limit forcing me to think other ways. I tried my luck by submitting some bullshit at last moment which of-course failed
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   +1 I got the same complexity, roughly 3.4*10^8 operations (you can do roughly 10^8 operations in 1 sec, so I gave it a shot), and somehow it fits in at 2.4 sec for me, which is why I feel the constraints were not fair to everyone as whether or not your code passes depends on your implementation too
•  » » » » » » 2 months ago, # ^ |   +2 It took you 2.4 sec in C++, I'm sure it won't work in Python, until they come up with solution that works with all language this is a really bad problem :(
•  » » » » 2 months ago, # ^ |   +5 damn, I just randomly checked 100*n pairs of indexes and if their gcd is 1 or not bc I thought it will give tle.
•  » » » » 2 months ago, # ^ |   0 This doesn’t pass in python
•  » » » » » 2 months ago, # ^ |   0 I think it is possible to make it pass in python ... I think this user has done it.
•  » » » » 2 months ago, # ^ |   0 but how does this pass? , we have 1e5 elements in the array , for every one of them we will go through 31622 numbers to check , which then becomes 1e5 * 31622 , this is 3162200000 ~~ 3e9 , so i don't get how this is not a tle , can u plz explain ?
•  » » » » » 2 months ago, # ^ |   +3 nvm , i get it , we have 3401 primes , it becomes 3401*1e5 ~~ 3e8 :D
 » 2 months ago, # |   +3 please tell the idea of C .. I thought sieve will simply give TLE so gave up that idea ...
 » 2 months ago, # |   0 C easy than A
•  » » 2 months ago, # ^ |   0 how did u solve it ?
 » 2 months ago, # |   0 منو لله حسام حبيب
 » 2 months ago, # | ← Rev. 2 →   0 Porblem C explain ... Basically How to find prime factors of a number<=1e9 in log(n)?? help....
•  » » 2 months ago, # ^ |   0 There are only 3401 primes smaller than sqrt(1e9) so you only need to check for those primes. Then, once you are done dividing by all the primes, if the number left is greater than 1 then it is another prime.
•  » » » 2 months ago, # ^ |   +6 so for each no in the array if I do this .. complexity can go upto 3401*n if all the numbers are a prime bigger than sqrt(1e9) . which will be 10^8 . Why wont it give TLE ?
•  » » » » 2 months ago, # ^ |   0 I feel like 10^8 operations shouldn't TLE for one second and also this problem gives 3 seconds anyway.To be fair, I know mod is slower than the other operations, so maybe one second is cutting it close but it should be fine for 3.
•  » » 2 months ago, # ^ |   0 Square root of 10^9 is 31622. There are atmost 3402 primes in 31622. There are 10^5 numbers and try to prime factorize by 3402 primes. Complexity O(n*3402) will pass.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +9 i Had this silly rule till now that 10^8 give a tle .... :(
•  » » » » 2 months ago, # ^ |   0 Same, I thought operations should be in order of 10^6 for a second time limit
•  » » » 2 months ago, # ^ |   0 Any idea why my solution gives TLE here
•  » » » 2 months ago, # ^ |   0 Will this pass in python as well?
•  » » » 2 months ago, # ^ |   +5 I saw your solution. My question is about your inner loop which at most can run 30 times. why you did not count complexity analysis. Can you give me an explanation, please? I think the complexity of your code would be O(n*3402*30). Please explain.
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   0 No. It's always up to O(n*3402). Because of, while inner loop is true, d[i] reduce by d[i]/prime[j]. If you notice carefully you will see, middle loop up to sqrt(d[i]). So reduce d[i] always reduce middle loop.
 » 2 months ago, # |   0 How to do D ꒦ິ^꒦ິ
 » 2 months ago, # |   0 https://codeforces.com/contest/1771/submission/184787882Anyone knows why is this wrong at pretest 3? Idea: Check all routes from one leaf to another. I could understand this getting TLE'd, but not WA
•  » » 5 weeks ago, # ^ |   0 Take a look at Ticket 16607 from CF Stress for a counter example.
 » 2 months ago, # |   +53 Constraints on C in fact very tough. It is easy to notice that there is $P=3500+-$ primes up to $\sqrt{10^9}$. But I think a bunch of people thought that $O(n*P)$ would get tle. moreover, we have some sets or hashtables that also affect the time complexity. Also, $O(n*P)$ theoretically should get tle
•  » » 2 months ago, # ^ | ← Rev. 2 →   +9 I thought it will get TLE, so I didn't write it. Too bad.
•  » » » 2 months ago, # ^ |   +10 Same for me, I don't recall ever seeing CF problems where the intended solution is that slow. I hope that there is a more "elegant" solution that I'm missing.
•  » » 2 months ago, # ^ |   +4 You can avoid hash table by taking a 3500 length array for storing frequency of each prime, but I agree that it was not clear that $3.5e8$ modulo operations would pass in tl.
•  » » 2 months ago, # ^ |   +8 True. I got TLE using python
 » 2 months ago, # | ← Rev. 2 →   -14 great contest thx EDIT: after VAR and discover it may be unrated contest it is second worse contest after this
 » 2 months ago, # |   0 Oh, in problem D, my solution works for $n^2\cdot26$, I thought it would pass, The asymptotics match, after all.
 » 2 months ago, # |   0 For D, I tried finding the longest palindromic subsequence for each leaf-to-leaf path. Is this approach wrong, and if so could someone please explain why :3My submission: https://codeforces.com/contest/1771/submission/184793847
•  » » 2 months ago, # ^ |   0 1 1 a this should be 1
•  » » 2 months ago, # ^ |   0 The approach shouldn't get you WA but TLE. I did the same approach and TLEed on testcase 17.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 A broom shaped tree. It can be $O(n^3)$.
 » 2 months ago, # | ← Rev. 3 →   +47 What is the intended solution to C? Is it the $O(n \cdot \pi(\sqrt{a_i}))$ solution? (where $\pi(x)$ is the number of primes less than $x$) I was hesitant to submit it for some time since ~4e8 ops in 3s felt risky. Also, I don't know if I'm just being dumb, but in E why can't we just try all horizontal parts in $O(n \cdot m^2)$ and for each check the longest possible vertical segment in O(1)?By "check the longest possible vertical segment in O(1)" I mean: Store first bad above / below each point. Store first and second medium above / below each point. Use the above two to compute how far we can extend each part (top left, bottom left, top right, bottom right). If we haven't used the medium in the horizontal segment, try it in all 4 parts (using second med above / below) and take the max of all.
•  » » 2 months ago, # ^ |   +8 about problem C. I was hesitating for about an hour, and only after giving up decided to submit 3e8 '/' operations and it did not TLE for some reason, still not sure why
•  » » » 2 months ago, # ^ |   0 C++ can do about 1e8 operations per sec. So 3e8 is done in 3 secs. And this is number theory, everything's faster than should be because a lot of cases are just skipped.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +1 Good lordI desperately tried to find a better solution and brushed off the idea that it doesn't pass because of python. Because it would be so weird to have language problems in d2C (and because I was too lazy to rewrite it today)Also it means C was a very straightforward problem with tight constraints.And now I see that there are only 10 successful submissions in pypy3-64 and most of them had to use some magical rho algorithm I have no idea about...
•  » » 2 months ago, # ^ |   0 Yeah, I did same stuff in E.
•  » » 2 months ago, # ^ |   0 For problem C, I just used Pollard-Rho, which is complexity $O(n\cdot (a_i)^{1/4})$. My submission runs in time but still takes over one second, so I wonder if there is a faster solution.
•  » » » 2 months ago, # ^ |   0 so you know that if x is not an prime number there will be a prime divisor of it <= sqrt(x) so it is max about sqrt(1e9) and the number of primes number up to sqrt(1e9) is about 3400 so you just need to fact the x by 3400 prime number
•  » » 2 months ago, # ^ |   0 I did something very similar to yours; the technique is similar to sweepline but easier: 184788266. Funny how I solved E before C. ¯_(ツ)_/¯
 » 2 months ago, # |   +1 Never felt so frustrated... Thank you! :|
 » 2 months ago, # |   +62 As a participant, C and D were complete garbage
•  » » 2 months ago, # ^ |   0 How do you do C?
•  » » » 2 months ago, # ^ |   0 I didn't solve it. I have just looked through the solutions after the contest.
•  » » 2 months ago, # ^ |   0 D was ok, C is indeed.
•  » » » 2 months ago, # ^ |   0 D seems quite standard. But, alright, I have seen worse Ds.
•  » » » » 2 months ago, # ^ |   0 idk how to solve it, i know array dp but not with tree
•  » » » » » 2 months ago, # ^ |   +8 Well, it's quite similar. You can make transitions in the order of d[v][u], where d is the distance between v and u. If you sort all the pairs by d, you can make dp transitions, which is basically dp on array, if you know the parents of the vertices on the path
 » 2 months ago, # | ← Rev. 2 →   0 Is click here solution is too slow to pass problem C ? please check this anyone's
•  » » 2 months ago, # ^ |   0 You are iterating over the vector v three times, all the reqd steps can be done in a single iteration while factorizing the number. Try doing that. Also the constraints are very tight, so avoid using functions.
 » 2 months ago, # |   0 hey can someone tell me why this gives tle:https://codeforces.com/contest/1771/submission/184791207 i know its o(n * sqrt(N))) where N = 1e9 but what is the diffrent between this and the prime factorization approach since its also suppose to be the same complexity
•  » » 2 months ago, # ^ |   0 sqrt 10^9 is 3x10^4, in total it can degrade to > 10^9
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 but people discussed above in the comments solutions that have the same complexity but it passed but maybe it fst after system test thanks anyway ps : n = 1e5, N = 1e9 just saying
•  » » » » 2 months ago, # ^ |   0 In the prime factorisation approach, you only check all primes till sqrt(1e9), which comes to be around 3e3. While you are checking all numbers till sqrt(1e9).
•  » » » » » 2 months ago, # ^ |   0 oh my bad ! didn't consider that thanks alot
 » 2 months ago, # |   +11 An unpleasant contest, a lot of newcomers fell for int in A, solutions on the verge of TL in C and D. When I was taught to do contests, they said it was not good to catch a constant or log, because there would be those who wrote a sloppy correct solution, but would not be able to pass it.
 » 2 months ago, # |   0 What is wrong with my A task submission ?
•  » » 2 months ago, # ^ |   0 int n;n*(n-1) is int, and overflows when $n=10^5$
 » 2 months ago, # |   0 Hi!! can anyone tell where can i find the editorial??
•  » » 2 months ago, # ^ |   0 It will be uploaded in some time, be patient
•  » » 2 months ago, # ^ |   0
 » 2 months ago, # |   0 what is wrong with this problem B submission 184799218
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Gives wrong output for below input: Click HereInput: 1 3 3 1 2 1 3 2 3 Your Output: 4 Expected Output: 3 
 » 2 months ago, # |   0 I'm unable to find out why this code fails for pretest 3 for A. please help me #include using namespace std; int main() { int t; cin>>t; for(int i=0;i>n; int x[n]; for(int j=0;j>x[j]; } sort(x,x+n); for(int i=0;i0;i--){ if(x[i]==x[i-1])b++; else break; } if(a==n || b==n)cout<
•  » » 2 months ago, # ^ |   0 You're using int, the product of a and b may overflow.
•  » » » 2 months ago, # ^ |   0 This was my first contest and I was unable to find this and I submitted it 3 times with other variations. Thanks!!
•  » » 2 months ago, # ^ |   0 Overflow if all elements are same
•  » » 2 months ago, # ^ |   0 The result may larger than int,you should use long long
•  » » 2 months ago, # ^ |   0 you must using unsigned long long int type for variable n
•  » » 2 months ago, # ^ |   0 solution: long long n, a=1, b=1; or if(a==n || b==n)cout<<1LL*n*(n-1)<<"\n"; else cout<<1LL*a*b*2<<"\n"; 
 » 2 months ago, # | ← Rev. 3 →   +1 EDIT: I'm sorry, this idea won't work, since it should trigger integer overflow. It passed pretests though, but will likely FST. This is what I wrote, if anyone is interested (but it is not supposed to pass):C does not need a sieve or anything more complicated than Euclid's GCD algorithm. All you need to do is maintain a running LCM. Initially, the running LCM is just the first element of the array. Check the GCD of the running LCM and the next value. If the GCD is not 1, then there must be an overlapping factor between this next value and one of the earlier values (doesn't matter which), so the output is YES. Otherwise, update the running LCM (by multiplying the current running LCM with this next element that we just found to be coprime to it) and move on. If we read the entire array, and the GCD was always 1, then the output is NO.My submission: 184790195
•  » » 2 months ago, # ^ | ← Rev. 2 →   +16 You can run into overflow with multiplying?
•  » » 2 months ago, # ^ |   +29 Am I missing something or is SIGNED INTEGER OVERFLOW on vacation?
•  » » » 2 months ago, # ^ |   0 lol
•  » » 2 months ago, # ^ |   +13 Hi, your LCM will overflow very very fast.Here's a test that breaks your solution1 10 999999937 999999929 999999893 999999883 999999797 999999761 999999757 999999751 999999751 999999757
•  » » » 2 months ago, # ^ |   +17 Oh, crap, pretests didn't cover overflow. I'm sorry!
•  » » » » 2 months ago, # ^ |   +3 u gone now
•  » » » » » 2 months ago, # ^ |   0 I think this is the first time in a very long time that I only solved two problems in a Div2 round. My rating is gonna drop like a rock :(
 » 2 months ago, # |   -23 My solution for A has fallen in the system test because i forgot to print a new line in in the case when all array is equal , i hope you can skip this mistake as it is a presentation error and it is also not included in the pretests , i was about to get back to specialist and i hope you MikeMirzayanov can consider it correct.
•  » » 2 months ago, # ^ |   0 Same here vro
•  » » 2 months ago, # ^ |   +2 same, but it's a dumb mistake from both us and those who made pretests lol. Also, C's pretests kinda weak too.
•  » » » 2 months ago, # ^ |   -10 i agree it's a dumb mistake but there should be a strong pretests so that i can look back and fix it , also it is not some corner case or overflow issues , i hope the system can consider our solutions correct
 » 2 months ago, # |   0 Fuck so close to solving D. It’s just going level by level and do DP.no idea how to solve C.
•  » » 2 months ago, # ^ |   0 You just need to know that there are O(sqrt(M) / log(M)) primes from 1 to M. Then You can just check, if there are 2 numbers that both divide a prime below sqrt(10^9) ~= 35000. Also you should divide each number on all primes below sqrt(10^9). Then you'll have either 1 or a big prime. Then check if there are 2 primes.
 » 2 months ago, # |   0 What is idea for D, i know solution dp n^2 for 1d array with size n and that solution must be between 2 leaves in tree but thats it.
 » 2 months ago, # |   +27 Pretests were comparable to a steaming pile of shite
 » 2 months ago, # |   +63 Wow!! what this pretests.
 » 2 months ago, # | ← Rev. 2 →   -6 .
 » 2 months ago, # |   +21 WTF was C?
 » 2 months ago, # |   +77 I FSTed C 184739561 on test 16. I typoed and only factorized out 2 and 3. This passes 15 tests...
 » 2 months ago, # |   -19 This is my first div 2 contest and I was able to solve 2 problems (system tests passed)I solved the second problem using set and sliding window technique, the solution is pretty intuitive and simple to understand, hence I thought of sharing it. #include using namespace std; typedef long long ll; void solve(){ int n, m; cin>>n>>m; vector> pairs; for(int i=0; i>a>>b; pairs.push_back({a, b}); } // create an adjacency list with the pairs vector> AList(n+1); for(vector& edge : pairs) { AList[edge[0]].push_back(edge[1]); AList[edge[1]].push_back(edge[0]); } // we can solve this problem using set and sliding window long long result=0; int l=0; map window; for(int i=0; i>t; while(t--){ solve(); } return 0; } 
 » 2 months ago, # |   0 184778086 is not correct184778210 also184766650 also
•  » » 2 months ago, # ^ |   0 please add more tests
 » 2 months ago, # |   +34 Problem F is a specialization of 1479D - Odd Mineral Resource. (Technically, that problem doesn't ask for the minimum value but most solutions for that problem will find the minimum anyway.)
•  » » 2 months ago, # ^ |   +20 In Odd Mineral Resource the queries are not online so parallel binary search + sweepline fenwick tree can be used, but in problem F a persistent segment tree is required. The two problems are still really similarly though
•  » » » 2 months ago, # ^ |   0 True, I forgot about that. I tried the persistent segment tree solution for Odd Mineral Resource so it was the same to me.
 » 2 months ago, # |   +7 Weak pretest.
 » 2 months ago, # | ← Rev. 2 →   0
 » 2 months ago, # | ← Rev. 2 →   +12 I'm just much surprised that how my solution for problem C got accepted in system testing (It shows that main tests are really weak), can anyone hack it? 184797036
•  » » 2 months ago, # ^ |   0 Maybe your code hit the omission in making data.
•  » » » 2 months ago, # ^ |   0 Yeah I know, That's why I asked people to hack it.
 » 2 months ago, # |   0 Can this idea work or is just way too slow even with a better implementation? (Problem C):https://codeforces.com/contest/1771/submission/184805467
•  » » 2 months ago, # ^ |   0 I think approaches with sieve on Python get TLE on this problem. I also kept getting TLE during the contest. But when I re-implemented the same approach with C++, I got AC.
•  » » » 2 months ago, # ^ |   +1 Thank you :)
 » 2 months ago, # |   +13 Very weak pretests for $C$.
 » 2 months ago, # |   0 What would be the expected rating of the first 2 questions?
 » 2 months ago, # |   0 What is wrong with my solution of A? It fails on 24th test. 184739221
•  » » 2 months ago, # ^ |   0 No clue, but I would suggest to convert all your variables to long long and submit again.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 I think you need to remove the "else" from: else if(v[i] == minn){ to: if(v[i] == minn){ `
•  » » » 2 months ago, # ^ |   0 Thank you so much!
 » 2 months ago, # |   0 Is it possible to hack solutions and get points? I think I see some wrong solutions for some questions but I don't know how to hack. They just need different input.
 » 2 months ago, # |   0 Got TL on F in system tests. Replaced map with unordered_map, got at least 10x speed-up on test 30: before that I was getting TL on test 30, but with unordered_map it works under 150 ms. It was log(N) per query anyway, and I was still using std::map O(N) times, but changing coordinate compression container to unordered_map somehow miraculously sped up the program. Just wondering, is it okay that such a small change caused that much performance loss?
•  » » 2 months ago, # ^ |   0 „Small change”? unordered_map is a hash map whereas map is a BST.
•  » » » 2 months ago, # ^ |   0 Yeah, but the size of the map was at most 2*10^5 (also at most 4*10^5 queries), and it shouldn't be anywhere close to time limit. As AlternatingCurrent pointed out, it seems like it is a problem from C++ standard library.
•  » » 2 months ago, # ^ |   +3 The same problem was mentioned in this blog. It seems like a problem from c++ itself :(
 » 2 months ago, # |   0 how to solve F?
•  » » 2 months ago, # ^ |