AmShZ's blog

By AmShZ, history, 15 months ago,

Hi Codeforces!

Dio, Keshi, Tet, alireza_kaviani, Davoth, AliShahali1382 and I are delighted to invite you to participate in Codeforces Round #722 (Div. 1) and Codeforces Round #722 (Div. 2), which will be held at May/24/2021 17:35 (Moscow time). Each division will have 6 problems and 2 hours and 15 minutes to solve them.

The curse has finally been lifted! We are proud to announce that antontrygubO_o didn't reject even a single task from the Div. 1 part!

Huge thanks to the following people:

For the sake of having short statements, this round does not have a theme. The characters featured in the statements are: Soroush (Tet), Sifid (Davoth), Parsa (Dio), Nima (N.N_2004), AaParsa (AaParsa), Haj Davood (davooddkareshki), Kavi (alireza_kaviani), Keshi (Keshi), Mashtali (AliShahali1382) and AmShZ (AmShZ).

Please read all of the problems and their notes, enjoy your time and solve as many as you can! Good luck have fun to everyone!

The scoring distributions will be announced later.

UPD: Here are the scoring distributions:

• Div. 1: 750 1000 1750 2000 2750 3000

• Div. 2: 500 1250 1750 2000 2750 3000

UPD: Editorial is out!

• +1145

 » 15 months ago, # | ← Rev. 3 →   +294 Being a setter, I fully understand the pain of other setters while writing statements.
•  » » 15 months ago, # ^ |   +40 Thank you for your contribution.
•  » » 15 months ago, # ^ |   +24 "Tet" is Vietnamese traditional new year holiday. :D See you, I think about Tet :D
 » 15 months ago, # |   +137
•  » » 15 months ago, # ^ |   +14
 » 15 months ago, # |   +119 omg saarang tester orz
•  » » 15 months ago, # ^ |   -21 what is orz ?
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +40 imagine O as the head of the man bowing , r as his hands , z as the rest of his body . Its used for giving ovation
•  » » » » 15 months ago, # ^ |   +44 woahhhh. thanks man
 » 15 months ago, # | ← Rev. 2 →   +185 as a teacher and as a friend, I am sure we will see a great contest :)
•  » » 15 months ago, # ^ |   +140 <3
•  » » » 15 months ago, # ^ |   +91 <3
•  » » » » 15 months ago, # ^ |   +2 <3
•  » » » » » 15 months ago, # ^ | ← Rev. 3 →   0 <3
•  » » » » » 15 months ago, # ^ |   0 <3
•  » » » » » » 15 months ago, # ^ |   -16 <3
•  » » 15 months ago, # ^ |   +39 <3
•  » » » 15 months ago, # ^ |   0 <3
 » 15 months ago, # |   +85 Finally wait for Anton round is over, would be a great round for sure!!!
•  » » 15 months ago, # ^ |   +9 its a trap
•  » » » 15 months ago, # ^ |   +9 Not in this contest :(
•  » » » » 15 months ago, # ^ |   +5 But its_Atrap
 » 15 months ago, # |   +136 As a tester, the problems are very nice and interesting! I recommend everybody to participate!
•  » » 15 months ago, # ^ | ← Rev. 3 →   +102 As a tester, I agree with vodacbaoan!
•  » » » 15 months ago, # ^ |   +7 orz <3
•  » » » 15 months ago, # ^ |   +9 As a participant, I agree with you guys:)
•  » » 15 months ago, # ^ |   +5 How to be a tester?
•  » » » 15 months ago, # ^ |   +12 You should either be friends with setters or have a history of being a setter.
•  » » » » 15 months ago, # ^ |   +3 It's too hard for me
•  » » 15 months ago, # ^ |   +3 Sir, How can I be a tester? :P
•  » » 15 months ago, # ^ |   -21 vodacbaoan is the official wife of Monogon. Upvote if u want them to marry.
•  » » » 15 months ago, # ^ |   -8 so you have downvote hell. Enjoy
•  » » » » 15 months ago, # ^ |   +5 Do u have a crush on vodac ?? xD
•  » » » » » 15 months ago, # ^ |   0 Yes
 » 15 months ago, # | ← Rev. 2 →   +31 Woow !! Finally again an iranian round :)) I'm so interested to participate in my compatriots' round ! Hope to reach pupil in this round, Thanks AmShZ and other dear authors.
•  » » 15 months ago, # ^ |   +13 Many times I see people commenting it's an Indian round, it's a Chinese round.. etc and now you are saying it's an Iranian round. What difference does it make? I don't think there is some pattern in the problem set associated with the region or something like that.
•  » » » 15 months ago, # ^ |   +3 We respect to our compatriots ! :)
•  » » » 15 months ago, # ^ |   +57 It's just that participants get excited because they have the same nationality as the authors. Not sure if it's true for Iran, but I guess that some countries have a few problem-setting-eligible users and those users are well-known among the people of that country. Wouldn't it excite you to see an acquaintance of yours set a round?
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   0 Agree with you
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   +35 I definitely would, but expressing it in that way looks inappropriate. Mentioning country looks like drawing borders to me.Maybe I'm over reacting. Btw thanks for the contest.
•  » » » » » 15 months ago, # ^ |   +15 Nah I feel the exact same way as you. But then again, different people have different opinions and beliefs, so I dont mind it.
•  » » » » » 15 months ago, # ^ | ← Rev. 4 →   +19 Chinese round: Maths, implementaion,data structureRussian round: constructive, observationalIranian rounds: balanced perfectlyIndeed it was balanced perfectly.
•  » » » 15 months ago, # ^ |   +18 i will add something about your comment after the contest
•  » » » » 15 months ago, # ^ |   +16 Hello, what is it?
•  » » » 15 months ago, # ^ |   +38 ok as i said there are some few things you can find out when the contest is made by irainian:1) there are always some graph problem and most of the graph problems are either shortest path or tree problmes2) there are lots of dp problems3) there is no complicated greedy problems because most of irainians hates greedy4) they also hate geometry so you 99% can be sure there is no geometry5) there are usually hard combinatorics & DS problems these are the things that ive learned because im either student / classmate / friend with them : )
•  » » » » 15 months ago, # ^ |   0 "There is no complicated greedy problems because most of Irainians hate greedy" =(
•  » » » » » 15 months ago, # ^ |   0 there is no complicated greedy problems because most of irainians hates greedy I dont know who likes greedy, atleast no one I know.
•  » » » » » » 15 months ago, # ^ |   +3 i like greedy
•  » » » » » » » 15 months ago, # ^ |   +3 atleast no one I know. I dont know you. :/
•  » » » » » » » » 15 months ago, # ^ |   +1 i still like greedy
•  » » » » » » 15 months ago, # ^ |   -6 I love greedy.
 » 15 months ago, # |   +246 as an author, give me contribution!
