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

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

Hi Codeforces!

GlowCheese, DeMen100ns, SPyofgame and I are delighted to invite you to participate in Codeforces Round #812 (Div. 2).

  • Start time: Aug/06/2022 17:35 (Moscow time)
  • Duration: 120 minutes.
  • Number of tasks: 6, including at least one interactive problem. Make sure to read this blog and familiarize yourself with these types of problem before the round!
This contest is brought to you by:

Special thanks to:

The score distribution is 500-1000-1750-2000-2500-3000

Hope to see you in final standings!

UPD: We have a small gift for a Vietnamese participant who have the highest score, so if it is you, please DM me after contest. Good luck everybody!

UPD2: Editorial

UPD3: Congratulations to the winners!

Div.2:

  1. RGB_ICPC7

  2. Xylenox

  3. 5cd

  4. Jason2022

  5. Imot

Div.1 + 2:

  1. peti1234

  2. A_G

  3. kotatsugame

  4. jiangly

  5. Rubikun

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

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

As an author, love you SPyofgame

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

As a fan of idol thanhchauns2, I'm really looking forward to participating and solving his own contest. Hope everyone have a great time!

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

problems are great!

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

    I wish every tester from now own takes this kind of oath

    proceeds to get a ocean full of shaved heads

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

    tester này nghiện ma túy

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

    who ask

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

    sorry to say that, but I expect to see you with shaved hair

    And no, in generall contest was good and most problems are really really great, but look at

    This

    Ig it's not OK that I spent more time on A than on B/C/D?

    CMON I SOLVED D FASTER THAN A

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

      I think it is the explanation, haha.

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

        Curious to ask, explanation to what?

        P.s. No negative in this comment, but I really didn't get, sorry xd

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

          I think what make problem A harder than usual is the explanation. If we remove it maybe you will find it easier.

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

            well, after I've read comments I understood one thing

            It's my guilt that I didn't read that either X or Y is 0

            I'm very very sory, problem A was great, and not hard at all, I just should've read statements properly :)

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

              now that makes sense, i can't imagine an expert struggling to solve d2a.

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

                Xd, I'm sorry

                I understood it in way that all coordinates are (x,y) not necessarily zero

                And actually, if I solved A at the time, an CM, not Expert :'( :noo:

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

    Cannot disagree.

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

ᓚᘏᗢ

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

As a tester, I wish u guys could gain the rating :3

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

Finally your contest after 1 year,

Excited to see and all the everyone!!

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

As a tester, hope you guys to enjoy this round.

As a weeb, I recommend you guys Youzitsu (Light Novel) and Gabriel Dropout (Anime/Manga)

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

As a tester, I hate love DeMen100ns

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

As the biggest fan of DeMen100ns and SPyofgame, hydroshiba orz

»
2 года назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится
As a tester...
»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Intentionally skipped testing this round, hope this one will be as good as previous one

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

The white text is painfully obvious on mobile

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

My best effort in this project is breathing instead of making instant-rejected problems (")>

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

Finally your round, obviously I will take part in it

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
  • "Last but not least, you for your participation and being WA, then dropping at least one color :P" It's the best easter egg I've ever seen :P
»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

amogus

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

orz

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

why this announcement is published 6 weeks ago?

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

    Probably because that's when it was announced? It was only added to the Home page now because it's the next contest.

    There are three other contests scheduled that should also be added to the Home page when they're up next.

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

nice :>

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

As a tester, i worked with authors who are talented high school, college students, they had to make a lot of efforts to prepare problemset during months, some problems were rejected or removed to have the best problemset for contestants. So no matter what you feel about this round, plz upvote this contest to encourage young Vietnamese CP-ers to contribute global CP community. Finally, let's enjoy our problems and hope all you guy get good ranking.

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

    yeah, you are right. Everyone who has made efforts to this contest deserve encouragement!

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

By the way, the kitty on the promotional picture is really cute (>w<)

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

Picture looks really good,hope it will be a nice round :)

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

I hope that C, D will not be as difficult as in the previous contest

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

