mohammedehab2002's blog

By mohammedehab2002, 14 months ago,

Hi everyone!

Codeforces round #649 will take place on Jun/13/2020 18:05 (Moscow time). It's rated for the second division, but, as usual, first division participants can take part out of competition.

The problems were created by me. I'd like to thank my forever orzable coordinator antontrygubO_o; my incredible army of testers dorijanlendvaj, 300iq, Osama_Alkhodairy, AmShZ, Discombobulated, TigranMec, _Aaryan_, Mohammad_Yasser, zoooma13, lavish315, Utkarsh.25dec, NOOBxCODER, and Laggy; and, of course, you-know-who for the amazing codeforces and polygon platforms.

This time, in an effort to kill type-races and because I'm lazy, you'll be given 5 problems and 2 hours to solve them.

UPD: the scoring distribution will be 750-1000-1500-2000-2500.

UPD: the editorial is out.

UPD: congratulations to the winners!

Div.1:-

Div.2:-

Good luck & Have fun :D

• +1165

 » 14 months ago, # |   +204 mohammedehab2002 and his xor.
•  » » 14 months ago, # ^ |   -37 This will be 4th problem :)
•  » » » 14 months ago, # ^ |   +17 all problems starting with xor1 xor2 xor3 xor4 xor5
•  » » 14 months ago, # ^ |   -40 XOR and Problem named as Ehab and ... :)
•  » » 14 months ago, # ^ |   -53 In my language, the Pronunciation of Xor means fever. That means "mohammedehab2002 and his fever".I hope today there will be something other than xor.
•  » » 14 months ago, # ^ |   -16 Unfortunately XOR was skipped this time from A B C D
 » 14 months ago, # |   +173 Incoming XOR missiles...
 » 14 months ago, # | ← Rev. 2 →   -154 damn
 » 14 months ago, # |   +365 *Codeforces Round #649 (Div. 2), writers: mohammedehab2002*
•  » » 14 months ago, # ^ | ← Rev. 2 →   +202 mohammedehab2002 be like....
 » 14 months ago, # | ← Rev. 2 →   +147 You-know-whoMaking Mike sound like Lord Voldemort
•  » » 14 months ago, # ^ |   +248 Who's that Mike? Lord Voldemort created codeforces and polygon and the 5 other horcruxes.
•  » » » 14 months ago, # ^ |   +59 You jinxed the round.
•  » » » 14 months ago, # ^ |   +460 *xorcruxes
•  » » » » 14 months ago, # ^ |   0 Xorz
•  » » » 14 months ago, # ^ |   +28 You said his name, and the Death Eaters are coming for you.
•  » » » » 14 months ago, # ^ |   +7 Xor Eaters Maybe xd
 » 14 months ago, # |   +276 Oh.. Thank you for thanking me for the amazing Codeforces and polygon platforms, almost forgot :P
 » 14 months ago, # |   +33 mohammedehab2002 and his short statements.
 » 14 months ago, # |   +291
•  » » 14 months ago, # ^ |   0 this was hella true
•  » » 14 months ago, # ^ |   0 Nailed it!
•  » » 14 months ago, # ^ |   0 now this meme makes a lot more sense.
•  » » 14 months ago, # ^ |   +30 Can't agree more, I solved problem A with seg Tree submission
•  » » » 14 months ago, # ^ |   +5 OMG, your code is so beautiful. Gonna keep this one :)
•  » » » » 14 months ago, # ^ |   +3 Thank you ^^
 » 14 months ago, # |   +37 Wait so what is up with the xor stuff? Sorry if I'm a noob and I don't know the jokes.
•  » » 14 months ago, # ^ |   +23 Check out the previous problems prepared by mohammedehab2002. You will see some interesting problems related to xor.
•  » » » 14 months ago, # ^ |   0 Alright, thanks for letting me know!
 » 14 months ago, # |   +184 A contest that has short statements is rarely found, so I advice you to register this contest :))
 » 14 months ago, # | ← Rev. 2 →   0 you-know-who for the amazing codeforcesSeems like there might be some XOR stuff along with Harry Potter
 » 14 months ago, # | ← Rev. 2 →   +15 Did you mean YouKn0wWho!
•  » » 14 months ago, # ^ |   -39 Mike may be <3
 » 14 months ago, # |   0 kill type-races and because I'm lazy, so contest is going to be a bit hard and tricky . I am excited for it .
•  » » 14 months ago, # ^ |   0 I don't think this killed too many type-races. ;)
 » 14 months ago, # | ← Rev. 2 →   +145 Spoiler Spoiler Spoiler Spoiler
•  » » 14 months ago, # ^ |   +36 Next problem names could be like=>A. Ehab and XOR problem(1) B. Ehab and XOR problem(2) C. Ehab and XOR problem(3) D. Ehab and XOR problem(4) E. Ehab and XOR problem(5):D:D:D
•  » » 14 months ago, # ^ |   +102 This time I hope to see the problem "Ehab goes to Rehab" xD xD
 » 14 months ago, # | ← Rev. 7 →   -52
 » 14 months ago, # | ← Rev. 2 →   -49 This is how my division 2 round with just 5 problems is like.... PROBLEM AWRONG ANSWER TEST CASE 2TIME LIMIT EXCEEDED TEST CASE 2WRONG ANSWER TEST CASE 2WRONG ANSWER TEST CASE 2WRONG ANSWER TEST CASE 2TIME LIMIT EXCEEDED TEST CASE 2...... and finally brain shutdowns...