•  » » 15 months ago, # ^ |   +65 as a no one , sik tir :)))
•  » » » 15 months ago, # ^ |   0 :(
•  » » 15 months ago, # ^ |   -8 as a Participant, I have given you contribution
 » 15 months ago, # |   +28 orz
 » 15 months ago, # |   +59 antontrygubO_o orz.
 » 15 months ago, # | ← Rev. 3 →   +41 Its a really nice round with great and beautiful problems. I hope everybody can enjoy this round.great effort from all of the setters to finaly make this round.good luck everybody and have fun. (Dont read kostia's comments :))
 » 15 months ago, # |   +85 As a tester, the problems are interesting and the statements are short. Hope you enjoy the round :)
•  » » 15 months ago, # ^ |   -43 Can we expect strong pretests?
 » 15 months ago, # |   +23 Such boys !
 » 15 months ago, # |   +7 round after another 2 days:( can't wait
 » 15 months ago, # |   +53 me seeing the contest announcement
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 Frankly, you shouldn't count it as a ghaazzz round. And this way we can still expect a real ghaazzz round.
•  » » » 15 months ago, # ^ |   0 agree.we can't count it as a ghaaazzz round,but as a ghaazzz round.
•  » » » » 15 months ago, # ^ |   0 Edited! (if that's how you want to see it)
 » 15 months ago, # |   +74 As a tester, I am way too late to post an as a tester comment.(insert all the normal tester comments about how good the round was here)
 » 15 months ago, # |   0 Best of luck to all the participants :)
 » 15 months ago, # |   0 We are proud to announce that antontrygubO_o didn't reject even a single task from the Div. 1 part Hmm.....this is gonna be a very interesting round. Good luck. See you on the scoreboard : )
 » 15 months ago, # |   +48 as a tester, orz
 » 15 months ago, # |   +290
 » 15 months ago, # |   +5 The best adhoc cooontest")
 » 15 months ago, # |   -96 Whenever We open Codeforces and see a contest announcement on home page, Inside us
•  » » 15 months ago, # ^ |   +21
 » 15 months ago, # |   +10 I hope Question C has no nonsense
 » 15 months ago, # |   0 Good Luck Everyone !!
•  » » 15 months ago, # ^ |   +1 Thank you boii.
 » 15 months ago, # |   0 Thank you
 » 15 months ago, # |   +3 Length of the round is set to be 2 hours on the contests page, please fix it. AmShZ
 » 15 months ago, # |   +4 May I ask what was the reasoning of having exactly 2 hours 15 minutes, and not 2 hours, and not even 2.5 hours?
•  » » 15 months ago, # ^ |   +105 Whenever you give a 2hr contest and submit one of those messy problems in the last minute and get WA on pretest 2 and then wish you had only 10-15 minutes more. These are those 15 minutes.
 » 15 months ago, # |   -34 Benq is going to participate in this game, I think he will play a very good result in this game.
•  » » 15 months ago, # ^ |   -37 which one can winning can you guess it may be turist either benq.
 » 15 months ago, # |   +16 Finally another Div.1!!!But what a pity that the contest is held on Monday! I think many people like me can't participate in. sad to see that
•  » » 15 months ago, # ^ |   0 dblark Google Kickstart(which on Sunday) may be the reason.
 » 15 months ago, # |   +10 Auto comment: topic has been updated by Tet (previous revision, new revision, compare).
 » 15 months ago, # |   +10 The blog mentions the length of the contest as 2 hours and 15 minutes, while the contest page is showing 2:00.
•  » » 15 months ago, # ^ |   +16 We don't have editing rights yet, it'll be fixed soon.
 » 15 months ago, # |   +27 Ever since I became candidate master(more than one month ago). It's first Div. 1 contest Hope to have good contest Thank you very much Haj Davood :)
 » 15 months ago, # |   0 1-GON Back to work though as a tester...Hoping for a great round this time.Best of luck everyone Regain your lost rating.
 » 15 months ago, # |   0 Excited for the Contest hope that I will be able to solve at least B in this contest
•  » » 15 months ago, # ^ |   0 i also try for that may be i can solved that at least 2 either 1
 » 15 months ago, # |   -24 Which one won the game Div 1? 1) Benq 2) Tourist 3) Radewoosh Guess?
•  » » 15 months ago, # ^ |   +26 None of the them :P
•  » » » 15 months ago, # ^ | ← Rev. 2 →   -33 Which one won the game Div 1? 1) Benq 2) Tourist 3) Radewoosh Guess?
•  » » » » 15 months ago, # ^ |   +7 He used a very high level technique called "guessing"
•  » » » » » 15 months ago, # ^ |   -31 You are right bro ha....world number one method
•  » » » » » 15 months ago, # ^ | ← Rev. 2 →   -17 Which one won the game Div 1? 1) Benq 2) Tourist 3) Radewoosh Guess?
 » 15 months ago, # |   +15 Why codeforces is not taking contest frequently ? The wait after every contest is lasting soooo long :(