Hope I can reach Master after this round! Good luck to everyone!

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

Seems like nobody notice that our coauthor, DeMen100ns has two colors in the announcement.

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

Hope everyone have fun!

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

Most colourful blog I've seen in a while :3

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

image-2022-07-06-T09-36-54-205-Z

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

Watch as people upvote me just because I am a GM

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

04bf86d84b4883c8e7e6e94ed23606ff

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

Wish I can solve at least one problem!

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

Good luck! love you SPyofgame

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

Again a contest with a huge gap between B and C :(

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

i would personally prefer two minutes later, but ok

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

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

Is this rated for me? Up to 2100 or up to 1900

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

C 1750 looks scary :(

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

I will try to become Expert in this contest!

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

According to the points distribution, I guess C is going to be a good question. So what do u think ?

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

I will become specialist this contest!!!

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

Good luck for everyone ❤(✿◕‿◕✿)❤

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

As a participant, I wish myself good luck in advance

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

One of the authors is in a really bad health situation right now. To all participants, please shows your respect to him by solving as many problems as you can, we all want him to overcome as soon as possible.

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

| Last but not least, you for your participation and being WA, then dropping at least one color :P

B-but we can't drop any more colors

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

I guess the interactive problem is problem C because it has 1750 points :) Is my thinking correct or not ?

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

    As far as I know, ABC are never interactive since they only should require basic data structures and math knowledge sometimes (and their statement should be clear to everybody), the interactive problem will probably be D or F (my opinion :)), it's just because authors probably came up with this C, but they think it's a bit more difficult than usual, so they made it 1750

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

All the Best @EveryOne !!

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

Hope I become pupil in this contest

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

Stuck on problem A :holyfuck:.

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

b and c are very good problems!

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

How does a blue coder solve f in 5 minutes? Jiangly didn't do it for 40 minutes.

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

    Never judge a person by his color

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

    Sorry I do suspect std leaks, but I have no ill intentions, I'm just speculating how he cheated.

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

    Now I have almost enough proof that he is cheating. 1. He has two d and e submissions in the contest, with only a dozen seconds between them. 2. After passing the pretest of d, he submitted it again after a minute, and then wa2. This is obviously cheating by multiple people solving the problem at the same time, writers please check him. [user:thanhchauns2][user:DeMen100ns]

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

How to solve E?

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

    2Sat, but you don't have to do a whole offline incremental SCC bs, instead you only need to maintain a DSU, check if the next restriction can be satisfied, if so change the matrix accordingly, otherwise ignore it.

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

Video Solution for Problem C.

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

Hi,

I solved problem C at 1:14:31. But later i saw the code and felt that it might fail system testing as i used int instead of long at one place so i submitted again at 1:47:33 and as of now both are showing pretest passed. But i am getting points according to the 2nd attempt. If after system testing my 1st accepted solution does not fail so will i get score according to my 1st submission or 2nd submission?

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

    During system testing, your first submission will be skipped and your second submission will be considered. Also you'll lose extra 50 points for resubmission.

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

      ok thanks,

      Due to unnecessary resubmission i lost around 280 points today.

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

        I wouldn't consider it unnecessary if you personally had doubts about your solution. If you couldn't assure yourself that it would pass, then it would have been risky not to resubmit, since you would have lost a lot more points if it failed. Better to resubmit early than to wait until it gets hacked, or worse, until it fails system testing.

        I think the real lesson is that you should really examine your code carefully before the first submission, and that if you have some doubts later on, you should think carefully about whether such concerns could actually prevent acceptance. If you are unable to clear such concerns, then I think you should resubmit without regrets, even if you realize after the contest that it was okay. Hindsight is 20/20, after all.

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

    According to Codeforces Contest Rules

    If a contestant submits several times a problem's solution that passes all pretests, then the last solution is considered as the contestant's verified solution for this problem. All other solutions will be considered as unsuccessful attempts.

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

    The rules are that a resubmission will incur the -50 penalty, regardless of whether the former would have passed system test or not. It's unfortunate, but that's how it is.

    While there is no way to know for sure whether your first submission would have passed the system test now, I think int should be perfectly fine, because the largest square that needs to be considered is at most $$$2 (n - 1)$$$, which is well within int limits (unless you did something really crazy in your solution).

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