•  » » 14 months ago, # ^ |   +11 SO MANY DOWNVOTES!!!! But unfortunately I ended ,the more or less same way......
 » 14 months ago, # | ← Rev. 6 →   -72
 » 14 months ago, # | ← Rev. 2 →   -35 Hope there is not unexpectedly high increase in difficulty from B to C :)
 » 14 months ago, # |   -42
 » 14 months ago, # |   0 If someone can give link for 5 problem div 2 contests it would be a great help
•  » » 14 months ago, # ^ | ← Rev. 7 →   +58
•  » » » 14 months ago, # ^ |   0 Thanx bro
•  » » » 14 months ago, # ^ |   +3 how did you find all these contests ?
•  » » 14 months ago, # ^ |   +9 You can use this website for such things.
•  » » » 14 months ago, # ^ |   0 thanks
 » 14 months ago, # | ← Rev. 2 →   -36
 » 14 months ago, # |   +27 mohammedehab2002 the XORcist
 » 14 months ago, # | ← Rev. 3 →   +12 Probable difficulty of problems-A-1200- mathB-1400- greedy or number theoryC-1700- constructive algorithms and treesD-1900/2000 — XOR, constructive algorithmsE-2100+ — Beyond my guess :P
 » 14 months ago, # | ← Rev. 2 →   +36 4 testers from IIT Kanpur :OProbably maximum this time
 » 14 months ago, # |   +40 After antontrygubO_o's comment on Ashishgup's blog.*Le mohammedehab2002 : My forever orzable coordinator antontrygubO_o :)
•  » » 14 months ago, # ^ |   +437 :((
 » 14 months ago, # | ← Rev. 2 →   -26 .
•  » » 14 months ago, # ^ |   0 This is why you shouldn't take python literally.
 » 14 months ago, # |   0 Is this rated for participants with ratings up to 2100, or only up to 1900? It seems to vary for Division 2 rounds.
•  » » 14 months ago, # ^ |   +32 2100Div. 2 only rounds are rated for participants <2100 while in parallel Div 1 and 2 rounds, the Div.2 round is rated for participants <1900.
•  » » » 14 months ago, # ^ |   0 What is the explanation for such kind of division?
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   +11 Well, most of people with rating 1900-2100 should be able to solve up to Div2 D (included) or even Div2 E for upper rating participants (like 2000-2100), so argument for puting them in Div.1 is: they don't need to solve first two or so problems, and can focus more on Div2 E and harder problems. They would on average lose maybe 15-20 minutes on average Div2 A+B, but that is the time that can make difference between not solving Div2 E (= Div1 C) and solving it. I think that argument for allowing them to participate on average Div2 is to make them do more practice: Div1 is really rare!
 » 14 months ago, # |   0 May be the shortest announcement of a div.2 ever
•  » » 14 months ago, # ^ |   0 Because, he thanked everyone in a single paragraph instead of making a list like most other authors.
 » 14 months ago, # | ← Rev. 2 →   0 Why people focusing a lot on XOR. Can someone explain me in detail. so may be it will helpful not only for me but for others too may be in tomorow contest.
•  » » 14 months ago, # ^ |   0 Look at his before contest..most of the time he presents some problem with XOR .
 » 14 months ago, # |   -6 I hope the problem statements will be as short as the announcement.
•  » » 14 months ago, # ^ |   +3 I think it will be (as he said he is lazy xd).
 » 14 months ago, # |   -36 13 testers for just 5 problems, Isn't it strange ?
 » 14 months ago, # | ← Rev. 2 →   -47 Edited-I posted on a different contest, I was asking for educational round.....Sorry!!
•  » » 14 months ago, # ^ |   +18 Not before the contest.
 » 14 months ago, # |   +25 I think this time mohammedehab2002 will give us surprise and there won't be any xor related problem :P
 » 14 months ago, # |   +31 Looking forward to this round, man!You know the deal, upsolving the problems 5 mins after the round ends: https://youtu.be/2jW2zTSoGCMGood luck and have fun!
•  » » 14 months ago, # ^ |   +3 Your videos are the best ! Keep up the good work.
 » 14 months ago, # |   -45 Hope Ehab saves us from the steep rating drop caused by AshishGup !!! HaHa...I know you're going to downvote the comment, Go ahead !!! XD !!!
 » 14 months ago, # |   +146 As a tester, I can confirm that the number of letters in problem B's statement is a 4-digit number and that the number of occurrences of the letter 'e' is a 3-digit number.
•  » » 14 months ago, # ^ |   +82 I hope its in base-2
•  » » 14 months ago, # ^ |   +17 you know the rule...no leading zeroes allowed
 » 14 months ago, # |   +25
•  » » 14 months ago, # ^ |   +85 You have 1 hour 56 minutes left.
•  » » » 14 months ago, # ^ |   +99 The last second of the minute
•  » » 14 months ago, # ^ |   0 Sad to see your meme skills degraded :(
•  » » » 14 months ago, # ^ |   +28 Sometimes the meme fails it's ok
•  » » » » 14 months ago, # ^ |   +2 Great, waiting for your comeback :)
•  » » » 14 months ago, # ^ |   +3 he needs warmup
•  » » 14 months ago, # ^ |   +13 I wonder why it took you 5 seconds to move your mouse pointer to the submit button.
•  » » » 14 months ago, # ^ |   +7 I sneezed
 » 14 months ago, # | ← Rev. 2 →   +39 5 problems ..