•  » » 15 months ago, # ^ |   +3 Though codeforces is kinda better, but you can also participate in other online contests. Such as atcoder, codechef and even yukicoder. These websites combined you'll have at least one contest every other day(maybe everyday).
•  » » » 15 months ago, # ^ |   +8 Ya , but the happiness of increase in rating on codeforces is of different level. :)
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   +3 I agree. The same is true for atcoder, but still not as much as codeforces. Besides, competing is great itself.
 » 15 months ago, # |   +14 Don't know why, but I feel good about this contest. Feel like I'm going to get to almost reach pupil.
 » 15 months ago, # |   +22 antontrygubO_o orz.
•  » » 15 months ago, # ^ |   +9
•  » » » 15 months ago, # ^ |   +12 Indeed.
 » 15 months ago, # | ← Rev. 2 →   -24 k
 » 15 months ago, # |   +10 good luck, have fun :)
 » 15 months ago, # |   +28 Dio If I surpass you, will you give that username?
•  » » 15 months ago, # ^ |   +4 IT WAS ME DIO
•  » » » 15 months ago, # ^ |   +60 i dont think so...
 » 15 months ago, # |   +9 The problems are always interesting <3
 » 15 months ago, # |   +24 Iran is an actually a good country :D
•  » » 15 months ago, # ^ |   +7 I agree with you
 » 15 months ago, # |   +22 and if i say orz i get negative contribution "(
 » 15 months ago, # |   0 May the problems will be much easier than character featured names.;(
 » 15 months ago, # |   +14 Hi ! When will the scoring distributions be announced ?
•  » » 15 months ago, # ^ |   +16 We are still discussing it :(I'll post them the instant we agree on something ...
 » 15 months ago, # |   -33 I wish somehow we can redirect some contributions to antontrygubO_o?
 » 15 months ago, # |   +21 B part has a score of 1250 instead of 1000 or 750, I hope I become a specialist.
•  » » 15 months ago, # ^ |   +13 Best of luck! :)
•  » » 15 months ago, # ^ |   +3 You have solved 393 problems in 3 months!! Great work bro. All the best!
•  » » » 15 months ago, # ^ |   +4 Thanks a lot :)
 » 15 months ago, # |   0 how does the scoring distribution of the problem matter? What does it actually mean?
•  » » 15 months ago, # ^ |   +3 It gives you an idea about the level of the problem. Though it is not always accurate but most of the times it is. For example B problem might be a bit hard today as compared to other div-2's B problem but again it might be easy too. You can never tell you can only guess.
 » 15 months ago, # |   -47 Div 2 3rd problem is of same difficulty of Div1 3rd problem wow :(
•  » » 15 months ago, # ^ |   -15 what algorithm did u use to find that out
 » 15 months ago, # |   +18 Seeing the score distribution, contest will be hard
•  » » 15 months ago, # ^ |   -7 This is one of the hardest code distribution I have seen so far.
 » 15 months ago, # |   -10 why sooo weird score distribution in div-2?
 » 15 months ago, # |   -41 time to skip after seeing the score distribution.
•  » » 15 months ago, # ^ |   +12 you should never skip
 » 15 months ago, # |   +11 good luck to all!
 » 15 months ago, # |   0 Problem B : Sifid likes everything big. Nice :)
 » 15 months ago, # | ← Rev. 2 →   -15 :)
 » 15 months ago, # |   +12 Ghaaz = Goose(in Persian)
 » 15 months ago, # |   +22 rainboy orz
 » 15 months ago, # |   +1 Only way i can solve Div 2 C is, if it is given as captcha to view anime online.
 » 15 months ago, # |   +6 how to solve C?:)
•  » » 15 months ago, # ^ |   +1 dp on trees, and only $l_{i}$ and $r_{i}$ are important in the range.
•  » » » 15 months ago, # ^ |   +5 I did exactly the same, still I'm getting TLE!! :(
•  » » 15 months ago, # ^ | ← Rev. 2 →   +3 can solve by dfs. just handle parent and child relation and add every child value with parent then answer is root value. Spoiler#include using namespace std; #define mxx 1e18 #define mnn -1e18 //#define int long long #define Y() cout<< "YES" < adj[N]; ll power(ll n,ll p){if(p==0) return 1;if(p==1)return n;if(p%2)return power(n,p-1)*n;else{ll x=power(n,p/2);return x*x;}} ll modpow(ll a,ll b,ll m){ll ans=1;while(b){if(b&1)ans=(ans*a)%m;b/=2;a=(a*a)%m;}return ans;} ll nsum(ll num){return (num*(num+1))/2;} void edge (ll u,ll v) {adj[u].PSB(v) ;adj[v].PSB(u);} /*------------------START---------------------*/ bool vis[N]; ll par[N],root; ll ansmx[N],ansmn[N],l[N],r[N],cnt[N]; ll dfs(ll rot){ vis[rot]=true; for(ll u: adj[rot]){ if(!vis[u]){ par[u]=rot; dfs(u); } } if(rot==root){ return max(ansmn[root],ansmx[root]); } ll mn=l[rot],mx=r[rot]; ll pmn=l[par[rot]],pmx=r[par[rot]]; ll v1=max(abs(pmn-mn)+ansmn[rot],abs(pmn-mx)+ansmx[rot]); ll v2=max(abs(pmx-mn)+ansmn[rot],abs(pmx-mx)+ansmx[rot]); ansmn[par[rot]]+=v1; ansmx[par[rot]]+=v2; //ansmn[par[rot]]+=ansmn[rot]; // ansmx[par[rot]]+=ansmx[rot]; //cout<>n; vis[0]=false; ansmn[0]=ansmx[0]=cnt[0]=0; for(ll i=1;i<=n;i++){ adj[i].clear(); cin>>l[i]>>r[i]; vis[i]=false; ansmx[i]=ansmn[i]=0; cnt[i]=0; } for(ll i=1;i>u>>v; edge(u,v); cnt[u]++,cnt[v]++; } for(ll i=1;i<=n;i++){ if(cnt[i]==1){ root=i; break; } } par[root]=-1; ll ans= dfs(root); cout<>Test; while(Test--){ solve(); } return 0; } 
•  » » 15 months ago, # ^ |   0 I tried greedy, but failed on pretest 2. 117234211
•  » » 15 months ago, # ^ |   +1 For those who solved Div2C / Div1A, could you guide why DFS is needed (as opposed to BFS)?
•  » » » 15 months ago, # ^ |   0 Any traversal technique works ig. I solved using dfs though xD
•  » » » » 15 months ago, # ^ |   0 Actually I had used BFS, which was incorrect. I think I now understand why. DFS is a must here since the max value of the root node (you can pick any node as root) depends on the max values of its children, which in turn depend on their children, etc. So once it's clear that you have to pick either L or R for each vertex (and no value in between), then it's a matter of solving subproblems first — recursion with DP does that effectively.
•  » » » » » 15 months ago, # ^ |   0 Yeah, it doesn't I overlooked it. Basically it's like we should find the answer for all nodes in the last level and then the previous level and so on. So we can somehow store answers for higher levels first and then for lower levels using BFS. But we have to store the nodes which are at a particular level and it is implementation heavy.So I think BFS is something like top-down traversal so it's better to use DFS as it's a bottom-up traversal in such cases.
 » 15 months ago, # |   +21 Is O(N^3) meant to pass div1D?
 » 15 months ago, # |   0 Why is a simple DFS getting TLE on Div2 C??
