mohammedehab2002's blog

Codeforces Round #649 (Div.2)
By mohammedehab2002, 4 years ago, In English

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:-

  1. Um_nik
  2. 244mhq
  3. hank55663
  4. noimi
  5. neal

Div.2:-

  1. SanyaSaske
  2. Chloristendika
  3. el_risitas
  4. Ehaam
  5. RinkaSnow

Good luck & Have fun :D

  • Vote: I like it
  • +1165
  • Vote: I do not like it

Comments Comments (266)
| Write comment?
»
4 years ago, # |
  Vote: I like it +204 Vote: I do not like it

mohammedehab2002 and his xor.

→ Reply
»
4 years ago, # |
  Vote: I like it +173 Vote: I do not like it

Incoming XOR missiles...

→ Reply
»
4 years ago, # |
  Vote: I like it +365 Vote: I do not like it

*Codeforces Round #649 (Div. 2), writers: mohammedehab2002*

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +147 Vote: I do not like it

You-know-who

Making Mike sound like Lord Voldemort

→ Reply
»
4 years ago, # |
  Vote: I like it +276 Vote: I do not like it

Oh.. Thank you for thanking me for the amazing Codeforces and polygon platforms, almost forgot :P

→ Reply
»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

mohammedehab2002 and his short statements.

→ Reply
»
4 years ago, # |
  Vote: I like it +291 Vote: I do not like it

→ Reply
»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Wait so what is up with the xor stuff? Sorry if I'm a noob and I don't know the jokes.

→ Reply
»
4 years ago, # |
  Vote: I like it +184 Vote: I do not like it

A contest that has short statements is rarely found, so I advice you to register this contest :))

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

Did you mean YouKn0wWho!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

kill type-races and because I'm lazy, so contest is going to be a bit hard and tricky . I am excited for it .

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think this killed too many type-races. ;)

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +145 Vote: I do not like it
Spoiler
Spoiler
Spoiler
Spoiler

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +102 Vote: I do not like it

    This time I hope to see the problem "Ehab goes to Rehab" xD xD

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -49 Vote: I do not like it

This is how my division 2 round with just 5 problems is like....

PROBLEM A

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...

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    SO MANY DOWNVOTES!!!! But unfortunately I ended ,the more or less same way......

    → Reply
»
4 years ago, # |
← Rev. 6   Vote: I like it -72 Vote: I do not like it

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -35 Vote: I do not like it

Hope there is not unexpectedly high increase in difficulty from B to C :)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If someone can give link for 5 problem div 2 contests it would be a great help

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -36 Vote: I do not like it

→ Reply
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

mohammedehab2002 the XORcist

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +36 Vote: I do not like it

4 testers from IIT Kanpur :O

Probably maximum this time

→ Reply
»
4 years ago, # |
  Vote: I like it +40 Vote: I do not like it

After antontrygubO_o's comment on Ashishgup's blog.
*Le mohammedehab2002 : My forever orzable coordinator antontrygubO_o :)

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -26 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this rated for participants with ratings up to 2100, or only up to 1900? It seems to vary for Division 2 rounds.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is the explanation for such kind of division?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +11 Vote: I do not like it

        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!

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

May be the shortest announcement of a div.2 ever

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because, he thanked everyone in a single paragraph instead of making a list like most other authors.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Look at his before contest..most of the time he presents some problem with XOR .

    → Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

I hope the problem statements will be as short as the announcement.

→ Reply
»
4 years ago, # |
  Vote: I like it -36 Vote: I do not like it

13 testers for just 5 problems, Isn't it strange ?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -47 Vote: I do not like it

Edited-I posted on a different contest, I was asking for educational round.....Sorry!!

→ Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

I think this time mohammedehab2002 will give us surprise and there won't be any xor related problem :P

→ Reply
»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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!

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Your videos are the best ! Keep up the good work.

    → Reply
»
4 years ago, # |
  Vote: I like it +146 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +39 Vote: I do not like it