•  » » 14 months ago, # ^ | ← Rev. 2 →   +5 From the diagram given above you are surely gonna fall..... As you took a jump bit early...
 » 14 months ago, # |   +229
 » 14 months ago, # |   +1 I hope Problem names Will be greater than Problem statements as usual
 » 14 months ago, # |   +11 The first problem's score is $750$, So hard contest?
 » 14 months ago, # |   +49
 » 14 months ago, # | ← Rev. 2 →   -23 I guess Contest will be unrated if no xor problems will be given :)
 » 14 months ago, # |   -30 mohammedehab2002 be like :
 » 14 months ago, # |   0 Seems like today I can just solve upto B
 » 14 months ago, # | ← Rev. 2 →   -10 preparing myself to become pupil [EDIT: Why everyone downvoting me, it actually happened)
•  » » 14 months ago, # ^ |   +30 All the best. Hope you can achieve it XD
•  » » 14 months ago, # ^ |   -9 Finally you achieved that with your hard work.
•  » » 14 months ago, # ^ |   0 you can always predict low rating and achieve that...
 » 14 months ago, # | ← Rev. 3 →   +5 First time seeing an announcement without explicitly naming Mike hah
 » 14 months ago, # |   +106
•  » » 14 months ago, # ^ |   0 Can you please provide link to his blog? It would be really helpful to learn from his blog.
•  » » » 14 months ago, # ^ |   +3
•  » » » » 14 months ago, # ^ |   0 Thank you
 » 14 months ago, # |   +63 mohammedehab2002 I think you should mention the unusual start time. I have opened the blog almost 3-4 times since yesterday but noticed the start time just now when told by a friend.
•  » » 14 months ago, # ^ |   -27 It is starting at the same time as LeetCode BiWeekly :(
 » 14 months ago, # | ← Rev. 2 →   -15 Unusual time contests are disaster. ps: Mat maan maa chuda
 » 14 months ago, # |   +1 mohammedehab2002 I never try his competition but when I saw comments, it seems like he will give questions in which xor will be used.
 » 14 months ago, # |   0
 » 14 months ago, # | ← Rev. 2 →   -62 mohammedehab2002 unfortunately, we can't participate in the leetcode and codeforces contests at the same time. the thing I want to say is most people will choose codeforces because it's lot big platform than leetcode. but newbies like me can gain high points by attending both the biweekly and weekly challanges of the same week. it could have been earlier or after the other contest.
•  » » 14 months ago, # ^ |   +82 who the hell chooses leetcode over codeforces!!
•  » » » 14 months ago, # ^ |   0 but i would rather participate in both of them
 » 14 months ago, # | ← Rev. 2 →   0 A significantly low number of registrations compared to previous rounds. Probably because of the score distribution. Or maybe because of the start time.
 » 14 months ago, # |   0 Good luck to everyone!
 » 14 months ago, # |   +133 Problem D is almost exactly the same as 1325F - Ehab's Last Theorem ？Isn't it ？
•  » » 14 months ago, # ^ |   +8 Agreed
•  » » 14 months ago, # ^ |   0 recycled
•  » » 14 months ago, # ^ |   0 I think they must be different.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +31 You probably should have commented this after the contest ended, not when it was going on.But yeah, knowing that problem exists (even if you haven't solved it) is a massive help even though the condition here is much easier than it that case. If you can figure out the property using the size of the smallest circle, it can be solved in a similar manner to that problem.
•  » » » 14 months ago, # ^ |   +9 Yes, it is true. I was not thoughtful sorry!
•  » » » 14 months ago, # ^ |   +33 Not only a massive help, it kills the problem. I copied my solution to that F and changed like 4 lines.
•  » » 14 months ago, # ^ |   +11 and they have the same author?? but why?
•  » » 14 months ago, # ^ |   0 that why i could not solve it.
•  » » 14 months ago, # ^ |   +9 Yes it is.
 » 14 months ago, # | ← Rev. 2 →   -21 .
•  » » 14 months ago, # ^ |   +28 No Similarities Brother
 » 14 months ago, # |   0 Thanks! I enjoy doing it today
 » 14 months ago, # |   +3 How did you solve C?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +1 Constructive algorithm , Find a set of elements which are not present in the given array, sort these set of elements , Now Answer exists only when given array is sorted and there exist no such position i in array such that a[i]>i.After doing these things lets say ans is our ans array Move on in the array till a[i]==a[i-1] and pop out elements from the given setand push in answer arrayand when you reach a[i]!=a[i-1] push a[i-1] into the answer array and repeat this till you reach the end of the array.
•  » » » 14 months ago, # ^ |   +1 Thanks
•  » » 14 months ago, # ^ |   0 For problem C I feel it was difficult to come up with such constructionI did not observe that for $a_i {!=} a_{i-1}$ ans is b[i] = a[i-1] What I did : A maintained list of numbers that are exactly between any two different $a_i$'s. So that I can pick one by one element from list wherever I need them. Maintained missing number or mex, after inserting $b_{i-1}$. If my missing number is less than $a_i$ then fill b[i] = missing_number and check next missing number is a[i] or not, cause now updated missing_num should be a[i] for it to be mex. If my missing_number = a[i] then that's it, we have already done our job now you can use this chance you take elements greater than $a_i$ i.e we have maintained the separate list for this purpose (step 1) My submission :83684656
 » 14 months ago, # | ← Rev. 2 →   +5 I cannot implement D but is this approach fine:Find any minimal cycle in $G$. If its length is $\le k$ then we are done. If its length is greater than $k$ and say it is $L$ then we can split this minimal cycle into 2 set of $\lfloor\frac{L}{2}\rfloor$ vertices such that the set are bipartite. Then choose $\lceil\frac{k}{2}\rceil$.This may be wrong but I was not able to find minimal cycle (cannot implement)