•  » » 15 months ago, # ^ |   +3 No its not
•  » » » 15 months ago, # ^ |   0
•  » » » » 15 months ago, # ^ |   +7 Use fast IO in C++ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
•  » » » » 15 months ago, # ^ |   +7 I think the large input gives you TLE. Try using ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); this at the begining.
•  » » » » » 15 months ago, # ^ |   +6 You mean to say the reason it's TLE has got nothing to do with the logic?? It was due to slow I/O?? I'll cry the whole night today :(
•  » » » » » » 15 months ago, # ^ |   +23 Yeah but all of us got TLE on some problem before this and learned from that to use this "trick". At the end of the day you learned something new so is a good day!
•  » » 15 months ago, # ^ |   0 Because it has O($n^2$) time complexity
•  » » » 15 months ago, # ^ |   0 My submission?
•  » » 15 months ago, # ^ |   0 It happened to me too. Simple O(n) recursive dp. TLE on test 4. I have absolutely no idea why.
 » 15 months ago, # |   0 What happens if you AC a problem twice in pretests? I resubmitted one of the problems due to runtime and got -50 penalty but if the first solution passes systests, will I still get penalty?
•  » » 15 months ago, # ^ |   0 Yes, the system will skip your first solution. You would have got a penalty of 50 points plus the score of that problem will be the score at the time you submitted your second solution.
•  » » 15 months ago, # ^ |   +12 I don't think the first submission even gets run on system tests, so you will still get the penalty.
•  » » » 15 months ago, # ^ |   +27 I like meethi lassi and chole bhature.
•  » » » 15 months ago, # ^ |   +1 Oh ok, sad
•  » » 15 months ago, # ^ |   +8 Only the last submission will be judged against systests. (The first one is given a verdict of 'Skipped' after systests.) You will still get penalty.
 » 15 months ago, # |   +1 Is D on OEIS? And how to D it?
•  » » 15 months ago, # ^ |   -6 You need this one https://oeis.org/A051950
•  » » 15 months ago, # ^ |   +2 I used dp. categorized the length of pair (L) into two parts:for each n, define f(L) as:if L <= n, only those n % (L-1) == 0 will contribute. I count the frequency of each prime factor of n (p_i) and do a product of (p_i + 1).if L > n, it will be a fully covering case, and the inner part will be dp[L-n-1]. Those can be calculated use prefix sum.so each dp[n] = sum_{L=2}^{2n} f(L).I'm not sure if this is good for system test, and sorry for the brevity of the description
•  » » 15 months ago, # ^ | ← Rev. 2 →   +9 Very hard to demonstrate without paper.[...] [...]Suppose those two arches have the same length. Then we know nothing can belong inside of both of them, as each subarch isn't inside of the other (place inside of the left, not inside of the right), etc. And because the subarch must be smaller, then neither condition can be satisfied.Now, we know that must be a be a thick arch. Like for example, an arch of "thickness" 2 cross weaves 2 archs, if you know what I mean. And now you can place subarchs inside, this gives a relation dp[i] = sum of all j
 » 15 months ago, # |   +1 Holy fk I passed D pretests in the last seconds! Shoot ...
•  » » 15 months ago, # ^ |   0 Hints on problem C, please.
•  » » » 15 months ago, # ^ |   +3 I used DP actually. Try to solve the problem (maximum sum) for each subtree. And for each node u, you can calculate what the result will be if you use the left or the right.The transition for one node using its left value will bedp[u][L] = max(|l[u] — l[v]| + dp[v][L], |l[u] — r[v]| + dp[v][R])Let me know if you need more spoilers
•  » » » » 15 months ago, # ^ |   +3 I'll try. Thanks!
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   0 Solved it! Also learned a new way to implement DFS from your submission. Thanks a ton. Edit: Will this implementation work on any graph or is it exclusive for trees?
•  » » » » » 15 months ago, # ^ |   0 Hi thereI learned this from https://cp-algorithms.com/graph/depth-first-search.html :)I think the one I submitted only works for trees since it only checks whether the parent has been visited or not. You may an extra visited flag to work with general graph.
 » 15 months ago, # |   0 I am not familiar with the rules. I have submitted a correct solution at 0:05. But at around 0:35, I submitted another correct solution. I wonder why my score for that question is based on the finishing time of the latter one? (0:35 instead if 0:05)
•  » » 15 months ago, # ^ |   +1 The second one is scored.
•  » » » 15 months ago, # ^ |   0 I understand the rule right now but I wanna know the rationale behind this rule. Why don't it count the first correct submission that able to pass the system testing.
•  » » » » 15 months ago, # ^ |   0 If you want the first to count, then there is no need to submit the second. So, you decide.
•  » » » » » 15 months ago, # ^ |   0 It's just because I didn't know this rule before this contest. I would definitely not do it again in the future contest. Btw I resubmitted it just because the second one has a higher chance to pass the system testing.
•  » » » » » » 15 months ago, # ^ |   +3 Then isn't that a valid a reason to not consider your first submission ? As you were not confident that the first one would pass the final test cases and modified it to pass the system cases.I think its kinda synonymous to getting a WA and then debugging and resubmitting the correct solution .
•  » » 15 months ago, # ^ |   0 In case of multiple correct submissions (for same question), only latest one is considered. All previous submissions get skipped and don't appear in system testing.
 » 15 months ago, # |   0 Does D need some special DS or math technique?