5 problems ..

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    From the diagram given above you are surely gonna fall..... As you took a jump bit early...

    → Reply
»
4 years ago, # |
  Vote: I like it +229 Vote: I do not like it

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I hope Problem names Will be greater than Problem statements as usual

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

The first problem's score is $$$750$$$, So hard contest?

→ Reply
»
4 years ago, # |
  Vote: I like it +49 Vote: I do not like it

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

I guess Contest will be unrated if no xor problems will be given :)

→ Reply
»
4 years ago, # |
  Vote: I like it -30 Vote: I do not like it

mohammedehab2002 be like :

meme

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

preparing myself to become pupil [EDIT: Why everyone downvoting me, it actually happened)

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

First time seeing an announcement without explicitly naming Mike hah

→ Reply
»
4 years ago, # |
  Vote: I like it +106 Vote: I do not like it

→ Reply
»
4 years ago, # |
  Vote: I like it +63 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

mohammedehab2002 I never try his competition but when I saw comments, it seems like he will give questions in which xor will be used.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -62 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

A significantly low number of registrations compared to previous rounds. Probably because of the score distribution. Or maybe because of the start time.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to everyone!

→ Reply
»
4 years ago, # |
  Vote: I like it +133 Vote: I do not like it

Problem D is almost exactly the same as 1325F - Ehab's Last Theorem ？Isn't it ？

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Agreed

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    recycled

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think they must be different.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +31 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Yes, it is true. I was not thoughtful sorry!

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +33 Vote: I do not like it

      Not only a massive help, it kills the problem. I copied my solution to that F and changed like 4 lines.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    and they have the same author?? but why?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Yes it is.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -21 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks! I enjoy doing it today

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How did you solve C?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :

    1. 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.
    2. Maintained missing number or mex, after inserting $$$ b_{i-1} $$$.
    3. 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.

    4. 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

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought of the same thing, but couldn't think of a way to find the minimal cycle in O(n)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        thank you i was a bit confused with the solutions.

        → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +9 Vote: I do not like it

    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 stuck

    OR just read his editorial for a problem of a similar premise (problem F)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    you soved a,b,c,d with only one submisiion, I feel really sad that you could not solve e

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      He is master in doing these things :p

      → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve E? I managed to get AC by using random + some optimizations

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I had the same idea but did not searched randomly and could not fit into the limit.

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve D?

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

What is test 25 in problem D?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I think it is a tree with an independent set of size > K/2.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks, that was my issue!

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just curious, how did you arrive at that conclusion?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        I also failed on this testcase and had the same error.

        → Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Swap (A, B)

O.o

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it -11 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    They don't have to be unique. My code which may generate duplicate values passed pretests

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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$$$.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Elements of b not necessarily unique. For example sample 2.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Elements in b need not be unique. I had the same doubt and asked the question and they said it can repeat

    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Am I the only one who doesn't know how to read and ignored the fact that Subarray was written & explained on problem A?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    No I am with you :P

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      LOL, I figured it out 4 min to the end, coded it wrong, and got accepted at 1:59:59 SMH

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Happens sometimes. How did you solve C?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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!

          → Reply
»
4 years ago, # |
  Vote: I like it -63 Vote: I do not like it

Worst Contest Ever

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Was that the most difficult div2 A problem, ever? or did I miss something?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Cannot agree more to you!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Is there any case for problem C for which output is -1? I don't find any case like that.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain how to solve A.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    "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).

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nope. I literally wrote "except this one in parenthesis". Today's E was nice.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +17 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          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.

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    same with me I tried segtree and BS but kept getting WA over 4 times is some problem with the approach ??

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        5 3 1 1 1 1 1 Simulate your binary search on this testcase.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      You tried segtree and bs to solve a div2A? :|

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +16 Vote: I do not like it

        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

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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...

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I thought to use bs too. Luckily passed all tests: 83624037

    Hack test:

    Spoiler
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      LOL, lucky you. My BS just got wa 2. Seems the way we write BS is different.

      → Reply
