By hu_tao, 7 weeks ago, In English

Hi all!

This weekend, at Oct/17/2021 14:05 (Moscow time) we will hold Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1). It is based on the problems of Technocup 2022 Elimination Round 1 that will be held at the same time.

Note the unusual start time of the contest.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup website and take part in the Elimination Round.

The Div. 1 + Div.2 edition is open and rated for everyone. Register and enjoy the contests!

The problems were written and prepared by Tlatoani, golions, rabaiBomkarBittalBang, qlf9, and me. We would like to express our thanks for antontrygubO_o, isaf27, and KAN for reviewing our problems and being great coordinators!

Huge thanks to the following users for testing our round: kefaa2, AmShZ, dorijanlendvaj, Keshi, czhang2718, 2020akadaver, Magikarp1, Richw818, quantum8, RayLee234, I_Love_YrNameCouldBeHere, Qualified, 1-gon, smax, m371, kassutta, namanbansal013, HackerMonk, Ari, PurpleCrayon, FieryPhoenix, Jellyman102, bWayne, Omkar, Aleks5d, Makcum888

And as usual, thanks to MikeMirzayanov for the great Codeforces and Polygon platforms.

You will have 2 hours and 15 minutes to solve 9 problems. The score distribution will be announced very shortly before the contest starts. Good luck to all!

UPD1:

Score distribution: $$$500$$$ — $$$1000$$$ — $$$1500$$$ — $$$1750$$$ — $$$2250$$$ — $$$2750$$$ — $$$3000$$$ — $$$3500$$$ — $$$4000$$$.

UPD2:

Thanks to everyone who participated in the contest! We hope you enjoyed the problems. We apologize for the issues at the beginning of the contest; we hope that you were still able to have a great experience.

Editorial

UPD3:

Congratulations to the winners of Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1)!

  1. medium_waxberry
  2. fivedemands
  3. jiangly
  4. peti1234
  5. xay5421
  6. Um_nik
  7. orzdevinwang
  8. yosupo
  9. SHZhang2
  10. tatyam

And a special congratulations to peti1234 for being the only contestant to solve problem I!

Congratulations also to the winners of Technocup 2022 - Elimination Round 1!

  1. Ormlis
  2. SomethingNew
  3. Arayi
  4. alexxela12345
  5. I_HATE_CONSTRUCTIVES
  6. oleh1421
  7. Mangooste
  8. arbuzick
  9. idontwannawin
  10. Dasha_Gnedko
 
 
 
 
  • Vote: I like it
  • +460
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

see you next banner

»
7 weeks ago, # |
  Vote: I like it +73 Vote: I do not like it

Note the unusual timings :)

»
7 weeks ago, # |
  Vote: I like it +73 Vote: I do not like it

challenging problems.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping for a good contest :)

»
7 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Hoping to be back to cyan. working hard to become expert.

»
7 weeks ago, # |
  Vote: I like it +54 Vote: I do not like it

Clash with Atcoder Beginner Contest :(

»
7 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Damn 9 problems in 2:15 hrs

»
7 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Can we participate without being from a Russian speaking country?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    You can register for the contest based on this (#749)

»
7 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

May the force be with you. Good luck to you all :))

»
7 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

As a tester, good luck!

»
7 weeks ago, # |
  Vote: I like it -35 Vote: I do not like it

Can I see pretest examples in my solution?

»
7 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

MAy the OOds be ever in ur favor

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Looking forward to solve problems and see a hike in my rating.

»
7 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

The only bad thing is the time of the contest. There is another contest in atcoder at the same time.

»
7 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

9 problems,so much!!!!

»
7 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

Solve 9 problems within 2 hours and 15 minutes... The time limit is too tight!!!

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably first few problems would be ez :) . Otherwise the time is very tight.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    for LGMSs it's not so tight, for Div2 it's not big difference to solve first 3-4 problems in 2:15 or in 2:45 for example

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had only 10 minutes for the last three problems,so I just left and took a look at Atcoder Beginner Contest :(

»
7 weeks ago, # |
Rev. 2   Vote: I like it -142 Vote: I do not like it

great

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Woah cheater has the guts to comment!

    How are you cheater?

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      how he is cheater. I also need the third eye ;)

      PS: Lol! he changed his comment from "Hope again we will solve at least 3,4 problems . best of luck everyone !" to "great" XD.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        he/she adds random comments for avoiding plagiarism check.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sad thing is, they have actually figured out how to circumvent plagiarism checks.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        look at his solution for problems during the contest... there are more comments in code than the code itself

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it +32 Vote: I do not like it

          oh! got it. An expert cheater XD

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      His way of writing code is so terrible, he got rank 47 by cheating, another terrible news!

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    solve copy paste

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have solved the problems like f, too.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    Kitni cheating karega be?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I think I now know why "we" was used :|