•  » » 15 months ago, # ^ |   +3 DP and number theory is enough.
 » 15 months ago, # | ← Rev. 4 →   0 My approach on C CodeCan anyone tell me what is wrong with it. I have taken 4 critical numbers for each vertex 1) li2) ri3) (li+ri)/24) (li+ri+1)/2The best result for each of them in dfs is returned in a array in the same order .In the end when recursive calls finish we output max of all 4**** EDIT NOW WORKINGWE need only left mini and Right maxiDfs Based Solution of C Parsa's Humongous Tree without DP based on the fact that during path traversal on a tree from root , A particular node is reached only once.We return a pair {a,b} from every node.A has the best solution from that node to all nodes below it when left_mini is assigned to that node.B has the best solution from that node to all nodes below it when right_maxi is assigned to that node.We store best possible values of the current node from all children node i.e. one with maxi on all possible calls and other with mini and then return it.In the end when recursive calls end print the maximum of the pair of values returned from the root.Solution
 » 15 months ago, # |   0 D < C :((
•  » » 15 months ago, # ^ |   +22 No,D>C.
•  » » 15 months ago, # ^ |   +8 It took me more than 1 hour to solve D, whereas less than 10 mins to solve C...
 » 15 months ago, # |   -30 B is not nice problem, also misplaced.B>D>C
•  » » 15 months ago, # ^ |   +3 I guess you also thought that subsequence must be continuous.
•  » » » 15 months ago, # ^ |   -8 No, I think I understood the promblem correctly. But there seems to be some more or less obvious observation needed that is invisible to me.From other submission it seems that we can use all negative numbers (ok, understood), and then all positives up to the first bigger than the smallest diff so far.But why, why cannot be there ohter solution? Or did I get it wrong?
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   0 Have you considered the case when any element <=0 is repeating twice?This has caused me 5 wa and 40 minutes.
•  » » » » 15 months ago, # ^ |   +4 Note that the difference between two positive numbers is strictly smaller than the larger of the two numbers, so any solution can have at most one positive number. On the other hand, we can take as many non-positive numbers as we like. So the question really only is about whether we can take a positive number in addition to the non-positive ones, which is possible iff a positive number at most as large as any difference between the non-positive numbers exists.
•  » » » » » 15 months ago, # ^ |   -14 "...so any solution can have at most one positive number."Ok, thanks, that is the missing observation. What a stupid problem :/
•  » » » » » » 15 months ago, # ^ |   -15 Indeed, it was stupid.
•  » » » » » » 15 months ago, # ^ |   0 I found B to be hard to understand, not from the language, but from the definition of the promblem itself. I had to read the definition of a strange seq at least a dozen times, and actually now I am hardly able to tell from head (just did read it again some seconds ago).So, basically that problem is "somehow get that wiered definition into your head, then you will quickly see the solution." I am ok with a complecated, or strange definition if it is a complecated problem. But a very simple problem with a complecated definition is a bad problem.
•  » » » » 15 months ago, # ^ |   +4 You can see that there can be at most one positive integer and all others are 0/negative and their minimum abs difference must be greater than the positive number so we choose least positive number. If that number is still greater than minimum abs difference we remove that number. Since we are taking all nonpositive integers there can't be another solution. If we remove some negative integer to increase difference, ans will be less than number of nonpositive integers.
•  » » » » 15 months ago, # ^ |   0 Problem Div2B was constructive at best, it felt like you cater to the observation required and it should work. I am also curious about other approaches as well :)
•  » » 15 months ago, # ^ |   0 Tried to implement a DP solution for 2 hours. Only got TLE: https://codeforces.com/contest/1529/submission/117224214How did some many people come up with a solution for B?
 » 15 months ago, # |   +1 How did you solve B? Tried for two hours to Frankenstein it with all of the possible cases I could think of, using different sizes of negative, zero and one positive number.
•  » » 15 months ago, # ^ |   0 You can prove that there can be at most 1 positive number. Then it's easy.Take all negative + zero numbers or take the smallest positive number also. For the second choice check whether it is possible.
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 i tried with 5 case and take the maximum.1. all zero and all negative.2. only one zero and only one positive3. only one positive4. all negative and one positive (for taking positive and negative at a time check minimum of positive >= max difference of any 2 negative numbers)5. all negative and one zero and one positive (And taking all pos, neg and zero checked minimum of abs(negative value) >= min positive value and must checked 4 condition also)And taking all pos, neg and zero checked minimum of highest negative value >= min pos value and
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 Very easy solution: SPOILERSLet's notice that the order of elements doesn't matter. Sort the array. Then in a loop calculate the least difference and check — is it possible to add a new element?  int n; cin >> n; vector a(n); for(int i = 0; i < n; i++) cin >> a[i]; sort(all(a)); int diff = INT_MAX; int l = 1; for(int i = 1; i < n; i++) { diff = min(diff, a[i] - a[i - 1]); if(diff < a[i]) break; l++; } cout << l << "\n"; 
 » 15 months ago, # |   0 Used deque for interval minimum with correct complexity in div1D but TLE, unfortunate.