•  » » 14 months ago, # ^ |   0 I thought of the same thing, but couldn't think of a way to find the minimal cycle in O(n)
•  » » » 14 months ago, # ^ |   0 There is actually no known way to find the smallest cycle in O(n). The idea is that you can start looking for a cycle, and if you move k-1 away without finding one, then at that point you can just put independent vertices alternating on the length k path you found.
•  » » » » 14 months ago, # ^ |   +8 thank you i was a bit confused with the solutions.
•  » » 14 months ago, # ^ | ← Rev. 3 →   +9 Yup, thats the basic idea.There is also the case of there being no cycle, but then its just the task of forming a bipartite set out of the tree which is trivial.As for how to implement it, take a look at DFS Tree, I think it should be pretty intuitive after that. Idea if you are still stuckThe difference of heights between the current node and any node connected by a back edge implies a cycle of size difference of heights + 1OR just read his editorial for a problem of a similar premise (problem F)
•  » » 14 months ago, # ^ |   0 I solved D after the contest, I used same approach, additionally if we can not find a cycle in the graph, then the graph is a bipartite, then we can simply choose and print the set with atleast ⌈k/2⌉ nodes. 83694575
 » 14 months ago, # |   0 How to solve E?
•  » » 14 months ago, # ^ |   +1 you soved a,b,c,d with only one submisiion, I feel really sad that you could not solve e
•  » » » 14 months ago, # ^ |   0 He is master in doing these things :p
 » 14 months ago, # |   +3 How to solve E? I managed to get AC by using random + some optimizations
•  » » 14 months ago, # ^ |   0 How?
•  » » » 14 months ago, # ^ |   0 First of all you should find 0. Keep a candidate array where 0 could be. Then go through this array multiple times until 1 candidate remains. For each candidate pick 2 elements B and C randomly. Let's denote this candidate value by A. Then check if (A | B) & (B | C) = (A | B), if not then A is not a valid candidate. To get less than 4269 queries use some previous queries and also don't query the same pair of elements twice.
•  » » » » 14 months ago, # ^ |   0 I had the same idea but did not searched randomly and could not fit into the limit.
•  » » 14 months ago, # ^ |   0 Couldn't get AC, I tried to find an element by applying 170 random queries and use this element to find the 0 element. Can anyone please help me find out why this was wrong.
•  » » » 14 months ago, # ^ |   0 I thought if I apply a alot of queries to one number, there would be at least one number with bit 0 for every bit positions.
 » 14 months ago, # | ← Rev. 2 →   0 Did somebody please Help why I am getting WA on test 2 of problem A , I used Binary Search and Segment tree 83678283Edit : Wrong Logic
 » 14 months ago, # |   +3 How to solve D?
 » 14 months ago, # |   +10 What is test 25 in problem D?
•  » » 14 months ago, # ^ |   +10 I think it is a tree with an independent set of size > K/2.
•  » » » 14 months ago, # ^ |   +8 Thanks, that was my issue!
•  » » » 14 months ago, # ^ |   0 Just curious, how did you arrive at that conclusion?
•  » » » » 14 months ago, # ^ |   +11 I also failed on this testcase and had the same error.
 » 14 months ago, # |   +2 Swap (A, B) O.o
 » 14 months ago, # | ← Rev. 4 →   -11 In Problem C, earlier I wrote a code which might generate equal elements in array b but kept getting WA on test 4. After that the only change I made was make the elements distint and it passed the pretests. Any idea why ? Link to submissions : 83672136 83682310
•  » » 14 months ago, # ^ |   +10 They don't have to be unique. My code which may generate duplicate values passed pretests
•  » » » 14 months ago, # ^ |   0 And the problem is still solvable even if the elements have to be unique. For any value of b that is duplicated previously, just set it to a value that hasn't been used before which is greater than $10^5$.
•  » » 14 months ago, # ^ |   0 Elements of b not necessarily unique. For example sample 2.
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 Elements in b need not be unique. I had the same doubt and asked the question and they said it can repeat
 » 14 months ago, # |   +5 Am I the only one who doesn't know how to read and ignored the fact that Subarray was written & explained on problem A?
•  » » 14 months ago, # ^ |   +3 No I am with you :P
•  » » » 14 months ago, # ^ |   +6 LOL, I figured it out 4 min to the end, coded it wrong, and got accepted at 1:59:59 SMH
•  » » » » 14 months ago, # ^ |   0 Happens sometimes. How did you solve C?
•  » » » » » 14 months ago, # ^ |   +1 To solve C i used an Set. For each integer from 0 to mx, where mx is the maximum value of the array, I include them into the set. Then, for some extra values, like n+2, I added them too. So, let ans be the array representing the answer and vet the given array. If vet[i]!=vet[i-1], I said that ans[i] = vet[i-1]. Then, I erase vet[i-1] from the set. Then, all the other ans are -1, which means we dont know it yet. If we loop from all the positions, if ans == -1, we add the first not used element from the set, thus, giving us a valid answer!
•  » » » » » » 14 months ago, # ^ |   0 Cool. Thanks
•  » » 14 months ago, # ^ |   0 I tried to use kadane's algorithm with a tweak but didn't work. Any corner case? Or is it that first we need to calculate the whole sum and simulate what the problem definition demands i.e. taking out elements from left and right?
•  » » 14 months ago, # ^ |   0 Me too lol
 » 14 months ago, # |   -63 Worst Contest Ever
 » 14 months ago, # |   +11 Was that the most difficult div2 A problem, ever? or did I miss something?