»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

May Mike be with us.

»
7 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it
lighthearted meme
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    meme
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it -10 Vote: I do not like it
      meme
»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

This contest clashes with AtCoder Beginner Contest 223 at 17:30 (UTC+5.5)

»
7 weeks ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

have you noticed these days less number of people participating compared to two months earlier.

»
7 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

daytime in China,finally dont't need to stay up late

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping for positive delta and also:

1 манул)

»
7 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Looks like companies wanted to see each other clashes

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

everyone can register to the Technocup 2022 — Elimination Round.

isn't it supposed to be private register?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

:( Clashes with The International final

»
7 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

Accroding to tradition,This Contest might be delayed:(

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Contest begin, my province: shut down the electricity.

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

todays contest be like "you all lie under my shoes"

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Very very difficult questions !!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

the problems are very hard, should be div. 1 only imo.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Tree problem in B? why...

  • »
    »
    7 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    note that m<n, which means that there is at least one vertex never occurs as $$$b_i$$$ among all restrictions

    we can always find a such vertex and link all other vertices to it.

    so it's like a greedy problem more than a graph/tree problem to me.

»
7 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

Div.1 + Div.2 = Div.1.5

»
7 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Div2 rounds based on some Russian contest for school kids are always harder than usual Div2 rounds.

»
7 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

Imagine wasting 30+ mins on D because you forget to assert the values of $$$a_i$$$ in a query and print $$$a_i = n + 1$$$ in a certain case T_T.

But my mistakes aside, absolutely brilliant contest, one of the best I have seen in a while — Not a single boring problem from A-E! (can't talk about the rest since I haven't solved them, though F does look interesting as well)

E is a really really really cool problem — it looks insanely complex at first but decomposes to pretty easy ideas through some cool observations.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice C I got it but too late

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sameeee :(, there was just one simple observation and i over complicated that problem, got the idea only after a min of the contest end

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

What could be the testcase 3 for C?

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Likely some mistake with not checking if cells which are $$$X$$$ could hypothetically escape if they weren't $$$X$$$. If that isn't the case you can't determine if it was initially $$$X$$$ or not. Forgetting to check that caused WA3 for me.

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I looked for patterns like: _X \n X. where _ is any character, Here [2,2] can be both X or . , so this subgrid is indeterminable. Did I miss something?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        You were supposed to look for the pattern

          X
        X _
        

        UPD: Oops, finding both patterns is the same thing, you are right

  • »
    »
    7 weeks ago, # ^ |
    Rev. 7   Vote: I like it 0 Vote: I do not like it

    I removed my WA on 3 by accounting for the fact that the leftmost column in the subgrid need not be considered for finding an ambiguous cell since the leftmost column will always be unambiguous. so we only look to need to look for ambiguous cells in (x+1,y).

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C XX XX

query : can 1 2 is determinable ?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you mean XX \n XX? Then it's not determinable.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Y ?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        Because, we can't determine the state of (2,2) cell exactly without looking at the grid. Suppose, instead of

        XX  
        XX
        

        We're given,

        XX  
        X.
        

        Then, still none are exitable, but one cell in the latter is empty. So, undeterminable!

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ok

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Thanks for putting me out of my misery. I spent around 2 hrs struggling with this problem. Now that I know, no one deserves that -100 more than me, I am at peace. Thanks again.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        because XX \n XX and XX \n X. will both result in NN \n NN , hence not determinable

»
7 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

A was much harder than B. Really disapointed about not reading problem B first

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    wtf, i insta-solved A and only managed to solve B with 2 minutes remaining

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Same. Lool. I feel a little better now for struggling at B. Thank you.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      B isn't that much tougher than A. I mean the statement literally highlights $$$m \lt n$$$ in bold which is the key idea to an easy enough pigeonhole idea.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        oh wow! clearly i didn't notice the bolding

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But it did not state, as is customary, that it can be proven that under the given constraints the solution always exists.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This guy is on drugs

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Another math hater.

»
7 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

is this contest is for High-school ??

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +122 Vote: I do not like it

    It's Russian highschool level which is roughly the same difficulty as a U.S. post-doctorate program or a Chinese gradeschool contest.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This isn't a joke, is it? :)

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Most probably not even a gradeschool contest Chinese contest because all the problems were well known tricks.

»
7 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

Problem E is such a problem, where you know that the first thing that comes to your mind has to be correct [path does not matter], otherwise it will be NP-hard or something.

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

What is wrong in this approach for Problem C

I check the minimum answer for each column with BFS and for each query I get the maximum for each column $$$C_l$$$ $$$C_(l+1)$$$ ... $$$C_r$$$, If it's less than L, print "YES", otherwise print "NO"

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    had the same idea, WA pretest 3 :(

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I did something similar but got WA on test 3.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Maybe you did not handle if a blocked cell itself cannot exit the sub-graph if it was not blocked. In this case we will not be able to know if its N represents a blocked or an empty cell.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can u explain why do I need to check that?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Are you checking if cells which are $$$X$$$ would be theoretically exitable if they weren't $$$X$$$ as well?

    Suppose one of those cells is not exitable even if it wasn't $$$X$$$, then you wouldn't be able to differentiate between it being initially marked $$$X$$$ or not, so the grid isn't determinable.

    I forgot about this and got WA3 because of that.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      aah so you are saying that for n=2 m=2 XXXX query (1,2) should be NO instead of YES?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
        Rev. 2   Vote: I like it +11 Vote: I do not like it

        That's correct, because it could also be
        XX
        X.

        Both situations are identical in the view of exitability, since all 4 cells are not exitable.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I can't understand why I need to check If $$$X$$$ would be theoretically exitable if they weren't $$$X$$$.

      I am checking if there is empty cell is not exitable, if there is atleast one then I can't differentiate.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problems. Though it would be better (at least for me) to extend the duration of the contest... I just gave up when I finished reading problem G and found out that there was only 20 minutes left.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hint for B please

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    $$$m<n$$$ (strictly less)

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I made edges a -- c for the given m restrictions. Then, to get the remaining edges I connected all separate components (checked using DSU) by an edge. Whats wrong with this? I kept getting WA2.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Connecting all edges a-c may result in a cycle even when m<n. Consider the following: 1 4 2 2 5 3 3 6 1

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          EDIT: This will fail thsi test case

          ` 1 4 3 1 2 3 3 1 2 2 3 1

          `

          Thanks. I did realize this towards the end, so added the check for cycles even while adding the initial $$$m$$$ edges from the restrictions. This is what I did:

          add edge $$$a$$$ — $$$c$$$ if they arent in the same component

          if $$$a$$$ and $$$c$$$ are already part of the same component, add edge $$$b$$$ — $$$j$$$ instead. $$$j$$$ is any node apart from $$$a$$$, $$$c$$$ and $$$b$$$.

          Will this work? It didnt work during the contest because I was printing $$$0$$$-indexed $$$j$$$ node.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Consider this case,
        4 3
        1 2 3
        3 1 2
        2 3 1

        In your final answer, the third constraint will not be satisfied.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Make b[i] leaves

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It's given 1 < m < n .

    So there will be at least one node that can be between any two nodes, make it root. Now just connect all the other nodes to it.

    Spoiler
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My approach for B: I basically checked which node is not present as bi in the restrictions, then i used this node to create edge to every other node. but this gives WA on pretest 2 Can anyone explain where i am going wrong??

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    its correct its my solution too u probably implemented it wrong

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Check if your bi is 0-indexed or 1-indexed. I had the same problem where I accidentally read in all bi's 1-indexed, and changing it to 0-indexed fixed it.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also did same.. May be you have done some mistake in implementation

»
7 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Nice problem set.

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Anyone else getting RTE on pretest 25 on Problem E?

Update: Figured it out. Dumb mistake, I was trying to pick a starting point for the spanning tree by finding a vertex with a nonzero number of queries, but accidentally set the starting point to be the number of queries itself instead of the vertex id. In hindsight, could have just rooted the spanning tree at vertex 1.

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1586/submission/132264873
can anyone help with finding bug in this solution for C?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Did someone see F before? ko_osaga?

»
7 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

I liked F very much, thanks for the round :)

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    I think problem F is more like a MO problem than a OI problem.

»
7 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

(Deleted)

»
7 weeks ago, # |
  Vote: I like it -67 Vote: I do not like it

The parallel AtCoder abc223 had better quality of programming problems.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +124 Vote: I do not like it

    well, the quality of the problemset does not depend on whether you can solve them or not.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Chinese problemsetting forces invading Russia lol

»
7 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Problems are great, but I personally think the duration is a bit short, especially for data structure problems like H. Sadly I wasn't able to debug my code in time :(

more sadly, I succeeded in debugging it 10 minutes after the contest ended :(

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone else get WA on test 6 for problem E?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Your DP part is probably incorrect.

    6 5
    1 2
    1 3
    1 4
    3 5
    3 6
    3
    2 4
    1 5
    3 6
    

    Output should be 3.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is C a segment tree problem?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    More like dp-problem

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    No, much simpler than that.

    Hint: Consider under what situations will a single cell not be determinable.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It can be used (I used it) but not necessary

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +56 Vote: I do not like it
    Solution in 1 sentence
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    Nope, its dp combined with a sliding window like idea.

    The core idea is that if a cell can't exit the grid due to being blocked by cells above / to the left of it, it would be non-exitable regardless of whether it was $$$X$$$ or not. So all cells in a subgrid with $$$1 \leq i \leq n$$$, $$$x_1 \leq j \leq x_2$$$ must not be blocked for the answer to be yes.

    Basically let $$$minrow_{i, j}$$$ and $$$mincolumn_{i, j}$$$ be the smallest row and column reachable from a cell $$$(i, j)$$$.

    Then the minimum $$$x_1$$$ for a given $$$x_2$$$ is $$$max(mincolumn_{i, j})$$$ where $$$1 \leq i \leq n$$$, $$$1 \leq j \leq x_2$$$ and $$$maxrow_{i, j} \gt 1$$$.

    This can be calculated quickly for all $$$x_2$$$ with an easy observation — Since the function is max, $$$x_1$$$ never decreases as $$$x_2$$$ increases. So we can just iterate first on increasing $$$j$$$ then on $$$i$$$ to calculate the answer in $$$O(n \times m)$$$ time.

    Code
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    My solution is if there's an empty cell on column i, and it is blocked, then it is bad.

    So I use dp to check the furthest left a cell could and store the max for all cell of that column, then use segment tree to check max(l,r) <= l

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I aolved with seg tree tho idk it was the only soultion that came into my mind

»
7 weeks ago, # |
  Vote: I like it -62 Vote: I do not like it

CF goes down every 2 minutes: Maybe Codeforces developers didn't do enough leetcode!!!

»
7 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

Does anyone have a rigorous proof why arbitrary spanning tree works for E?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It suffices to prove that, for a given tree and $$$u,v,w \in V$$$, edges which appears in exactly one of the simple path $$$uv$$$ and $$$vw$$$ forms the simple path from $$$u$$$ to $$$w$$$. This should be verified easily.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First let's think of it as a dfs tree after getting a dfs tree.

    what you can do if you have a range of edges of ones on this tree is that you remove this range and replace it with one edge with 1 which is a back edge this edge will also have a 1 and since this edge is mapped to a range of edges it's obvious that you can't make it into a 0.

    I think it's the same with spanning trees the difference is the edges are not back edges but they are still mapped to one range of edges.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    The existence of an example is equivalent to all nodes participating in an even number of paths as endpoints. => is trivial, <= can be shown easily to hold for any tree (consider any edge, if it is used an odd number of times, the sum of usages in one of the subtrees would be odd as well).

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    path from u to v = (path from u to root) xor (path from v to root)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Feeling dumb af for not solving B

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the solution for D? Best idea I got was a randomized algorithm with expected number of queries to be exactly 2*n(which didn't pass as expected)

  • »
    »
    7 weeks ago, # ^ |
    Rev. 4   Vote: I like it +12 Vote: I do not like it

    Suppose we can find $$$p_n$$$ in at most $$$n$$$ queries, then we can find all other values in at most $$$n$$$ queries by increasing $$$a_1, \ldots, a_{n - 1}$$$ or $$$a_n$$$ by the required amount for it to match each value $$$1 \leq k \leq n$$$, one at a time.

    As for finding $$$p_n$$$, suppose I set $$$a_1, \ldots, a_{n - 1} = 1$$$ and $$$a_n = x$$$, then we will only get $$$0$$$ as a response if $$$p_n + x > n + 1$$$ (or $$$p_n + x > (n - 1) + 1$$$ if $$$p_n$$$ is $$$n$$$). So we can just iterate on all values of $$$x$$$ from $$$2$$$ upward and see the first value for which the condition fails to hold to exactly identify $$$p_n$$$.

    Code
  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it +11 Vote: I do not like it

    Hint: Create an undirected graph with N vertices where edge u-v indicates abs(p[u]-p[v])=1.

    If you figure this out it's simple. All that is left is running a dfs.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it
    My solution:
  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    You can also solve it with a tighter query limit using binary search:

    The idea is if you find the last element, you can find every other element in $$$n$$$ queries. We can find the last element by performing a binary search to find $$$p_n - min(p_{n - 1}, p_{n - 2}, ...)$$$. If this value is negative, it means the last element is 1. So we only end up consuming $$$n + logn$$$ queries :)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

problem D was really nice, I enjoyed it very much.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone point out my mistake on C? https://codeforces.com/contest/1586/submission/132256767

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think, you should delete this line:

    $$$if(Grid[i][j] == 0){$$$

    EDIT: It still struggles with test 4, Idk what else is wrong.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh , but if it's a X, then we can include that column rt?
      Like this,

      . . x .  . .  x .
      . x x .  . x [.] .
      . . . .  . .  . .
      . . . .  . .  . .  
      
      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In such a construction of two diagonally adjacent 'X' cells, the cell between them will always be non-exitable, regardless of what is written in it. Thus, we can change its state and get a different initial table with the same set of exitable cells, so we have to consider the mentioned case too and include that column.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ah my bad, didn't understand the statement clearly.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me to indicate mistake in solution c:132264422

»
7 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

Alex_Wei it's Unsuccessful hack for a reason :D

Spoiler
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Its 99.99% purposeful unsuccessful hacks to get last place. I've done it in the past when I felt I was getting too worried about my rating to the extent where the nervousness was ruining contests for me.

    Its trivial to copy paste the same input and change 1 value (can't use the same input twice on the same person) and make 20-30+ hacks / minute to quickly send yourself to last place.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

liked D very much ... though was'nt able to implement my logic in time , but felt really good after solving it! :D thnx authors for such good problems!

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

132242048 C isn't a multitest problem but why I don't clear the array it makes my code FST ? After I clear the array I got accepted.132265702. Why ? When I change C++20 to C++17 in my FST code I have wrong in test 19 instead of 16. Why ?? :>

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You are defining an array locally (inside of a function) rather than globally. The locally-defined array can contain anything at initialization.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ya. It will be a big experience for me. Thanks

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    the array you defined is not global, if you didn't clear it then it just contain garbage :D

    Spoiler
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am able to solve only 2 problems in most of the div 2 contests. can anyone give me suggestions to become a specialist

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    Try to solve 3 problems.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks. I will try.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Okay to be serious, here are some suggestions that may be helpful for you:

        1. Try to have a good format of code, this is helpful because it allows you to debug easier and code faster.(This means indentations and spaces)

        2. Try to think more before you code. Try to have an idea of what algorithm you will implement, and what are the details that may cause problems.

        3. Solve more problems in general. To be able to solve 3 problems, you need to be fluent in the language you code and be able to think logically to reach a solution. The third problem often needs some thinking, it isn't as direct, so it may need more practice.

        4. If you are sure that your algorithm is correct, and you fail to debug, try writing it over.

        Hope this may be helpful for you.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Does it mean that the first two problems require no thinking at all? :)

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Jokes aside, seeing how many people here (even high rating ones) completely blacked out on B, nope.

            Sometimes those "easy" problems actually requires you to figure out a specific trick, you get the problem if you do and you don't get it if you don't. Which is exactly what B is.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          okay.thank you so much

»
7 weeks ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

The contest is nice ,problem D,E,F are interesting . It is sad that I can solve G if 5 more minutes are given :(

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It is sad that I can solve D if 5 more minutes are given :D
    also 9 problems deserve way more than 2:15

»
7 weeks ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

issue solved

»
7 weeks ago, # |
  Vote: I like it +58 Vote: I do not like it

To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!

==

Рейтинги предварительно обновлены. Через некоторое время я удалю читеров и пересчитаю рейтинг снова!

»
7 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

This contest, I got rank 1328th (my previous rating is 1531) and my friend got rank 1446th (his pre rating is 1650) but my rating increased 75 and his rating increased 95. Can someone explain me this??? Many thanks

»
7 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

I'm curious about the special judge for problem B.How to check an output is valid or not quickly(I can only thought about a data structure which is O(n log^2 n))?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if b is on path between a and c, than dist(a,b)+dist(b,c)=dist(a,c)

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        this help's to check if the tree is valid

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          Finding distance is not any faster than simply checking nodes on the way to the LCA.

          How is it relevant to the comment you replied to?

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            If there are $$$m$$$ restrictions, we can check the validity of output in $$$O((n+m)logn)$$$. this is faster than $$$O(nlog^2n)$$$

            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Can you elaborate?

              • »
                »
                »
                »
                »
                »
                »
                »
                7 weeks ago, # ^ |
                Rev. 2   Vote: I like it +6 Vote: I do not like it

                first, we precalculate LCA(binary lifting) for each node & dist from root to each node. this takes $$$O(nlogn)$$$ time&memory. next, for each of $$$m$$$ restrictions like $$$a \space b \space c$$$ we check if $$$dist(a,b) + dist(b,c) = dist(a,c)$$$. we do this in $$$O(logn)$$$ time by finding the LCA for each pair of nodes. if so, the output is invalid.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Shouldn't it depend on $$$m$$$ too?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I suspect that I read the C question incorrectly. Yesterday I wrote this question in a very complicated way, which always showed errors. Today I understood the ac code, but I entered what I was confused about yesterday, and something went wrong. https://codeforces.ml/contest/1586/submission/132311045 This is the code of my wa yesterday. https://codeforces.ml/contest/1586/submission/132313973 This is ac code. But I can't understand the ac code. 3 3 XXX XXX XXX one 1 3 NO

4 5 ..XXX ...X. ...X. ...X. one 4 4 YES I hope someone can help me.

»
7 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

Awesome contest!

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry, i was going to write that on commentary of 748 div.3, but i chose the wrong contest.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello please help me out. Just now I received a mail that my solution of problem 1586B of Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1) conicides with user 1928311. First of all there is no chance of my solution getting leaked to any one because i didnt shared it. Secondly, kindly see the submission time of his solution , I submitted that at 17:21 and he submitted at 17:45. How could I cheat then. Please help me regarding this.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    1. How could I cheat then you shared your solution.

    2. i didnt shared it any proof?

    3. it can't be coincidence, the solutions are very similar.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Arey how could one prove that he/she didn't shared his solution. Its not possible na. Atleast I proved that I didn't cheat. Please help me. Else it will simply demotivate me from CP

      • »
        »
        »
        »
        7 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        have you used an online editor like ideone?

        also for proving that you didn't cheat you need to prove that you didn't share any code, and that is almost impossible

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No I used vscode. Wow got -113 without any fault :).I am impressed by your team and judgements for simply disqualifying a participant for not cheating :) Very good.

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            i am just a cf user not an admin or something else.

            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              So whom should I ask for this problem??

              • »
                »
                »
                »
                »
                »
                »
                »
                7 weeks ago, # ^ |
                  Vote: I like it +2 Vote: I do not like it

                no one.

                Спойлер
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  You must be saying about the template.That is the xor function. I have a discord a server where I have shared my template with others. Many people use that

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  only one small part of the template,

                  also not only the template the rest of the code is also the same.

                  you obviously cheated.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          also for proving that you didn't cheat you need to prove that you didn't share any code, and that is almost impossible. Thats what i am saying na, you just say what kind of proof u need from me that i didn't shared the code. I am giving you.

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
            Rev. 2   Vote: I like it +1 Vote: I do not like it

            There will be a person in charge in each round. You can go to 749 (div1+div2) comments to find out. One person said that he would launch a new ranking again within a few hours or days after the game. I think this person should be responsible for the ranking of the game.

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Hope it can help you

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            just another indian cheater getting caught and still doesn't feel any guilt of it

            132234060 132242274

            It's amazing that he's still not ashamed of himself even with his EXACTLY same code.

            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
                Vote: I like it -8 Vote: I do not like it

              Yes that's because I didn't cheat. I was just explaining my solution to some of my friends in my hostel and one of them simply took the snap of it and wrote it as it is

              • »
                »
                »
                »
                »
                »
                »
                »
                7 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                that's called CHEATING

                First of all there is no chance of my solution getting leaked to any one because i didnt shared it

                and you lied :) Anything else you want to say

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks ago, # ^ |
                    Vote: I like it -8 Vote: I do not like it

                  That's simply because I solved the qs myself n I didn't wanna loose my ratings. Nyways I am guilty for what I did and paid it with my ratings down

            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
                Vote: I like it -8 Vote: I do not like it

              U better see the submission time and then decide who cheated

              • »
                »
                »
                »
                »
                »
                »
                »
                7 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                sharing your code is also called cheating

                are you dumb or something?

                you and your indian friends are all cheaters and you even lied that you didn't shared.

                you all deserves it ^-^

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  it is funny how cheaters lie and think we are stupid enough to believe them.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  yea tru

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Don't solve this contest. Let's play witcher