Amazing contest!

I am very happy because I solved 3 problems (A, B and C), unfortunately I solved them too late with 2 WA on pretest 2 verdicts. Does anybody know some real tips on how to solve problems faster and with less wrong submissions?

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

Great problems. (Specially D) How to solve D? Did anyone get AC using randomized algorithms, it would be great if someone could share some insights.

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

    hint: you can determine the winner of the four using only 2 questions

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

    When you query four consecutive people, it only takes two queries to figure out who the winner is out of the four people. Maintain the array of winners from the last iteration, repeat the two queries per four people, until you have either two people, or a single person, then we know the winner. The number of queries used is the sum $$$2^{n-1} + 2^{n-3} + ... + 2^1 (or~2^0)$$$ and it is easy to see that this is below the query limits

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

      Sad I didn't know what to do with this information, I figured out to find a winner among four people in 2 queries during the contest. Thanks

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

what is the observation for b? time is very tight for c can an o(n*k) solution pass main tests? where k is number of perfect numbers less than 2 * 1e5?

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

For problem D the time limit was so tight using java it passed with C++ but cost me 20 minutes to debug in C++ since I don't use it much, couldn't you make a larger time limit for java? other than that the problems were really good.

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

As a Candidate master, I even can not solve C, and I got the worst standing since I sign in Codeforces... sad

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

    C is worst problem in long time... we have to see simple but completly random stupid observation. Like christmas riddle for pre schoolers.

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

      The fact that there always exists a square between $$$[n, 2n]$$$ is not something I would consider to be stupid at all... In fact, this is not only easily observed from thinking of small examples, but it's also easy to prove.

      Similarly, the observation that $$$(a + b) = (a + i + b - i)$$$ is extremely trivial.

      Neither of these are stupid. It does require some mathematical maturity to realize that these two observations would lead to an exact solution, but there is no randomness or stupidity involved here.

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

      It's not a stupid observation. You can do strong induction and claim that if you can build array using numbers (0,i), for each 0<=i<=n, it's also possible to do so with numbers (0,n+1). This is due to the fact that there's at least one perfect square between i and 2*i. Now you have construction using the given prime for finding (n+1)-th element, and thus can fill the suffix (i,n+1) in increasing fashion, and due to induction hypothesis we can build the remaining part.

      It's a cute problem imo.

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

      I think both C&D are tricky, agree with that the observation of C is quite random. Again, sadly I didn't pass any of them... This time I may lose more than 150 rating ... :(

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

    As a Specialist, I even can not solve B, and i got the worst standing since i sign in Codeforces... sad

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

      :( I am too sad and I can not fall asleep. This contest exposed my problems, I'm an idiot in number theory

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

        You are very good sir ! I am an idiot in everything ;((((((. I think I will quit cp and hire at foodpanda after i get my bike fixed

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

First time I solved pD on div.2!

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

Has anyone Accepted the problem-D using Java? I have tried reusing array[1 << 15] but the TL seems too tight.

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

B is very similar to a USACO problem

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

    I solved Air Cownditioning for fun a few days back and was able to solve it using that.

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

Sad for Python users — D was very difficult to complete within the time limit.

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

what's wrong with this approach for D?
get winner of 1-2 pair, now we covered participants up to covered=2, then go iterating over next participants from covered+1 to covered*2. if someone won more matches then it's a winner for range from 1 to covered*2. now change covered=covered*2 and repeat until end.
somehow I get WA

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

Is the idea for $$$E$$$ correct? I got WA2.

Create graph with $$$n$$$ vertices. Iterate over all $$$i < j$$$ and if $$$a[i][j] < a[j][i]$$$ add edge with $$$xor = 1$$$, meaning, we have to swap either $$$i$$$ or $$$j$$$ cross, if $$$a[i][j] > a[j][i]$$$ add edge with $$$xor = 0$$$, meaning, we have to either swap both $$$i$$$ and $$$j$$$ cross, or not, if $$$a[i][j] = a[j][i]$$$, don't add edge.

All edges have time of appearing. We have to satisfy the greatest prefix of such edges. Let's do binary search. We fixed subgraph with times $$$< x$$$. We have to set to all vertices value 0 or 1, to satisfy all edges' xor. First set all vertices undefined. Iterate over vertices, if we see undefined, set to it any value and do dfs. Dfs only walks on available edges, if it sees undefined neighbour vertice, it sets correct value to it and goes to it. If it sees neighbour vertices, such that is doesn't satisfy edge's xor, then we can't satisfy this prefix of edges.

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

    Furthermore, seems I solved $$$D$$$ in $$$\frac{1}{3} \cdot 2^n$$$ queries. What is expected to do with 2 times more queries?

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

    Notice that you have to repeatedly do this process as after the greatest prefix and the first "unsatisfiable restriction" , we may still have restrictions that can be satisfied, so we would probably get a $$$O(mn) = O(n^3)$$$ solution

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

    The optimal solution is not neccessaty formed as a prefix.It means you can choose "not add edge i" and "add edge (i+k)" at the same time.

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

167298607 why this got TLE ????

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

I have probably used all of my luck for the next few months: Screenshot-2022-08-06-093710

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

I loved this contest!

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

D was reallllly difficult to complete within the time limit for Python user!!!!!!!!!!!!!!! It's unfair!!!, please rejudge it!!!

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

    You know that the input and output in Python is quiet slow, even my submission is the same as the tutorial , also got TLE, really unfair!!

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

      All the python user that pass the contest, the time is 1980ms+, quiet strict

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

    sad, always python users have to wait to increase to the next tier because of the RLE or TLE questions which happens so frequently. It's always absurd optimisations to made it pass. My friend has been waiting one year for expert and he couldn't hit it again today because he TLEd on D and he got a -60 instead, he's 5 stars on codechef (almost 6 stars) and 2450 on LC

    I really feel you

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

      Thanks for understanding!! Always Python user are not be considered in the CP. in the future if I have the chance to hold a contest, I must set different time limit restrict for different programming language, hope one day it can make true

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

        In leetcode yesterday I made 8 different TLE on O(26*10^5) algorithms.Top down was giving MLE, bottom up with O(n) space was giving TLE as well,I was so surprised that I submitted the same code multiple times, then finally optimised it to O(26) space and it passed

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

          Once, i took part in the LeetCode weekly contest and met the same thing, really sad

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
  • For D Problem, I applied the same logic as mentioned in the editorial, but i am getting Wrong Answer.
  • I have tried my best but I am not able to figure out the mistake.
  • Can someone please help me to figure out the mistake? 167302006
  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    same bro i am also not able to find my mistake.

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

    I'm not sure whether I understand your code correctly, but I think that in a scenario where res is not 0, you have to move 2 guys to next level, but you're moving only one

    • »
      »
      »
      2 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится
      Yes,I think I am doing that only.
      
      For 4 players, I am always querying for the 1st and 4th one.
      
      if(res == 0): move {2nd, 3rd} up
      else if(res == 1) move {1st, 3rd} up
      else move {2nd, 4th} up
      
      Please correct in case there is anything wrong in this.
      
      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yes its true, but this will make queries more than it's allowed

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          • Actually, it won't exceed the queries.
          • The Logic was correct, but there was a slight mistake in the implementation.The order in which I am pushing in a step will also matter, just made this change and I got an AC. 167311506
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Take a look at Ticket 16001 from CF Stress for a counter example.

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

167304705 why is this got TLE???

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

what is wrong in my approach for problem B https://mirror.codeforces.com/contest/1713/submission/167293528 Approach inserted all the elements of the array into the set if the size of set is equal to the size of array this means that the all the permutations have cost greater or equal to array therefore YES

if not then i m checking the position of duplicate elements if all duplicate elements are adjacent this means the permutations of it has greater cost so the answer is yes otherwise the answer is no.

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

    The NO-instances are not characterized by duplicate elements. But rather, they are characterized by the transition from decreasing to increasing. For example, the array [2, 1, 3] should output "NO" (it requires 4 operations, whereas [1, 2, 3] only requires 3 operations), even though there are no duplicates.

    The issue with decreasing->increasing is that the two sides cannot be decremented at the same time once the center becomes 0, whereas a sorted/reverse-sorted/increasing->decreasing array can ensure that every operation hits all non-zero elements at once.

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

Thanks for the great contest :) !!!! Really loved all the problems and especially problem D And a great rating increment :)

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

Great problems. To be fair, I raged pretty hard about the time limit being way too tight on D (or there being way too many queries for an interactive problem), but other than that, great set :)

Screencast and solutions to A-D will be available on my youtube channel as soon as youtube finishes process it.

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

the pretest of B is shit!

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

In problem B there should have been a pretest where you needed to use long long int!

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

    What? You don't need to use long long int?

    I easy solved it just with ints: 167240602.

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

      There is a solution where participants want to check if $$$\sum(max(0, a[i] - a[i-1]))$$$ is equal to $$$max(a[i])$$$. In fact, this is also a correct solution but it may require a $$$sum$$$ variable to store big number which can only fit $$$long \ long \ int$$$.

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

Balanced contest! Edit: I got expert back!

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

In problem D, if n=6, can we make 43 queries?

As, (2 ^ 7)/3 is around 42.67

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

can someone tell me what is wrong with my B solution: https://mirror.codeforces.com/contest/1713/submission/167256508 . i've been trying to figure it out for the past 3 hours :)

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

The best contest of 2022! Orz thanhchauns2

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

Interesting E. I come up with it just after the contest finished:(

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

Any particular reason for C being of 1750 points?, I think it was not that hard and could have been of 1250 or 1500 points.

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

Really good questions. Thanks for the contest

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

Use greedy strategy, problem D could be solved within 2^(n-1) queries?

this submission https://mirror.codeforces.com/contest/1713/submission/167314546 assert queries * 2 less or equal 2^n

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

In problem D, In the test case given, can't 2 win the contest?

1 2 3 4 5 6 7 8

2 4 5 7

2 7

2

The final win array becomes = [0, 3, 0, 1, 1, 0, 2, 0] Can someone explain this.... any point I'm missing?

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

    Yes, it can. But it gives the right answer 7, so it is accepted, even though its logic may be nonsense at all, i.e. the tester only cares about the final answer, rather than the logic behind.

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

wish there were stronger pretests :c

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

Expected Brood War themed problems.

thanhchauns2 didn't deliver.

As a consequence, I had a terrible performance. Lowest rating in almost 2 years :(

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

    Unfortunately, all problems with Brood War theme is either saved or removed. The set is entirely different from the first. I feel so sorry about this.

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

Ваше решение 167238238 по задаче 1713B значительным образом совпадает с решениями других участников и находится в группе одинаковых решений altgifted/167238238, vasily312/167281265. Такое совпадение является явным нарушением правил. Отметим, что непреднамеренное утечка тоже является нарушением. Например, не следует пользоваться ideone.com с настройками по умолчанию (публичным доступом к вашему коду). Если вы имеете неоспоримые доказательства, что совпадение произошло по причине использования общего источника, опубликованного до соревнования, то напишите комментарий к посту о раунде со всеми деталями. Подробнее можно прочитать по ссылке http://mirror.codeforces.com/blog/entry/8790. Такое нарушение правил может являться основанием для блокировки вашего аккаунта или других штрафных санкций. В случае повторения нарушений, ваш аккаунт может быть заблокирован.

MikeMirzayanov

Что делать в такой ситуации? Я вообще без понятия что это за человек, исключено чтобы он хоть как-то получил доступ к моему решению, я использовал локальный ide

Могу только предположить, что это случайное совпадение – шаблонная обертка и решение в 2 цикла

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

Shit interactive problem