•  » » 14 months ago, # ^ |   0 Cannot agree more to you!
•  » » » 14 months ago, # ^ |   0 What's worse is my wrong solution passes A. Whole contest I kept trying to fix it cause I knew it was wrong. And it passed ST wtf. It will fail for this. 1 5 2 2 3 1 2 1
•  » » » » 14 months ago, # ^ |   0 uphacked
•  » » » 14 months ago, # ^ |   0 thats true
 » 14 months ago, # | ← Rev. 2 →   +1 Is there any case for problem C for which output is -1? I don't find any case like that.
•  » » 14 months ago, # ^ |   -8 Yes, if the array a is not sorted, it is -1.
•  » » » 14 months ago, # ^ |   +14 The question specifies that the array a is always sorted.
•  » » » » 14 months ago, # ^ |   0 Oh, sorry, so I don't think there is a case.
•  » » » » » 14 months ago, # ^ |   0 If a[0] != 0 and a[0] != 1, then it will be -1.
•  » » » » » » 14 months ago, # ^ |   0 This too cannot happen according to the case ai ≤ ai+1
•  » » » » » » 14 months ago, # ^ | ← Rev. 2 →   0 2 1 2
•  » » » » » » 14 months ago, # ^ | ← Rev. 2 →   +9 Again, the question specifies 0<=a[i]<=i. So a[1] will always be either 0 or 1.
•  » » » » » » » 14 months ago, # ^ |   0 Right, my bad.
•  » » » » » » 14 months ago, # ^ |   0 But constraint says 0<=a[i]<=i So a[1] can't be 2.
•  » » 14 months ago, # ^ | ← Rev. 2 →   -8 0 0 1 1
•  » » » 14 months ago, # ^ |   +3 That doesn't work. One output would be 2 2 0 0
•  » » » 14 months ago, # ^ | ← Rev. 2 →   -6 Another example is0 1 2 3 4 5
•  » » » » 14 months ago, # ^ |   +1 that will be6 0 1 2 3 4
•  » » » » » 14 months ago, # ^ |   0 Ok, understood. Thanks
•  » » 14 months ago, # ^ |   0 I don't think there is a case for problem C with output -1, although I did include it in my code just to be sure.
 » 14 months ago, # |   +3 Jesus christ it took me 1 hour 54 minutes to solve A but <1 hour to get B and C :\I'm about to get screwed by delta change
•  » » 14 months ago, # ^ |   0 Can you explain how to solve A.
•  » » » 14 months ago, # ^ |   0 Basically if sum of all elements is non-zero mod x, return n.If all the elements are 0 mod x, return -1.Otherwise, return max(n-f-1, l-1), where f is the index of the first non-zero element, and l is the index of the last non-zero element.
 » 14 months ago, # | ← Rev. 2 →   -9 Interesting problems, as usual (excellent/brief descriptions!), but that was a tough problem A...It feels like Div 2 contests are getting a lot harder in general. This comment/meme was so accurate