•  » » 15 months ago, # ^ |   0 Was your code $\mathcal{O}(nm)$? Because even $\mathcal{O}(nm \log n)$ passes in less than a second: 117224037
•  » » » 15 months ago, # ^ |   0 117252128mango_lassi I think it is O(N^3) or O(NM) if you like, I will take a look again.
•  » » » » 15 months ago, # ^ |   0 Looks like $\mathcal{O}(N^3)$, so I guess the constants are just too high.Kinda sad if they were trying to cut $\mathcal{O}(nm \log n)$ and this happens :(
•  » » 15 months ago, # ^ |   0 It doesn't, consider this code : Link
•  » » » 15 months ago, # ^ |   0 I guess I am just unfortunate.
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   +5 I think you can avoid re-computation using deque by doing it before only and storing it?
•  » » » » » 15 months ago, # ^ | ← Rev. 2 →   0 Yep you are right. But you wrote in the smart way (avoid recomputing) and still took almost two seconds, which suggests that the deque solution probably has a large constant factor. Considering that most people's submissions ran in 1~2s, I think there is a good reason that I avoid unnecessary deque next time.Still, thank you very much for your suggestions.
•  » » 15 months ago, # ^ |   0 mango_lassi117254437 Didn't use deque and simply passed, but still used more than one second though.
•  » » » 15 months ago, # ^ |   0 Wrong submission? That's a solution to div2A
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   0 Oh sorry, this one 117255437
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   0 I will take a look at your solution... less than one second is interesting.
 » 15 months ago, # |   0 Can someone tell me what is wrong with my C ? I have built logic like dp but its not precise dp. Code... //Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define F first #define S second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i> g(N); vector w(N); vector cal(N,-1); ll ans = 0; void dfs(int v,int p){ bool leaf = true; for(int to : g[v]){ if(to!=p){ leaf = false; dfs(to,v); } } if(!leaf){ ll a1=0,a2=0; for(int to : g[v]){ if(cal[to]!=-1){ a1+=abs(cal[to]-w[v].F); a2+=abs(cal[to]-w[v].S); } else{ a1+=max(abs(w[to].F-w[v].F),abs(w[to].S-w[v].F)); a2+=max(abs(w[to].F-w[v].S),abs(w[to].S-w[v].S)); } } if(a1>a2) cal[v] = w[v].F; if(a2>a1) cal[v] = w[v].S; ans+=max(a1,a2); } } void run_case(){ int n,i,j,k,u,v; cin >> n; for(i=0;i> w[i].F >> w[i].S; } for(i=0;i> u >> v; --u,--v; g[u].pb(v); g[v].pb(u); } ans = 0; dfs(0,0); cout<> tt; while(tt--){ run_case(); } } 
 » 15 months ago, # |   +24 such nice problems! good job :)
 » 15 months ago, # | ← Rev. 2 →   0 I found that my $D$ is on the edge of the TL much latter in the contest but decided against improving it(I hope it passes), how to calculate number of divisors for each [1,2n] fast, I did $O(sieve*logn)$?
•  » » 15 months ago, # ^ |   0 Did you pass? I used sieve to calculate number of divisors but TLE in python
•  » » 15 months ago, # ^ |   +3 You can do it by iterating for each number from 1...n by its multiples. 1,2,3,4,.... 2,4,6,8..... 3,6,9,12... . . k, 2k, 3k... . . n it's very similar to sieve. This has complexity NlogN
•  » » » 15 months ago, # ^ |   0 Yeah, very stupid of me being unable to find such simple algorithm given that I had used this before more than once
•  » » » 15 months ago, # ^ |   0 Are you familier with Python? Below is my function to count number of divisors. I think it is O(nlogn), please correct if I'm wrong. def findDivisors(N): div = [0] * (N + 1) for i in range(1, N + 1): for j in range(i, N + 1, i): div[j] += 1 return div 
•  » » 15 months ago, # ^ |   0 Can you explain the basic idea of how to solve D.
•  » » » 15 months ago, # ^ |   +3 @dhruv7888 It can be solve by DP. Ex, N = 3: dp[3] = dp[2] + dp[1] + dp[0] + number of diviors of 3Because when you know all the good pairs of N = 2, to form good pair with N = 3, you can add a pair bound all pairs with N = 2, similarly add 2 outside pair to N = 1 ...
 » 15 months ago, # |   0 Does anyone solve problem D with DP formula, dp[i] = prefix[i] + number of Divisors of i? I got TLE, could you share the way to count the number of divisors?
•  » » 15 months ago, # ^ |   0 It's because you used a slow method to find the number of divisor of n. There exists a algorithm that takes O(nlogn) time to find all the number of divisor from i to n. Yours take O(n^2)
•  » » 15 months ago, # ^ |   +3 If you have factorisation in form $n = \prod p_i^{a_i}$ then number of divisors is equal to $\prod (a_i + 1)$.Factorisation can be done pretty quickly by precomputing all primes, or just using linear sieve.
•  » » » 15 months ago, # ^ |   0 Thank you, the factorisation is really good idea, I have leant new thing. What the time complexity of the factorisation? Does Linear sieve mean that iterating for each number from 1...n by its multiples? And it will take O(NlogN)?
•  » » » » 15 months ago, # ^ | ← Rev. 3 →   +1 https://cp-algorithms.com/algebra/prime-sieve-linear.html What the time complexity of the factorisation? Either $O(primes < \sqrt{n})$ or O(prime factors of n) depending on what you use. Both should pass pretty comfortably.
•  » » 15 months ago, # ^ |   +16 for (int i=1; i<=n; i++) { for (int j=i; j<=n; j+=i) { factor[j]+=1; } } 
•  » » » 15 months ago, # ^ | ← Rev. 2 →   0 Thank all you guys, I found the reason of TLE not because of count number of divisors function. It got TLE because I performed MOD at last step and when result is too large MOD will result TLE.
•  » » 15 months ago, # ^ |   0 Yes. I used dp[i] = pref[i — 1] + number of Divisors of i.
 » 15 months ago, # |   0 I never thought 6 months ago that I'll be able to even maintain a lower specialist. But alas my dream come true and If all my 4 solution passes, I'll be an expert.
•  » » 15 months ago, # ^ |   +22 My B failed (-_-)
•  » » » 15 months ago, # ^ |   +6 but congo on solving C and D :)
 » 15 months ago, # |   0 Solve C 10minutes, B 2hours and failed :(
 » 15 months ago, # |   0 Who manged to solve B??
 » 15 months ago, # |   0 How to solve C?
