By MagentaCobra, 3 years 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: 244mhq, AmShZ, dorijanlendvaj, Keshi, czhang2718, 2020akadaver, Magikarp1, Richw818, quantum8, RayLee234, SlavicG, Qualified, Monogon, smax, wxhtzdy, kassutta, namanbansal013, HackerMonk, Ari, PurpleCrayon, FieryPhoenix, Jellyman102, bWayne, H4ckOm, 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. nutella_waxberry
  2. fivedemands
  3. jiangly
  4. peti1234
  5. xay5421
  6. Um_nik
  7. orzdevinwang
  8. yosupo
  9. SHZhang
  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

| Write comment?
»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

see you next banner

»
3 years ago, # |
  Vote: I like it +73 Vote: I do not like it

Note the unusual timings :)

»
3 years ago, # |
  Vote: I like it +73 Vote: I do not like it

challenging problems.

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

    9 challenging problems in just 2:15 hour? isn't that quite less?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping for a good contest :)

»
3 years 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.

»
3 years ago, # |
  Vote: I like it +54 Vote: I do not like it

Clash with Atcoder Beginner Contest :(

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Damn 9 problems in 2:15 hrs

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

Can we participate without being from a Russian speaking country?

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

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

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

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

»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

As a tester, good luck!

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

MAy the OOds be ever in ur favor

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years 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.

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

9 problems,so much!!!!

»
3 years 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!!!

  • »
    »
    3 years 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.

  • »
    »
    3 years 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

  • »
    »
    3 years 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 :(

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

great

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

    Woah cheater has the guts to comment!

    How are you cheater?

    • »
      »
      »
      3 years 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.

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

        he/she adds random comments for avoiding plagiarism check.

        • »
          »
          »
          »
          »
          3 years 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.

      • »
        »
        »
        »
        3 years 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

    • »
      »
      »
      3 years 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!

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

    solve copy paste

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

      I have solved the problems like f, too.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +37 Vote: I do not like it

    .

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

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

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

May Mike be with us.

»
3 years ago, # |
  Vote: I like it +40 Vote: I do not like it
lighthearted meme
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    meme
»
3 years 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)

»
3 years 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.

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping for positive delta and also:

1 манул)

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

Looks like companies wanted to see each other clashes

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

:( Clashes with The International final

»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Accroding to tradition,This Contest might be delayed:(

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

Contest begin, my province: shut down the electricity.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Tree problem in B? why...

  • »
    »
    3 years 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.

»
3 years ago, # |
  Vote: I like it -25 Vote: I do not like it

Div.1 + Div.2 = Div.1.5

»
3 years 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.

»
3 years 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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice C I got it but too late

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What could be the testcase 3 for C?

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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?

      • »
        »
        »
        »
        3 years 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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C XX XX

query : can 1 2 is determinable ?

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

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

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

      Y ?

      • »
        »
        »
        »
        3 years 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!

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

          Ok

        • »
          »
          »
          »
          »
          3 years 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.

»
3 years 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

  • »
    »
    3 years 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

    • »
      »
      »
      3 years 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.

    • »
      »
      »
      3 years 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.

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

is this contest is for High-school ??

  • »
    »
    3 years 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.

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

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

    • »
      »
      »
      3 years 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.

»
3 years 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.

»
3 years 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"

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

    had the same idea, WA pretest 3 :(

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

    I did something similar but got WA on test 3.

  • »
    »
    3 years 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.

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

      Can u explain why do I need to check that?

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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?

      • »
        »
        »
        »
        3 years 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.

    • »
      »
      »
      3 years 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.

»
3 years 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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hint for B please

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

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

    • »
      »
      »
      3 years 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.

      • »
        »
        »
        »
        3 years 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

      • »
        »
        »
        »
        3 years 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.

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

    Make b[i] leaves

  • »
    »
    3 years 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
»
3 years 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??

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

    its correct its my solution too u probably implemented it wrong

  • »
    »
    3 years 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.

  • »
    »
    3 years 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

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

Nice problem set.

»
3 years 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.

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

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did someone see F before? ko_osaga?

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

  • »
    »
    3 years 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.

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

(Deleted)

»
3 years ago, # |
  Vote: I like it -67 Vote: I do not like it

The parallel AtCoder abc223 had better quality of programming problems.

  • »
    »
    3 years 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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Chinese problemsetting forces invading Russia lol

»
3 years 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 :(

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years 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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is C a segment tree problem?

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

    More like dp-problem

  • »
    »
    3 years 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.

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

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +56 Vote: I do not like it
    Solution in 1 sentence
  • »
    »
    3 years 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
  • »
    »
    3 years 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

  • »
    »
    3 years 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

»
3 years 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?

  • »
    »
    3 years 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.

  • »
    »
    3 years 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.

  • »
    »
    3 years 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).

  • »
    »
    3 years 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)

»
3 years 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)

  • »
    »
    3 years 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
  • »
    »
    3 years 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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it
    My solution:
  • »
    »
    3 years 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 :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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 [.] .
      . . . .  . .  . .
      . . . .  . .  . .  
      
      • »
        »
        »
        »
        3 years 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.

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

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

»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Alex_Wei it's Unsuccessful hack for a reason :D

Spoiler
  • »
    »
    3 years 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.

»
3 years 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!

»
3 years 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 ?? :>

  • »
    »
    3 years 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.

  • »
    »
    3 years 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
»
3 years 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

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

    Try to solve 3 problems.

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

      Thanks. I will try.

      • »
        »
        »
        »
        3 years 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.

        • »
          »
          »
          »
          »
          3 years 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? :)

          • »
            »
            »
            »
            »
            »
            3 years 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.

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

          okay.thank you so much

»
3 years 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 :(

  • »
    »
    3 years 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

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

issue solved

»
3 years 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!

==

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

»
3 years 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

»
3 years 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))?

  • »
    »
    3 years 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)

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

      And?

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

        this help's to check if the tree is valid

        • »
          »
          »
          »
          »
          3 years 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?

          • »
            »
            »
            »
            »
            »
            3 years 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)$$$

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

              Can you elaborate?

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years 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.

»
3 years 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.

»
3 years 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.

»
3 years 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.

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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

      • »
        »
        »
        »
        3 years 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

        • »
          »
          »
          »
          »
          3 years 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.

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

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

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

              So whom should I ask for this problem??

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

                no one.

                Spoiler
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years 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

        • »
          »
          »
          »
          »
          3 years 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.

          • »
            »
            »
            »
            »
            »
            3 years 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.

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

            Hope it can help you

          • »
            »
            »
            »
            »
            »
            3 years 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.

            • »
              »
              »
              »
              »
              »
              »
              3 years 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

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years 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

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

              U better see the submission time and then decide who cheated