•  » » 14 months ago, # ^ |   +12 "Div2 Contests are getting a lot harder in general" ?WTF? These days I feel they are a lot easier than before. Problem E in last 5-6 contests was easy (Except this one ofc).
•  » » » 14 months ago, # ^ |   -10 Well, perspective I suppose. I've been taking a beating so it definitely feels tough to me. Did you find today's problems easier than usual?
•  » » » » 14 months ago, # ^ |   0 Nope. I literally wrote "except this one in parenthesis". Today's E was nice.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +17 easy $\neq$ easierAlso, of course E is going to be easier the more problems there are and recently div2s have more problems than before.
•  » » » » 14 months ago, # ^ |   0 Yeah ik. I am talking about normal 6 problem rounds. I feel Es are easier than they used to be. 5 problem rounds' E is obviously much tougher to 6 problem rounds in general
•  » » » » » 14 months ago, # ^ |   +13 I'm not really sure about that, it might be related to the fact that you are better now than when you were solving old Es.
•  » » 14 months ago, # ^ |   0 I guess I've been downvoted quite a bit for these couple of comments. Not entirely sure why, since I was just sharing an opinion, but thought I'd provide some background to anyone who cares to read : The percentage of people who submitted any problems (relative to the total registered users) in the last contest seemed to be a lot smaller than the past few contests. Problem A was a lot harder than it usually is (the number of submissions, even after 20-25 minutes, was low). I am generally able to get A in quickly, so having 1 failed solution and then taking another 20 minutes was a major downer. Obviously, in retrospect, things look a little easier. Towards the end of the contest, CF Predictor showed a net loss of -36 points in my rating, so it was frustrating to see that even after getting 3 problems in during a Div 2 round with 5 problems (though at the time I wasn't sure that they would all pass). Eventually, my rating went up slightly, so that prediction turned out to be incorrect. Anyway, perhaps a nice feature to have on Codeforces would be a poll option. This way, we could get near real-time feedback from the community.
 » 14 months ago, # |   +3 Even til the end of the contest didn't I konw why my binary search for A WA on test 2....DIV3 I'm coming :)
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 same with me I tried segtree and BS but kept getting WA over 4 times is some problem with the approach ??
•  » » » 14 months ago, # ^ |   -6 I'm waiting for the case 2 open... It's 1 am now in China... I want to figure it out why BS wa on test 2 before go to sleep.
•  » » » » 14 months ago, # ^ |   0 5 3 1 1 1 1 1 Simulate your binary search on this testcase.
•  » » » » » 14 months ago, # ^ |   0 it gives 5 which a/c to me is correct
•  » » » » 14 months ago, # ^ |   0 If you look carefully at Test 2, last input: 8 2 0 1 0 1 0 1 0 1 binary search will start searching for a good subarray of length 8 then 4 then 2, all of which do not exist. After that it will search for 3, which will be the maximum length according to BS. So it will return 3.
•  » » » 14 months ago, # ^ |   +31 You tried segtree and bs to solve a div2A? :|
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   +16 I had done some similar problems recently involving similar ideas and after misinterpreting what "subarray" meant I thought that was the best way to go !!! XD Moreover I just had to edit the code slightly to adjust the problem rather than creating one from scratch
•  » » 14 months ago, # ^ |   +4 In the case of Binary Search, when you don't find a solution for a particular size, you reduce the size(range). There may be the case that there exists a size of the subarray that is greater than current size you checked. Hence wrong logic.
•  » » » 14 months ago, # ^ |   0 Now I got it...Just for the first sight thought it must be a BS problem, when I konw why it isn't, so happy with me. The whole 2 hours of confusion is now gone away. Though ratings down, get knowledge :) , seems we need to check it out if it can use BS then only one side of mid is acceptable. In A, if we choose mid==2 then mid==1 and mid==3 are both acceptable but BS only go one way so it is wrong.Never consider it before...
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   0 Well I never knew what the definition of "subarray" meant for this contest until the contest ended :(
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 I thought to use bs too. Luckily passed all tests: 83624037Hack test: Spoiler1 6 3 1 2 1 2 1 2 
•  » » » 14 months ago, # ^ |   0 LOL, lucky you. My BS just got wa 2. Seems the way we write BS is different.
 » 14 months ago, # |   -61 I want a quick editorIAL NOW !!!!!!.
•  » » 14 months ago, # ^ |   -58 upvote this please
•  » » » 14 months ago, # ^ |   -31 cheers to those mfuckers who downvoted my post !!
•  » » 14 months ago, # ^ |   0 For your comment ,, author posted the editorial so quickly . xD
 » 14 months ago, # |   +49 https://codeforces.com/contest/1325/problem/FThe Problem D today was VERY SIMILAR to this problem. It gives many participants unfair advantage. Please look into this. mohammedehab2002
•  » » 14 months ago, # ^ |   +19 The solution to today's question can be obtained by a simple modification to the code given in the editorial of this problem.
•  » » » 14 months ago, # ^ |   0 Yes I agree. This problem gives an unfair advantage to those who have not read that problem.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 I also tried to remember that this type of similar problem I had seen before somewhere else :|. Anyway, I enjoyed the problem. My favourite one of today's problem set <3 .
•  » » 14 months ago, # ^ |   -11 Well, the idea is pretty standard anyway
•  » » » 14 months ago, # ^ |   +12 Yes, I agree in principle that the idea is standard and every question will use ideas which are known to people. But I also believe that there should be some threshold of originality in the questions so that it does not give people who have seen the questions previously to simply copy the code and make slight modifications to achieve the solution. It gives them unfair advantage by saving them a lot of implementation time. Also I don't think it was a very straightforward problem for people in my rating range as only 346 people could solve it. :(Other than that, the questions were really good and I enjoyed solving them :)
•  » » » » 14 months ago, # ^ |   +23 Agree, the most uncomfortable is that it was the same problemsetter.because I'm lazy, you'll be given 5 problemsThis does not look like a joke anymore!
•  » » » » 14 months ago, # ^ |   0 i agree with your reason. when i come to E problem, i think that this problem is like already solved problem.. And After i read your comments, i realized my thought is correct
 » 14 months ago, # |   +6 Problem A was tricky (for some) when it comes to the definition of subarray. I overlooked it and it took me 3 WAs to find out what was wrong...
•  » » 14 months ago, # ^ |   +2 yep and it took me 1 WA, not paying attention to the word "subarray" and solving it for "subsequence".
•  » » » 14 months ago, # ^ |   +1 Me too, when I saw what it meant I facepalmed
•  » » 14 months ago, # ^ | ← Rev. 3 →   +1 Can you Please tell if I misinterpreted the definition of the subarray here , otherwise my soln seems fine 83678283Edit : I did :(
•  » » » 14 months ago, # ^ |   0 If there is an array $A$ with elements $a_1, a_2, ..., a_n$, then a subarray of $A$ is an array with only all the elements between $l$ and $r$, where $1<=l<=r<=n$, i.e. it has elements $a_l,a_{l+1},...,a_r$. On a side note, binary search + segment tree for div2 A is totally unnecessary...
•  » » » 14 months ago, # ^ |   +1 Why you are using binary search in segment tree? I think you will miss many cases with this. From your solution,i can infer that the length of subarray is independent of values of array, whereas it is dependent. My solution - SpoilerIf total sum % x != 0, answer is n. Else two cases- 1.if there exist an element not divisible by x then choose greedily such first or last element(and remove all elements before it( or after it if u wanna remove the last element not divisible by x)including that) and maximize the length. 2.no such element present, output -1.Sorry for my bad English.
•  » » » 14 months ago, # ^ |   +1 The case that your solution failed one was ~~~~~ 1 4 7 ~~~~~So you definition of subarray is not what caused your code to give WA. Based on your code, I think your definition is correct.
•  » » 14 months ago, # ^ |   0 True, lesson learned — read twice code once. it was tough to see what the question meant once i was sure answer would be n or n-1 or -1.
•  » » » 14 months ago, # ^ |   +1 me too :/
 » 14 months ago, # |   +108 mohammedehab2002 and Testers after the contest.
•  » » 14 months ago, # ^ |   +52 When I could'nt solve A even after 15 min had passed..Me thinking : "Is subarray size related to Xor of elements?" :facepalm:
 » 14 months ago, # | ← Rev. 2 →   -44 What a terrible contest: why the hell is the gradient so high between C and D? It should have been at-most 2000 rated but this D is sure to be >=2200.And to top it off, D was knowledge-based (DFS Tree) and implementation heavy. Such an underwhelming speedforces contest :|
 » 14 months ago, # |   +33
 » 14 months ago, # |   +2 Erm weaktestcases for D? I just commented my assert and it got AC. Please uphack this.Solution
•  » » 14 months ago, # ^ |   +3 Hey, you're not alone. How can I pass the problem D?
 » 14 months ago, # |   0 Why the weak pretests? :((((
 » 14 months ago, # |   -8 -1 is not possible for Problem C There have no any case in the testing input. How funny!!!!!
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 He is right..Then i don't understand why people down-voting. Cause,, A is sorted and Ai <= i, the answer will always exist.
 » 14 months ago, # |   -28 Weak Test Cases of Problem CFollowing solution fails for very basic test case 2 0 2 (Why No test case exists for -1 answer in main test cases ) 83678632 1364C - Ehab and Prefix MEXs Solution
•  » » 14 months ago, # ^ |   +12 Read the constraints properly. It says Ai<=i
•  » » » 14 months ago, # ^ |   +4 Thank you for clarifying
•  » » 14 months ago, # ^ |   0 If you mean20 2Then output is 1 0And if you mean32 0 2Then input is not valid. Since a[i] sorted in nondecreasing order and 0<=a[i]<=i. With this constraint there exist no such case for which output is -1 so that you can't find such case in testcases.
 » 14 months ago, # |   0 For question D, Could anyone please tell me, what am i missing ? 83685667
•  » » 14 months ago, # ^ |   -8 I think you should add depth[x] — depth[y] + 1 >= 3 in your dfs
•  » » » 14 months ago, # ^ |   0 Sorry, But I retried its not the case. I guess it has issues when there is no cycle.
•  » » 14 months ago, # ^ |   +5 Try this test: 3 2 3 1 2 1 3The answer should be: 1 2 3 But your code gives the output: 1 1
•  » » » 14 months ago, # ^ |   0 Thank you so much, I get it
•  » » » » 14 months ago, # ^ |   0 What was the problem? Something wrong with coloring?
•  » » » » » 14 months ago, # ^ |   0 In case of a star graph, I considered only one case, so I was failing.
•  » » » » » » 14 months ago, # ^ | ← Rev. 2 →   0 you mean, when you colored vertexes, you considered only black(white) ones?
 » 14 months ago, # |   0 For D I did this: First, considered the case separately if the given graph was a tree, by building the bipartite graph. Otherwise, find any cycle in the graph and recursively check while the length of the cycle is greater than k, check for any edge within the cycle breaking the cycle into two and solving again for these two cycles. And if there's no edge within a cycle and size is greater than k, print the independent set.I guess this should give TLE for some test, could anyone try to uphack it? 83682515
 » 14 months ago, # |   0 Hi, I am a newbie in this platform, I am a little bit good with converting logic into code but i can't even understand the logic behind the problem A. I think I should need to learn a lot of things. can anyone suggests tops I should need to cover? to solve all problems. Some best resources or video lectures would be helpful.Thanks in advance!!!!!!!!!
•  » » 14 months ago, # ^ |   0 Do a lot of practice starting from the level just above you. Go to problem-set and sort it in decreasing number of submissions and start solving. Don't invest more than 20 mins on a question. Later do check out its editorial to find out the algorithms which you are missing in your knowledge bank.
 » 14 months ago, # | ← Rev. 2 →   0 In Problem D,-> First I checked if problem 2 can be solved. If it can be then print the result -> Otherwise, for 1st problem, if I run a DFS from 1 and construct two set where 1st set contains vertices that has nodes that has even depth and 2nd set contains nodes that has odd depth. Then, isn't it possible to choose ceil(k/2) independent vertices from either set 1 or set 2. I got WA on testcase 49. My intuition was, those chosen ceil(k/2) would form an independent set. If they are not then, there will be a cycle which has length <= k. Can anyone help me understand why I got WA.
•  » » 14 months ago, # ^ |   0 I have the same solution and it works: https://codeforces.com/contest/1364/submission/83784311You like have a bug.
 » 14 months ago, # |   +18 For everyone saying this D and last F are the too similar. Well, it can't be true that both me and antontrygubO_o have been drunk since my last round to not notice if they aren't different enough. Yes, they have very similar statements, but they have very different solutions, which is obviously the case since one of them are about SHORT cycles and the other is about LONG ones. I mean, are "find the shortest cycle" and "find the longest cycle" similar problems? One is simple $O(n^2)$ bfs and one is NP-hard.Please, read the solutions for both problems before you judge.Today's D:The common idea is: if the graph is a tree, you can easily find an independent set with size $\lceil\frac{n}{2}\rceil$ by bicoloring the vertices and taking the vertices from the more frequent color. Otherwise, the graph is cyclic. Let's get a cycle that doesn't have any edges "cutting through it." In other words, it doesn't have any pair of non-adjacent vertices connected by an edge. If its length is at most $k$, print it. Otherwise, take every other vertex (take a vertex and leave a vertex) and you'll end up with a big enough independent set. How to find such cycle?Let's do a dfs in our graph. In the very first time we hit a node that has a back-edge, we take the back-edge that goes to the deepest possible node to close our cycle. This cycle can't have any edges crossing it because none of our node's ancestors has a back-edge (by definition.)Last round's F:Let $sq$ denote $\lceil\sqrt{n}\rceil$.Let's take the DFS tree of our graph. Assume you're currently in node $u$ in the DFS. If $u$ has $sq-1$ or more back-edges, look at the one that connects $u$ to its furthest ancestor. It forms a cycle of length at least $sq$. If $u$ doesn't have that many back-edges, you can add it to the independent set (if none of its neighbors was added.) That way, if you don't find a cycle, every node only blocks at most $sq-1$ other nodes, the ones connected to it by a back-edge, so you'll find an independent set!For people saying they copied the solution and changed something and got AC, I'm assuming you have a reasoning for why your solutions work. If you can give a proof (longest cycle)*(maximum independent set)>=(number of vertices), and use the same or similar proof to prove 2*(maximum independent set)>=(shortest cycle) please give me that proof because I'm interested to hear it.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +73 Ok so compare this and this. I just made changes at few places. And yeah, still analyzing the old submission.
•  » » » 14 months ago, # ^ |   0 wow
•  » » 14 months ago, # ^ |   0 we still love your questions.
•  » » 14 months ago, # ^ |   +31 I have just copied the code from last editorial of F and changed just: -> sq to k -> >= to <= and it got accepted. why you not also copied the other question. This was the wrost round I ever given.
•  » » » 14 months ago, # ^ |   +19 ya.. i have also done the same 83691648
•  » » 14 months ago, # ^ |   +3 This code and this code are exactly same, I just changed less than equal to greater than equal. And got AC in both.
•  » » 14 months ago, # ^ |   0 Even the statements were so similar in both the problems, the least you could have done is change the statements so that on googling it would have not linked to the older problem. How lazy and overconfident does one have to be to not do this
 » 14 months ago, # | ← Rev. 2 →   0 Could somebody point out the mistake in this logic for D : Go to every back-edge (u,v) and find the distance b/w u and v in the dfs tree, if the distance is < k then we just found a cycle. If no back-edge satisfies this condition then select the independent set by dividing the graph into bipartite sets.
 » 14 months ago, # | ← Rev. 2 →   0 Can someone look at this(Problem C) 83665936. Got Wrong at TC25
•  » » 14 months ago, # ^ |   0 As elements of array b must be less than or equal to 1000000 as said in constriants.
 » 14 months ago, # |   +61 MikeMirzayanov my rating got increased even though I should be out of competition.
•  » » 14 months ago, # ^ |   +20 You probably registered for this contest while you were a Candidate Master.
 » 14 months ago, # |   -9 solution of problem C
 » 14 months ago, # |   -8 I couldn't find anything about xor in the first 2 question.
 » 14 months ago, # |   0 Hey, I have given the correct solution for the first question, but it shows an error on test 2 and when I resubmit the same code. It accepts the solution.
•  » » 14 months ago, # ^ |   0 The system does not accept resubmitting unchanged code.
•  » » » 14 months ago, # ^ |   0 See submission 83638170 and 83694208. Both has exact same code.
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   +6 You code is buggy, vector "dp" should have size x and not n. Both solutions are buggy and same. Both should have received RTE ideally. But, c++ is not very strict about index out of bound and hence your solution is passing probably.
•  » » » » » 14 months ago, # ^ |   0 got it thanks
 » 14 months ago, # |   +25 suta was first division participants before this contest, but his rating is changed.bug?
 » 14 months ago, # |   -34 Why weak pretests in Problem C? System Testing did not cover the case where the solution is -1. :(
•  » » 14 months ago, # ^ |   +11 There is no solution with the given constraints where the answer can be -1. Since A is sorted and Ai <= i, the answer will always exist.
•  » » 14 months ago, # ^ |   0 Do you have any testcase under given constraint for which output is -1? If you have any, let us know. Everyone along with author will be happy to see that.
 » 14 months ago, # |   -24 https://codeforces.com/contest/1325/problem/FThe Problem D today was VERY SIMILAR to this problem. It gives many participants unfair advantage.
•  » » 14 months ago, # ^ |   -29
•  » » 14 months ago, # ^ |   +19 Though I didn't solve it, but you can say similar thing for almost every problem. Just bring any red coder and he will point out a similar problem to every problem of this round.
 » 14 months ago, # |   -32 Upvote this to get AC in 4 questions only in your next contest. T_T
 » 14 months ago, # |   +1 I want to share one thing about problem 1364D - Ehab's Last Corollary, Today I submitted code and my code 83718270 was accepted. But Later I found that it is giving me wrong answer for below testcase. Testcase:8 9 3 8 1 8 7 8 6 7 2 2 4 2 5 4 5 5 3 4 3 Output:1 4 5 which is wrong because there is an edge between 4 and 5.
 » 14 months ago, # |   0 problem B wasn't python friendly.
 » 14 months ago, # |   -24 verry bad!