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, taran_1407, TigranMec, _Aaryan_, Mohammad_Yasser, zoooma13, lavish315, Utkarsh.25dec, far_from_NOOB, 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
mohammedehab2002 and his xor.
This will be 4th problem :)
all problems starting with xor1 xor2 xor3 xor4 xor5
XOR and Problem named as Ehab and ... :)
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.
Unfortunately XOR was skipped this time from A B C D
Incoming XOR missiles...
*Codeforces Round #649 (Div. 2), writers: mohammedehab2002*
mohammedehab2002 be like....
You-know-who
Making Mike sound like Lord Voldemort
Who's that Mike? Lord Voldemort created codeforces and polygon and the 5 other horcruxes.
You jinxed the round.
*xorcruxes
Xorz
You said his name, and the Death Eaters are coming for you.
Xor Eaters Maybe xd
Oh.. Thank you for thanking me for the amazing Codeforces and polygon platforms, almost forgot :P
mohammedehab2002 and his short statements.
this was hella true
Nailed it!
Can't agree more, I solved problem A with seg Tree submission
OMG, your code is so beautiful. Gonna keep this one :)
Thank you ^^
Wait so what is up with the xor stuff? Sorry if I'm a noob and I don't know the jokes.
Check out the previous problems prepared by mohammedehab2002. You will see some interesting problems related to xor.
Alright, thanks for letting me know!
A contest that has short statements is rarely found, so I advice you to register this contest :))
Did you mean YouKn0wWho!
Mike may be <3
kill type-races and because I'm lazy, so contest is going to be a bit hard and tricky . I am excited for it .
I don't think this killed too many type-races. ;)
post a pic
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
This time I hope to see the problem "Ehab goes to Rehab" xD xD
This is how my division 2 round with just 5 problems is like....
WRONG ANSWER TEST CASE 2
TIME LIMIT EXCEEDED TEST CASE 2
WRONG ANSWER TEST CASE 2
WRONG ANSWER TEST CASE 2
WRONG ANSWER TEST CASE 2
TIME LIMIT EXCEEDED TEST CASE 2......
and finally brain shutdowns...
SO MANY DOWNVOTES!!!! But unfortunately I ended ,the more or less same way......
Hope there is not unexpectedly high increase in difficulty from B to C :)
If someone can give link for 5 problem div 2 contests it would be a great help
Hope this helps :)
https://codeforces.net/contest/1169 https://codeforces.net/contest/1150 https://codeforces.net/contest/1136 https://codeforces.net/contest/1111 https://codeforces.net/contest/1104 https://codeforces.net/contest/1105 https://codeforces.net/contest/1059 https://codeforces.net/contest/1047 https://codeforces.net/contest/1040 https://codeforces.net/contest/1020 https://codeforces.net/contest/1008 https://codeforces.net/contest/998 https://codeforces.net/contest/992 https://codeforces.net/contest/989
Thanx bro
how did you find all these contests ?
You can use this website for such things.
mohammedehab2002 the XORcist
Probable difficulty of problems-
A-1200- math
B-1400- greedy or number theory
C-1700- constructive algorithms and trees
D-1900/2000 — XOR, constructive algorithms
E-2100+ — Beyond my guess :P
4 testers from IIT Kanpur :O
Probably maximum this time
After antontrygubO_o's comment on Ashishgup's blog.
*Le mohammedehab2002 : My forever orzable coordinator antontrygubO_o :)
:((
.
Is this rated for participants with ratings up to 2100, or only up to 1900? It seems to vary for Division 2 rounds.
2100
Div. 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.
What is the explanation for such kind of division?
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!
May be the shortest announcement of a div.2 ever
Because, he thanked everyone in a single paragraph instead of making a list like most other authors.
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.
Look at his before contest..most of the time he presents some problem with XOR .
I hope the problem statements will be as short as the announcement.
I think it will be (as he said he is lazy xd).
13 testers for just 5 problems, Isn't it strange ?
Edited-I posted on a different contest, I was asking for educational round.....Sorry!!
Not before the contest.
I think this time mohammedehab2002 will give us surprise and there won't be any xor related problem :P
Looking forward to this round, man!
You know the deal, upsolving the problems 5 mins after the round ends: https://youtu.be/2jW2zTSoGCM
Good luck and have fun!
Your videos are the best ! Keep up the good work.
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.
I hope its in base-2
you know the rule...no leading zeroes allowed
You have 1 hour 56 minutes left.
The last second of the minute
Sad to see your meme skills degraded :(
Sometimes the meme fails it's ok
Great, waiting for your comeback :)
he needs warmup
I wonder why it took you 5 seconds to move your mouse pointer to the submit button.
I sneezed
5 problems ..
From the diagram given above you are surely gonna fall..... As you took a jump bit early...
I hope Problem names Will be greater than Problem statements as usual
The first problem's score is $$$750$$$, So hard contest?
I guess Contest will be unrated if no xor problems will be given :)
mohammedehab2002 be like :
preparing myself to become pupil [EDIT: Why everyone downvoting me, it actually happened)
All the best. Hope you can achieve it XD
Finally you achieved that with your hard work.
First time seeing an announcement without explicitly naming Mike hah
Can you please provide link to his blog? It would be really helpful to learn from his blog.
https://codeforces.net/blog/entry/73490
Thank you
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.
mohammedehab2002 I never try his competition but when I saw comments, it seems like he will give questions in which xor will be used.
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.
who the hell chooses leetcode over codeforces!!
but i would rather participate in both of them
A significantly low number of registrations compared to previous rounds. Probably because of the score distribution. Or maybe because of the start time.
Good luck to everyone!
Problem D is almost exactly the same as 1325F - Ehab's Last Theorem ？Isn't it ？
Agreed
recycled
I think they must be different.
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.
Yes, it is true. I was not thoughtful sorry!
Not only a massive help, it kills the problem. I copied my solution to that F and changed like 4 lines.
and they have the same author?? but why?
Yes it is.
.
No Similarities Brother
Thanks! I enjoy doing it today
How did you solve C?
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 set
and push in answer array
and 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.
Thanks
For problem C I feel it was difficult to come up with such construction
I did not observe that for $$$ a_i {!=} a_{i-1}$$$ ans is b[i] = a[i-1]
What I did :
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
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)
I thought of the same thing, but couldn't think of a way to find the minimal cycle in O(n)
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.
thank you i was a bit confused with the solutions.
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.
The difference of heights between the current node and any node connected by a back edge implies a cycle of size difference of heights + 1
OR just read his editorial for a problem of a similar premise (problem F)
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
How to solve E?
you soved a,b,c,d with only one submisiion, I feel really sad that you could not solve e
He is master in doing these things :p
How to solve E? I managed to get AC by using random + some optimizations
How?
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.
I had the same idea but did not searched randomly and could not fit into the limit.
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.
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.
How to solve D?
What is test 25 in problem D?
I think it is a tree with an independent set of size > K/2.
Thanks, that was my issue!
Just curious, how did you arrive at that conclusion?
I also failed on this testcase and had the same error.
Swap (A, B)
O.o
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
They don't have to be unique. My code which may generate duplicate values passed pretests
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$$$.
Elements of b not necessarily unique. For example sample 2.
Elements in b need not be unique. I had the same doubt and asked the question and they said it can repeat
Am I the only one who doesn't know how to read and ignored the fact that Subarray was written & explained on problem A?
No I am with you :P
LOL, I figured it out 4 min to the end, coded it wrong, and got accepted at 1:59:59 SMH
Happens sometimes. How did you solve C?
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!
Cool. Thanks
Worst Contest Ever
Was that the most difficult div2 A problem, ever? or did I miss something?
Cannot agree more to you!
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
uphacked
Is there any case for problem C for which output is -1? I don't find any case like that.
Yes, if the array a is not sorted, it is -1.
The question specifies that the array a is always sorted.
Oh, sorry, so I don't think there is a case.
If a[0] != 0 and a[0] != 1, then it will be -1.
This too cannot happen according to the case ai ≤ ai+1
2 1 2
Again, the question specifies 0<=a[i]<=i. So a[1] will always be either 0 or 1.
Right, my bad.
But constraint says 0<=a[i]<=i So a[1] can't be 2.
0 0 1 1
That doesn't work. One output would be 2 2 0 0
Another example is
0 1 2 3 4 5that will be
6 0 1 2 3 4
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.
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
Can you explain how to solve A.
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.
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
"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).
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?
Nope. I literally wrote "except this one in parenthesis". Today's E was nice.
easy $$$\neq$$$ easier
Also, of course E is going to be easier the more problems there are and recently div2s have more problems than before.
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
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.
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 :
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.
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 :)
same with me I tried segtree and BS but kept getting WA over 4 times is some problem with the approach ??
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.
5 3 1 1 1 1 1 Simulate your binary search on this testcase.
You tried segtree and bs to solve a div2A? :|
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
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.
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...
I thought to use bs too. Luckily passed all tests: 83624037
Hack test:
LOL, lucky you. My BS just got wa 2. Seems the way we write BS is different.
I want a quick editorIAL NOW !!!!!!.
upvote this please
cheers to those mfuckers who downvoted my post !!
For your comment ,, author posted the editorial so quickly . xD
https://codeforces.net/contest/1325/problem/F
The Problem D today was VERY SIMILAR to this problem. It gives many participants unfair advantage. Please look into this. mohammedehab2002
The solution to today's question can be obtained by a simple modification to the code given in the editorial of this problem.
Yes I agree. This problem gives an unfair advantage to those who have not read that problem.
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 .
Well, the idea is pretty standard anyway
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 :)
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!
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
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...
yep and it took me 1 WA, not paying attention to the word "subarray" and solving it for "subsequence".
Me too, when I saw what it meant I facepalmed
Can you Please tell if I misinterpreted the definition of the subarray here , otherwise my soln seems fine 83678283
Edit : I did :(
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...
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 -
If 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.
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.
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.
me too :/
mohammedehab2002 and Testers after the contest.
When I could'nt solve A even after 15 min had passed..
Me thinking : "Is subarray size related to Xor of elements?" :facepalm:
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 :|
Erm weaktestcases for D? I just commented my assert and it got AC. Please uphack this.
Solution
Hey, you're not alone. How can I pass the problem D?
Why the weak pretests? :((((
-1 is not possible for Problem C There have no any case in the testing input. How funny!!!!!
He is right..Then i don't understand why people down-voting. Cause,, A is sorted and Ai <= i, the answer will always exist.
Weak Test Cases of Problem C
Following 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
Read the constraints properly. It says Ai<=i
Thank you for clarifying
If you mean
2
0 2
Then output is 1 0
And if you mean
3
2 0 2
Then 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.
For question D, Could anyone please tell me, what am i missing ? 83685667
I think you should add depth[x] — depth[y] + 1 >= 3 in your dfs
Sorry, But I retried its not the case. I guess it has issues when there is no cycle.
Try this test: 3 2 3 1 2 1 3
The answer should be: 1 2 3 But your code gives the output: 1 1
Thank you so much, I get it
What was the problem? Something wrong with coloring?
In case of a star graph, I considered only one case, so I was failing.
you mean, when you colored vertexes, you considered only black(white) ones?
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
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.
I have the same solution and it works: https://codeforces.net/contest/1364/submission/83784311
You like have a bug.
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.
Ok so compare this and this. I just made changes at few places. And yeah, still analyzing the old submission.
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.
ya.. i have also done the same 83691648
This code and this code are exactly same, I just changed less than equal to greater than equal. And got AC in both.
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
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.
Can someone look at this(Problem C) 83665936. Got Wrong at TC25
As elements of array b must be less than or equal to 1000000 as said in constriants.
MikeMirzayanov my rating got increased even though I should be out of competition.
You probably registered for this contest while you were a Candidate Master.
https://codeforces.net/contest/1364/submission/83691155
solution of problem C
I couldn't find anything about xor in the first 2 question.
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.
The system does not accept resubmitting unchanged code.
See submission 83638170 and 83694208. Both has exact same code.
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.
got it thanks
MikeMirzayanov
suta was first division participants before this contest, but his rating is changed.
bug?
Why weak pretests in Problem C? System Testing did not cover the case where the solution is -1. :(
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.
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.
https://codeforces.net/contest/1325/problem/F
The Problem D today was VERY SIMILAR to this problem. It gives many participants unfair advantage.
MikeMirzayanov
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.
Upvote this to get AC in 4 questions only in your next contest. T_T
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.
8 9 3
8 1
8 7
8 6
7 2
2 4
2 5
4 5
5 3
4 3
1
4 5
which is wrong because there is an edge between 4 and 5.
verry bad!