•  » » 15 months ago, # ^ |   0 Observe that foreach vertex it is allways optimal to use either l[i] or r[i], never some value in between.Root the tree somewhere, do a dfs. Result of the dfs is foreach vertex the max value we can get if we used l[i] or r[i] for that vertex.To find the two values for the current vertex, find the values for all adj vertex, then try both values and record the max value possible.
•  » » » 15 months ago, # ^ |   0 thanks
•  » » » 15 months ago, # ^ |   0 can u explain more?
•  » » » » 15 months ago, # ^ |   0 Can you give feedback in a way that I have sufficient information to write an answer fitting your needs?
 » 15 months ago, # |   +6 Just another day using java
 » 15 months ago, # |   +13 Very nice problems! Thank you for the contest!
 » 15 months ago, # |   0 At first, I tried some greedy solution of C, and it looks scary...Then I glanced at D, it looks scary too...So I waste about 1.5 hours trying to solve E...This story tells us that don't solve problems out of order if you're not sure you can solve all of them :(
 » 15 months ago, # |   +32 I decided to abandon python after this contest. Using python in codeforces is totally a disaster and will ruin your rating. Many problems, especially graph problems, like problem C in this contest, using python will cause you TLE, TLE, TLE...... while others languages can pass easily with same algorithm. It takes me 5 minutes to think of problem C, 15 minutes writing and compile, and an hour to submit, TLE, optimize my code, submit, TLE, optimize my code .....It's very very very frustrating to make tens of attempts but didn't pass, and see my current ranking drop from 300 to over 2000. Goodbye my rating, and goodbye python.
 » 15 months ago, # | ← Rev. 2 →   0 I am getting TLE in C. Time complexity of my code is O(2*(v+e)) but I facing TLE, please help me. 117248045Edited- This issued was solved, instead of cin, I used scanf. It's working properly now.
•  » » 15 months ago, # ^ |   0 Use map<> instead of unordered_map
•  » » » 15 months ago, # ^ |   0 still getting TLE
•  » » » » 15 months ago, # ^ |   0 Actually it's caused by read large amount of data by "cin", in other words, you get TLE because you spend too much time on I/O
•  » » » » » 15 months ago, # ^ |   0 It means I should use scanf instead of cin, right?
•  » » » » » » 15 months ago, # ^ |   0 Yes.
•  » » » » » » » 15 months ago, # ^ |   0 Thanks MonkeyKing, got AC
•  » » 15 months ago, # ^ | ← Rev. 2 →   -14 removed
•  » » » 15 months ago, # ^ |   +18 Not knowing C++ grammar very well, but: dfs(vector graph[],... is O(1), while: dfs(vector &graph[],... gives CE on my computer.
•  » » » » 15 months ago, # ^ |   0 You are right, arrays work like pointers, nothing is copied.So it might be undefined behaviour caused by negative value of parameter p which is used as array index.
•  » » » » 15 months ago, # ^ |   0 Can you help me to findout why I am getting TLE ?
•  » » » 15 months ago, # ^ |   -15 Great insight
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 deleted
•  » » 15 months ago, # ^ |   0 I hate it how cf will timeout even with the correct time complexity. I gave up the problem after 2 submissions knowing the time complexity is correct for my solution and I just need to define my variables globallyI gave a google interview and the interviewer asked me not to declare variables globally but pass it by reference
•  » » » 15 months ago, # ^ |   0 Defining your variables globally is not the issue; you TLE because your IO is too slow. Adding cin.tie(0)->sync_with_stdio(0); to your code gets AC (scanf/printf would probably also pass).
•  » » » » 15 months ago, # ^ |   0 https://codeforces.com/blog/entry/20225#comment-250378I am my own enemy ?P.S:- this solved the issue, thanks :)
•  » » » 15 months ago, # ^ |   0 Not sure what you intend to imply when you share about the google interview. In interviews, the constraints are different, even if you're able to solve a problem in optimal complexity, you might be asked to solve it using a different DS or less memory or anything else. Just cos you were asked to not use global variables doesn't mean it's a bad thing, the interviewer wanted to see if you can solve it without using global variables, that's it.
 » 15 months ago, # |   0 :( Can anyone show me some tips for solving A and B super fast?
•  » » 15 months ago, # ^ |   +6 observe observe observe.
 » 15 months ago, # |   0 I'm such an idiot. I solved div#2 C but was using int instead of long long. Thankfully it struck me just 10 minutes before the contest ended.And it wasn't the first time this happened to me. :(
•  » » 15 months ago, # ^ | ← Rev. 2 →   +1 define int long long gang
•  » » » 15 months ago, # ^ |   0 sometimes it will cost a TLE :)))
•  » » 15 months ago, # ^ |   0 Lol man, exactly what happened to me. First time I solved DP problem in a contest, first time I solved C in division 2. Lesson learned man, I changed my template to replace ints with long longs by default now. I do not want this to happen again, feels really bad
•  » » » 15 months ago, # ^ |   0 Lol same, first time dp, first time problem C!
•  » » 15 months ago, # ^ |   0 How to solve div2c I was able to solve only A and B
 » 15 months ago, # |   0 Solved div 2 B with ternary search .Can anyone explain a simpler solution for it..
•  » » 15 months ago, # ^ |   0 the simplest solution I found is take all -ve and all 0, then try to take as many +ve as possible
•  » » » 15 months ago, # ^ |   +9 You can take atmost one positive
•  » » 15 months ago, # ^ |   0 Simple solution is to take all the non-negative numbers. After that, it is pretty easy to observe that we can take almost one positive number. So start by finding the minimum difference in the non-negative elements already selected and try to pick a positive number greater than or equal to the minimum difference. I observed this after solving a few cases on paper.
 » 15 months ago, # |   0 How did people solve C div1? The solution boils down to running a DFS on the first graph, adding/removing vertices from the second graph and counting number of nodes from the second graph which currently have no descendants. What is the good data structure for this? I used some preorder segment tree with rollbacks, but there might be an easier solution...
