Блог пользователя mohammedehab2002

Автор mohammedehab2002, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +1165
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +204 Проголосовать: не нравится

mohammedehab2002 and his xor.

»
4 года назад, # |
  Проголосовать: нравится +173 Проголосовать: не нравится

Incoming XOR missiles...

»
4 года назад, # |
  Проголосовать: нравится +365 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +147 Проголосовать: не нравится

You-know-who

Making Mike sound like Lord Voldemort

»
4 года назад, # |
  Проголосовать: нравится +276 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

mohammedehab2002 and his short statements.

»
4 года назад, # |
  Проголосовать: нравится +291 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +184 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

Did you mean YouKn0wWho!

»
4 года назад, # |
  Проголосовать: нравится 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 .

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +145 Проголосовать: не нравится
Spoiler
Spoiler
Spoiler
Spoiler

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +102 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -49 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 6   Проголосовать: нравится -72 Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -35 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -36 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

mohammedehab2002 the XORcist

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

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 года назад, # |
Rev. 2   Проголосовать: нравится +36 Проголосовать: не нравится

4 testers from IIT Kanpur :O

Probably maximum this time

»
4 года назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -26 Проголосовать: не нравится

.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What is the explanation for such kind of division?

      • »
        »
        »
        »
        4 года назад, # ^ |
        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!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

May be the shortest announcement of a div.2 ever

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -47 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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!

»
4 года назад, # |
  Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +39 Проголосовать: не нравится

5 problems ..

»
4 года назад, # |
  Проголосовать: нравится +229 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -23 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится

mohammedehab2002 be like :

meme

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

First time seeing an announcement without explicitly naming Mike hah

»
4 года назад, # |
  Проголосовать: нравится +106 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

»
4 года назад, # |
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.

»
4 года назад, # |
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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck to everyone!

»
4 года назад, # |
  Проголосовать: нравится +133 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Agreed

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    recycled

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think they must be different.

  • »
    »
    4 года назад, # ^ |
    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +33 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    and they have the same author?? but why?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Yes it is.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -21 Проголосовать: не нравится

.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How did you solve C?

  • »
    »
    4 года назад, # ^ |
    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 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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
4 года назад, # |
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)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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.

  • »
    »
    4 года назад, # ^ |
    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 stuck

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E?

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve D?

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

What is test 25 in problem D?

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Swap (A, B)

O.o

»
4 года назад, # |
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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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$$$.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    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

»
4 года назад, # |
  Проголосовать: нравится +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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    No I am with you :P

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Happens sometimes. How did you solve C?

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +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!

»
4 года назад, # |
  Проголосовать: нравится -63 Проголосовать: не нравится

Worst Contest Ever

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you explain how to solve A.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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.

»
4 года назад, # |
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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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).

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -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?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.

»
4 года назад, # |
  Проголосовать: нравится +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 :)

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +31 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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...

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    Hack test:

    Spoiler
»
4 года назад, # |
  Проголосовать: нравится -61 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

https://codeforces.com/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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      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 .

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    Well, the idea is pretty standard anyway

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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 :)

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +23 Проголосовать: не нравится

        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!

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 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

»
4 года назад, # |
  Проголосовать: нравится +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...

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

    Edit : I did :(

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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...

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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 -

      Spoiler

      Sorry for my bad English.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.

»
4 года назад, # |
  Проголосовать: нравится +108 Проголосовать: не нравится

mohammedehab2002 and Testers after the contest.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +52 Проголосовать: не нравится

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

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

»
4 года назад, # |
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 :|

»
4 года назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

Solution

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why the weak pretests? :((((

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    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.

»
4 года назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    Read the constraints properly. It says Ai<=i

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 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

»
4 года назад, # |
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.

»
4 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +73 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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

»
4 года назад, # |
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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 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.

»
4 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

MikeMirzayanov

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

bug?

»
4 года назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.

»
4 года назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

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

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

»
4 года назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +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:
Output:
»
4 года назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

verry bad!