»
4 years ago, # |
  Vote: I like it -61 Vote: I do not like it

I want a quick editorIAL NOW !!!!!!.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -58 Vote: I do not like it

    upvote this please

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -31 Vote: I do not like it

      cheers to those mfuckers who downvoted my post !!

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For your comment ,, author posted the editorial so quickly . xD

    → Reply
»
4 years ago, # |
  Vote: I like it +49 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    The solution to today's question can be obtained by a simple modification to the code given in the editorial of this problem.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes I agree. This problem gives an unfair advantage to those who have not read that problem.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 .

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    Well, the idea is pretty standard anyway

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      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 :)

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

        Agree, the most uncomfortable is that it was the same problemsetter.

        because I'm lazy, you'll be given 5 problems

        This does not look like a joke anymore!

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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...

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    yep and it took me 1 WA, not paying attention to the word "subarray" and solving it for "subsequence".

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    Can you Please tell if I misinterpreted the definition of the subarray here , otherwise my soln seems fine 83678283

    Edit : I did :(

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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...

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 -

      Spoiler

      Sorry for my bad English.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +108 Vote: I do not like it

mohammedehab2002 and Testers after the contest.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

    When I could'nt solve A even after 15 min had passed..

    Me thinking : "Is subarray size related to Xor of elements?" :facepalm:

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -44 Vote: I do not like it

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 :|

→ Reply
»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Erm weaktestcases for D? I just commented my assert and it got AC. Please uphack this.

Solution

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the weak pretests? :((((

→ Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

-1 is not possible for Problem C There have no any case in the testing input. How funny!!!!!

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    He is right..Then i don't understand why people down-voting. Cause,, A is sorted and Ai <= i, the answer will always exist.

    → Reply
»
4 years ago, # |
  Vote: I like it -28 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Read the constraints properly. It says Ai<=i

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For question D, Could anyone please tell me, what am i missing ? 83685667

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I think you should add depth[x] — depth[y] + 1 >= 3 in your dfs

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, But I retried its not the case. I guess it has issues when there is no cycle.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much, I get it

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What was the problem? Something wrong with coloring?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          In case of a star graph, I considered only one case, so I was failing.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            you mean, when you colored vertexes, you considered only black(white) ones?

            → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +73 Vote: I do not like it

    Ok so compare this and this. I just made changes at few places. And yeah, still analyzing the old submission.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This code and this code are exactly same, I just changed less than equal to greater than equal. And got AC in both.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone look at this(Problem C) 83665936. Got Wrong at TC25

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As elements of array b must be less than or equal to 1000000 as said in constriants.

    → Reply
»
4 years ago, # |
  Vote: I like it +61 Vote: I do not like it

MikeMirzayanov my rating got increased even though I should be out of competition.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    You probably registered for this contest while you were a Candidate Master.

    → Reply
»
4 years ago, # |
  Vote: I like it -9 Vote: I do not like it

https://codeforces.net/contest/1364/submission/83691155

solution of problem C

→ Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I couldn't find anything about xor in the first 2 question.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The system does not accept resubmitting unchanged code.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      See submission 83638170 and 83694208. Both has exact same code.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        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.

        → Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

MikeMirzayanov

suta was first division participants before this contest, but his rating is changed.

bug?

→ Reply
»
4 years ago, # |
  Vote: I like it -34 Vote: I do not like it

Why weak pretests in Problem C? System Testing did not cover the case where the solution is -1. :(

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it -24 Vote: I do not like it

https://codeforces.net/contest/1325/problem/F

The Problem D today was VERY SIMILAR to this problem. It gives many participants unfair advantage.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -29 Vote: I do not like it

    MikeMirzayanov

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it -32 Vote: I do not like it

Upvote this to get AC in 4 questions only in your next contest. T_T

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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:
Output:
→ Reply
»
4 years ago, # |
  Vote: I like it -24 Vote: I do not like it

verry bad!

→ Reply