•  » » 15 months ago, # ^ |   +10 I used a binary indexed tree to check if a given vertex has any marked descendants, and a link cut tree to find the deepest marked ancestor of a given vertex. 117214561
•  » » 15 months ago, # ^ |   +60 I used just a set. If you run a euler tour on the second tree and map each vertex to a segment, it's equivalent to finding the longest subsequence of vertices on the first tree such that none of their segments intersect, and the subsequence is part of a path from the root to some vertex in the first tree.Basically you store a set of all the segments that you take from the root to a parent of a vertex; when scanning the vertex in, check if a segment intersects it in the set. If it does, remove that (because it's never optimal to take a larger over smaller segment if both intersect, and if two segments intersect, one must completely overlap the other since it's from a euler tree). Then, add the segment belonging to the current vertex in the set. The answer is the maximum size of the set at any time.
•  » » 15 months ago, # ^ | ← Rev. 2 →   +3 The only data structure I used was a set. If you record the in and out times using DFS in the second tree, we have each node in the first tree is labeled with an interval $[in, out]$. We want to consider all intervals on a path from the root to a leaf, and try to find the largest set of nonintersecting intervals. But since the $[in, out]$ intervals either don't intersect or contain each other, we can simply use a set to do this. Submission
 » 15 months ago, # |   0 When is rating normally distributed?
 » 15 months ago, # | ← Rev. 2 →   +6 Is there a proof of correctness for Div2 problem C ?Considering the right or left value on each node will yield the maximum value.
•  » » 15 months ago, # ^ | ← Rev. 2 →   +5 Say you choose some value a such that l < a < r, and you've already chosen some value b for another node. If a ≥ b, then adding 1 to a will increase |a - b|. Otherwise, subtracting 1 will increase it. You can keep adding/subtracting until you get to l or r, and get a max value.
•  » » 15 months ago, # ^ |   +2 Consider $v[i]=l[i]+1$ to be a better solution than $v[i]=l[i]$ Then this is because there are more adj vertex with $v[adj]v[i]$If this is so, then $v[i]=max(l[i],r[i])=r[i]$ is true, by induction.
 » 15 months ago, # |   +3 I did not pass problem C because I used int instead of long long. Lesson learned. That would be the first time I solved problem C :(
 » 15 months ago, # |   +22 In problem D, when I used vectors for adj lists it TLEd and when I used 2D array for weights, it ACed. This was not fair T-T T-T. It costed me "Grandmaster" today.
•  » » 15 months ago, # ^ | ← Rev. 2 →   -15 I think vector is not as fast as array for n > 1e5 :)
 » 15 months ago, # | ← Rev. 2 →   -27 [Deleted]
 » 15 months ago, # | ← Rev. 9 →   +19 A non recommended approach for Div 2 problem $D$ Write bruteforce solution and generate first few terms of the sequence, here they are $1, 3, 6, 13, 25, 52, 102, 206, 411, 823,...$ As this can't be found on OEIS, make an observation that $dp(i) = 2 \times dp(i - 1) + c_i$ Search for sequence $c$ : $1, 0, 1, -1, 2, -2, 2, -1, 1,...$ which is A051950, so $c_i = \tau(i) - \tau(i - 1)$, where $\tau(i)$ is the number of divisors of $i$.
 » 15 months ago, # |   +12 AAAAaAAaaaAAaaaaa I didn't submit D1D because I fucked up one line of my dijkstra and an "i" was supposed to be a "j", and last round I FST'd because a "<=" was supposed to be a "<"why am I so cursed
 » 15 months ago, # |   0 Div 2 Problem B was not a great problem . It consumed all my time and just failed system test too :( .
 » 15 months ago, # |   +47 Feedback on the contest:A: Clean nice easy (and a bit standard) problem.B: I am not a fan of counting problems where there is fundamentally zero computer science involved.C: Cool problem. The two crucial observations (finding a polynomial solution, and then finding a pseudo-linear solution) where equally hard for me. The difficulty of the problem was really on the spot.D: Cool problem. The fact that, in the end, this is just Dijkstra is very nice.E: Once again, I am not a fan of counting problems where there is fundamentally zero computer science involved (I could not get AC during the contest, so maybe my solution is flawed and thus my comment does not make sense).Overall I really enjoyed taking part in the contest since the two problems C, D were cool! Thanks to the authors, nice contest!
•  » » 15 months ago, # ^ |   +10 C is a cool problem, but for me, D is just a very straight-forward problem as it is just a very simple shortest-path problem.
•  » » 15 months ago, # ^ |   +23 Nah, you are correct, E is just a counting problem where zero computer science is involved. Not sure if that is the case for F, but really, 3 counting problems in a single round?
•  » » » 15 months ago, # ^ |   0 thats fine, did you notice there were 4 graph problems and 3 of which were trees!
•  » » » » 15 months ago, # ^ |   0 Are you counting E as a graph problem? I wouldn't.C was a nice problem though :)
•  » » » 15 months ago, # ^ |   +10
•  » » » » 15 months ago, # ^ |   -10 anton round orz
 » 15 months ago, # |   +87 To not keep you waiting, the ratings updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!
•  » » 15 months ago, # ^ |   +1 Thanks !
•  » » 15 months ago, # ^ |   +1 thanks mike
•  » » 15 months ago, # ^ | ← Rev. 3 →   +1 thanks mike
•  » » 15 months ago, # ^ |   +3 Weak test cases on problem div2 B, solutions are getting Wrong answer on:13-2 0 3
•  » » » 15 months ago, # ^ |   0 MikeMirzayanov117231674 solutions like that one returns 3 instead of 2!!!!! please solve the issue
•  » » 15 months ago, # ^ |   0 Remove the cheaters from codeforces itself.
•  » » 15 months ago, # ^ |   +5 Come on! Let me become purple it's just a single point! :"( My curve does have limit in 1899!!!. Wish to become candidate for the first time after removing cheaters :)
•  » » » 15 months ago, # ^ |   0 wish to see you in red babe ツ
 » 15 months ago, # |   0 Can anyone please explain how the Problem D(DIV-2) boils down to just finding prefix sum of number of divisors?
•  » » 15 months ago, # ^ |