interlude's blog

Codeforces Round #745
By interlude, history, 3 years ago, In English

Hello Codeforces!

CQXYM and I are glad to invite you to Codeforces Round 745 (Div. 1) and Codeforces Round 745 (Div. 2), which will be held on Sep/30/2021 13:15 (Moscow time). Note the unusual time of the round.

Each division will have 6 problems and 2 hours to solve them. All problems were written and prepared by CQXYM and me. The round will be rated for both divisions.

We would like to thank:

This is our first round, and great efforts have been put into preparing this round. Were you to kindly participate in this round, we would be very grateful and hope you will enjoy it.

Good luck!

UPD: Here are the scoring distributions:

Div. 1: $$$500$$$ — $$$1000$$$ — $$$1750$$$ — $$$2000$$$ — $$$3500$$$ — $$$3500$$$

Div. 2: $$$500$$$ — $$$1000$$$ — $$$1500$$$ — $$$1750$$$ — $$$2500$$$ — $$$2750$$$

And we would also like to thank Um_nik for testing the round.

UPD2: Editorial is out!

UPD3:

Winners

Congratulations to the winners:

Div1:

  1. nutella_waxberry

  2. maroonrk

  3. Radewoosh

  4. Karry5307_AK_NOI2024

  5. hos.lyric

Div2:

  1. _ywy_c_asm_

  2. lpf666

  3. Fuzen

  4. leap_frog

  5. OguriCap

  • Vote: I like it
  • -1232
  • Vote: I do not like it

Comments Comments (464)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it -155 Vote: I do not like it

As a tester I would encourage you to participate in this round and assure you that the problems are interesting and good .

Update :- My review to testers

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

Here it is!

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

Mathforces?

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

Another Chinese round and friendly time for Chinese! Looking forward to great problems and having fun!

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

Sad, why isn't Monogon a VIP tester :(

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

    I'm only moderately important this time.

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

    What? 1-gon's comment didn't hit 100 upvotes in a day?? Impossible!)

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

This time is good for me.

Orz CQXYM!

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

I hope.

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

I don't have anything against Chinese rounds, but... really, morning on a weekday?

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

    Probably people in different time zones exist.

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

    In China it is 6:05p.m. on the day before the National Day holiday. You can imagine the experience of participating a CF round after school :)

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

      But (maybe?) most middle school students have to stay at school and study at night.

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

        It often happens on weekdays. But if tomorrow is holiday, students can go back home in the afternoon.

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

    I think that it's because the National Day holiday in China is coming.

    However authors don't know 6 p.m. is even worse than 10 p.m. for many Chinese because most of schools end at 9 :(

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

      However we must take the fact that ICPC World Final will be held today into consideration. Thus we choose 6 p.m. over 9 p.m.

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

Rare time....but maybe just right for Chinese contestants like me. I'm a little EXCITED. Hope all of us can enjoy it!

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

I finnish school 5 minutes before the round, can't join, but I wish those who read the greatest of luck.

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

    I managed to convince the teacher to let me compete at school.

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

Big thanks for the time of the round from Asia! :)

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

Great, 3:05 AM.

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

    i guess that's an i for an i for us having to participate from 10:30pm to almost 1am before...

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

interlude I think we need to update this blog to make this appear on top of the div.3 contest. Many people might not see it. Especially the unusual start time of the round. I didn't see this blog existed. Because the first post from the top was round 744. thanks for considering. :) good luck to the people who are participating.

→ Reply
»
3 years ago, # |
  Vote: I like it +72 Vote: I do not like it
lighthearted meme
→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it -15 Vote: I do not like it

    .

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it
    Hahahahhahahhahaa!!!
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You High on Weed . :) __ | | | | | | | | ( | | | | )

      Hope you Understand my feeling.

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

      That's not a good idea to play jokes like this on the Internet. We can sure that there was something wrong with the education you get from your parents.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +66 Vote: I do not like it
    Meanwhile me
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it -26 Vote: I do not like it
      Hahahahhahahhahaa!!!
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -27 Vote: I do not like it
        Hahahahhahahhahaa!!!
        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it -26 Vote: I do not like it
          Hahahahhahahhahaa!!!
          → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Imagine having school online, and not offline

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

      Now that the contest is over, are you happy with your decision?

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

        i guess yes as he got a very good rank in this one

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

    I have a test in my class today that completely overlaps with the contest timings. Cant skip them even if I want to

    :sobb:

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

Another great round!! Hope I can do better than before in it.

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

Hi there. Could the contest be at 18.35?

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

    The round authors are Chinese; I assume starting at 22:35 is not comfortable to them.

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

Hoping to become Pupil after this round...Best of Luck everyone!!

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

As a Chinese,I usually leave school at 6:30 PM,so I cannot enjoy this round :(

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

Is 1900-2100 no longer in Div 2?

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

    People rated <2100 can participate in div2, when it is div2Only round(so no parallel div1), but when there is a parallel div1 round, 1900+ have to participate there. It has been like this for a long time

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

A way to increase contribution from 0 to 100:

0-20: leave stupid comments

20-40: write a blog on how to increase contribution from 0 to 20

40-60: write a blog on how to increase contribution from 20 to 40

60-80: write a blog on how to increase contribution from 40 to 60

80-100: write a blog on how to increase contribution from 60 to 80

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

Big thanks for the friendly time of the round:)

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

    Actually, 9 p.m. is better than 6 p.m. for Chinese students.

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

My first div2 round here. Hopefully it doesnt go downhill. fingers crossed. I like this time slot :)

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

From contest authors and testers, I'm waiting really good contest!

→ Reply
»
3 years ago, # |
  Vote: I like it -118 Vote: I do not like it
Greeting all chinese people!
→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it -27 Vote: I do not like it

    Idk what's up with everyone, so retracting it for the better!

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

    I think the content you posted is not appropriate, because we all know that the Great Firewall in Mainland China blocks almost all "user-generated content" websites, and codeforces as a "user-generated content website" is not blocked by it because There is very little political content on codeforces. If you post more content in this area, the result is likely to be that codeforces is blocked by the Great Firewall of China. As a result, it will cause great inconvenience to users in mainland China. They need to cross the Great Firewall to access codeforces.

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

      Good.

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

      However, according to some netizens in the QQ group Universal OJ Users, almost everyone in China mainland who use Codeforces can across the Great Firewall

      But anyway, I don't think any political content posted on codeforces is appropirate because codeforces is a website for people who love programming. I think whether it will make codeforces blocked or not it's not good to post content which is not about algorithms on codeforces

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

      Although I heard some netizens say, and I also think whether Codeforces is blocked or not doesn't matter to many codeforces users, I think after all using websites not blocked is more convenient.

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

    Lol, this is pretty good, don't know why it's being downvoted

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

can anyone tell me what is the process of penalty in DIV 2 round

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

    Technically, there are no 'penalties' on time count. But yes, you get less points if you solve a problem after incorrect attempts.

    Each problem is assigned points (e.g., Problem A in this round is 500), the faster you solve a problem, the more points you get. The amount of points you can achieve gradually decreases over time.

    Problem A points deteriorates at a rate of 2 points per minute (you get 498 points if you solve after 1 minute, 496 points if you solve after 2 minutes, 494 points if you solve after 3 minutes and so on)

    Plus, every incorrect attempt costs you 50 points.

    Now let's see, if you solve that problem A after 10 minutes on your 2nd attempt, you get (500) - (10*2) for 10 minutes to solve - (50) for one incorrect attempt = 430.

    If you solve that problem A after 15 minutes on your 3rd attempt, you get (500) - (15*2) for 15 minutes to solve - (50*2) for two incorrect attempt = 370.

    Additionally, the minimum points you get on any problem is lower bounded by 30% of the max points on that particular problem. e.g., irrelevant of how many incorrect attempts or how much time, you will get a minimum of 500 * 30% = 150 for that problem A.

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

Round delayed by 10 minutes

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

deleted...

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

Time added 10 minutes!

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

contest extended by 10 min!

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

Why this sudden addition of ten minutes in starting the round??

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

Hopefully the delay doesn't signify an unrated round.

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

now what to do with 10 min of my life??

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

    Think about what to do with 10 min of life

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

how many point i need to join to div 1 ???

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

I hope it'll be the only problem of the contest.
Wish all the best!!!

P.S. The "problem" here doesn't mean the problems that we're going to solve in the contest.

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

This doesn't really matter, but why would you use "obsidian" instead of "black"?

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

If you can't write a nice problemset for cf, just move the problemset to other websites.

Terrible contest.

edit: Chinese slang

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

    ?______?

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

      It means he hates the idea provider due to hard problems, but it may be Chinese slang that is very disruptive and not appropriate to show in public.

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

First time not being able to solve (or not wanting to implement such an ugly solution for) even the first problem. Might just be me, but I think this contest needed a lot more tuning.

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

    Thought it was one of best contests I competed in, besides B and C out of order. Finally some actual implementation and more ideas than just greedy/math with one for loop required...

    If you can't solve a 30 line solution due to implementation I'm not sure you should be in div1. I've long said there is severe lack of implementation skill for most low div1 users and below.

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

Hardforces (: (at least for me )

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

Coding is very hard

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

div.1 too hard for me :(

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

Why would you write statement like this:

"and the diameter of the graph must be less than $$$k-1$$$?"

Couldn't you write "diameter of the graph must be less than $$$k$$$"?

Or even better, "diameter of the graph must be less than or equal to $$$k$$$?

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

    For real, my code was so messed up I had to rewrite because I got confused in the middle.

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

I'm sorry but i am happy because today it's not only me who can't solve a single problem.

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

How to unregister?

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

Not my cup of tea...

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

Damn bro you didn't have to kill us with those problem statements!

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

Man!! explain me the problems. Cant understand anything from the statements

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

its my 2nd chinese round and i find it harder the usual div2 coz i can solve avg 2 problem but in this round i can't do even A. Chinese loves maths too much ≧ ﹏ ≦

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

only 3.7k submissions to problem A, btw WAonpretest2forces :(

→ Reply
»
3 years ago, # |
  Vote: I like it +72 Vote: I do not like it
At least I'm not alone, here we are :')
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Getting demoralized when not able to solve any problem.

    then coming to comments-->turns out to be a natural therapy

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

Not even able to solve one quest, very tough round.

but atleast doing no submission won't affect my rating ^-^

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

The wording of some of the problems are hard to understand :(

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

In the last 12 rounds held over the past 3-4 months, this is the only round where I had to spend ~10 minutes on both A and B just to be able to interpret properly what the question wants to say, never mind attempt to solve them. Statements were weirdly put, and maybe difficulty wasn't properly calibrated going by the meagre amount of submissions ~4k for div2 A even after an hour.

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

one silly mistake costed 4 penalties on problem B :(

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


Thanks a lot for clarifying this, before the round I was worried that my solution might also be tested on a negative number of test cases.

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

I am even not able to solve B this time, my brain exploded thinking of it :(

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

A flaw in the rating system exposed brutally by this round: in div 1, those who do manage to solve A, but do so late and/or with penalty attempts, will see their rating fall significantly, while those who bail out completely on solving A will see no change to their rating.

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

    that's why A should always be comparatively easy in both divisions, can you imagine less than 6k participation in div2 :(

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Me on this contest be like:
→ Reply
»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Damn, That's the hardest A and C I've ever seen

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

HardForces :(

UPD: Sad, Got FST on Div.2 B :(

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

It`s really good, but is so hard:(

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

20000 registers 6000 contestants hmmm makes sense

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

Didn't participate in a Div. 0 before, but today i did.

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

Is O(N^3) the intended solution for Div1 A or are you expecting O(N^2)?

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

    $$$O(N^3)$$$.

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

      Amazing. I had an O(N^3) time with O(N^3) space initially which got MLE.

      Optimized it to O(N^3) time with O(N^2) memory and still got TLE.

      Tried optimizing it further and got WA.

      What a waste of 2 hours for me.

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

        I solved it O(N^3 * 16) it gave me TLE but i break when i find solution with value greater than 16 and passed the pretests

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

        Atleast you were writing codes. I was just crying for 2 hrs T_T

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

    Yes, my O(n^3) passed

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

    I think O(n^3)

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

Are the CF div2 rounds are getting harder or me getting dumber?

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

    You just happened to be in the wrong contest at the wrong time

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

A contest with really high difficulty...

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

So is there anyone tell me how to solve Div.1A/Div.2C. I got WA on pretest 18 :(

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

    You can discover the property that the answer will not be more than 16. and just do it in brute force. it will be O(n * m * 16 * 16). Hint : try to use the number larger than 16, maybe 17.

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

      I found that but failed to have further a further thought. Could you please tell me what the (16 * 16) is?

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

Any O(nlogn) solution for Div1C/Div2E? I only came up with sqrt decomposition XD

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

    wasn't time limit a little too tight for sqrt decomp? :(

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

      O(nsqrt(nlogn)) should work for n=100k.

      Example: 1540D - Инвертируем инверсии

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

        It has 5 sec limit. 1 sec limit kept me under the impression that nsqrt(n) is being punished here. anyways my fault :(

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

        Not in this task, not with 1 second time limit, IMO. 1.5 seconds would probably be enough.

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

      I passed system tests with $$$O(n\cdot \sqrt{n}\cdot \log{n})$$$.

      I used a fenwick tree for big values of $$$x[i]+y[i]$$$ instead of just maintaining when to add or subtract something.

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

        Weak systests :/ But I see that this solution was already hacked after contest. My solution with FT was a bit too slow too.

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

    I can only come up with $$$O(n\sqrt{n})$$$ solution too.

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

    The TL may be a bit tight for O(N sqrt(N))

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

      In fact the constant of the solution is very small. I think even $$$O(n\sqrt{n}log_n)$$$ solution can also pass.

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

        And O(n^5) can pass B with some optimization...

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

          $$$O(n^5)$$$ is the expected complexity.

          In fact you will find the constant is extreme small. A lot of state is useless.

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

            That's really unexpected.. I thought author may have come up with something smarter to get $$$O(n^4)$$$ solution and set $$$n=100$$$ to cut $$$O(n^5)$$$ one..

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

              In fact there do have a solution works in $$$O(n^3log^2n)$$$, but it's too difficult for D1B.

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

            Well, that's surprising. Why didn't you set $$$n \leq 50$$$? It would be much easier to understand that the solution is fast enough and it's worth coding. Was it that important to fail $$$O(n^6)$$$ solution?

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

              Um_nik played these games.

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

              Sorry but I didn't come up with any $$$O(n^6)$$$ solution.

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

                Then my question remains: why $$$n \leq 100$$$? Only to make some people not implement a correct solution?

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

                  "In fact the constant of the solution is very small." -interlude

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

                  I understand that the solution is fast enough. It would still be with $$$n \leq 50$$$. And this fact would be clear before implementing.

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

                  Just because the $$$O(n^5)$$$ solution can pass the task and it runs very fast. In fact you will find that the answer will be 0 if $$$m,k$$$ is larger than $$$\frac{n}{2}$$$.

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

                  Not always, my $$$O(n^5)$$$ solution got TL.

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

            Are u serious? Only because of this, I didn't code the solution and thought for an O(n^4) solution for almost 1.5 hrs. And the constant isn't that small, recursion won't pass easily without optimizations (returning wherever you can).

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

        However my O(N sqrt(N)) solution didn't pass.

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

      I failed on both BC for TL

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

        I think your solution for C is slow because of "cin and cout" .

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

          I'm sorry but as a matter of fact,coder's submission has got another TL after replace cin/cout with faster IO streams. Isn't it obvious that this failure it due to implementing or Time Limit but not IO ways?

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

          You are right..my bad

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

    O(nsqrt(n)), you can operate trains whose x+y>=sqrt(n) and whose x+y<sqrt(n) in different way.

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

Perfect! Problems are challengable and of benifits. especially C, it`s great on both Thinking and Realization. All in all, great round.

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

Ooh man! one of the toughest A in div 2!!!

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

    maybe you can just look at sample test cases to find the pattern without thinking much or proving anything . At least that's what I did XD

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

      I figured it out with PnC but still I would say it shouldn't have had been an A problem, maybe B or B1 if possible!

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

So difficult.

UPD : also fstforces.

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

Why is the diameter of the graph given as <=k-1, why not <=k ?

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

    It's < k-1, My guess is just to add more confusion.

    it's like let's make the contest very hard and confusing for the people who decided to participate at 3 AM as they already have a brain fog at this time :D

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

Am I the only one who has a bad feeling about system tests?

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

Well at least the judge queue will be short lol

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

Please, if you will write a round again in the future think about the quality of statements twice before. Some things were not very clear, like in div2 B where you should have specified strictly less, as you did while the round was going. Also, talking about B, it wouldn't be a bad idea to also write in bold important words, not just numbers and variables(here I'm talking about the word CONNECTED); you can see in other past problems that this is sometimes done, especially for important conditions like the connectivity one in B(for example for saying that all the numbers in an array need to be different). One last thing about this problem would be the limits for k, like were those special cases of k <= 1 really that important to be placed in the tests, ore are they even in the tests?

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

    I am really confused why the diameter of the graph must be strictly less than k−1. other than k, it causes unnecessary confusion.

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

hardforce

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

I feel like today's contest is suitable for Div 1.5 and Div 0.5

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

The round had nice problems (I read only div1A-C tho), though ridiculously hard. Could've easily been split into two separate div1 rounds with some easier, filler problems. I want to express my deepest sympathy to all div2 participants, who had those super tough problems given as C-E. Div1A should've been div2E IMO. To the authors, you did very good job with inventing interesting problems. Only that you underestimated their hardness and the overall contest turned out too hard.

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

    That is the job of coordinators and testers but I don't know how can they all agree to serve all these problems together.

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

Some solutions for Div2 B will fail for this test: n = 1, m = 0, k = 1

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

    is it NO ?

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

      Yeah, some solutions didn't consider that the given diameter could be negative as well.

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

        In first sample he told u diameter of the graph is zero, its obv. not strictly less than 0

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

        Although I honestly don't see why the authors would want to make k start from 0 and not 1.

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

        I felt,The definition of diameter is valid only when there are atleast 2 vertices. Is this assumption wrong?

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

Honestly how to iterate on this map in c++ for Div1 C ? map[(xi + yi)][day % (xi + yi)][xi].push_back({st_j, end_j}) Plus is it really the solution ?

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

    Just use map.insert.

    The solution is about O(n sqrt m)

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

Maybe the pretest is too weak?

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

system testing is super fast today!

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

Despite so many testers spanning across different ratings, a pretty unbalanced round.

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

Saw a pattern in the ans of A for n = 2 , half of the total-permutations and it actually worked for larger n

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

You could bold "connected" in B :/

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

k = 0 on problem B. Damn you guys got me!!!

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

Awesome difficulty Forces+FST Forces = Codeforces Round #745

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

Did someone mistakenly swap B and C?

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

    Before the contest I thought B is easier but it turns out that I was wrong.

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

Who actually proved their solutions for A lol

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

    I thought of something like, if a permutation is valid, it's reverse is always invalid. So half would be valid and half invalid

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

    Proof by symmetry is valid, and very simple.

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

    I think you can make a one-to-one mapping from valid permutations to invalid ones; let's say you want to count permutations which have exactly $$$n$$$ indices such that $$$p[i]<p[i+1]$$$; it's not hard to show that by negating all numbers and then adding $$$2n$$$ to all of them, you are going to have a permutation with exactly $$$n$$$ indices such that $$$p[i]>p[i+1]$$$ (note that we don't have any repeated numbers, so this condition is the exact opposite of the one we consider valid.) Let's assume $$$\Pi(i)$$$ is the count of all permutations that have $$$i$$$ consecutive increasing pairs, and $$$\neg\Pi(i)$$$ the same for decreasing pairs; we know a pair is either increasing or decreasing; so we have: $$$\Pi(i)=\neg\Pi(2n-1-i)$$$; so we have: $$$\neg\Pi(i)=\Pi(2n-1-i)$$$; therefore, we have $$$\sum_{i=0}^{n-1}\Pi(i)=\sum_{i=n}^{2n-i}\Pi(i)$$$; I think by now you can see why $$$\frac{n!}{2}$$$ works in this problem.

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

What is test 4 for problem Div2B ?

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

I came up with a (n^2)m solution for Div1 A but it gave TLE. Is there a more efficient solution?

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

    I also have this exact complexity and it passed. I used only vectors and pairs, maybe you used some more complex data structures?

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

      Hmm. Seems like the constraints were tight. I see many solutions giving TLE in the system test.

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

But it actually feels good to see a tough round now and then.

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

How to solve Problem C ?

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

hardforces + clumsyforces + (1.5 + 0.5 ) forces +system test fail forces + ....

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

It is so reassuring to see that the problems were hard for everyone! Nevertheless, they were also really engaging.

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

important rule : don't join chinese contest LOL

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

FSTForces :(

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

shitty contest

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

I think the pretest in Div 2 B could have been a little better. Other than that, contest had really interesting problems, except C. I didn't like C, as the only solution that I thought of was implementation heavy, so I simply skipped it and moved ahead. E was good. Just missed the window for submission.

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

Annoucement-cum-Hardforces

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

Is it possible to solve Div1B faster than $$$O(n^5)$$$?

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

    With 2D FFT we can solve it in $$$O(n^3log^2n)$$$.

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

      I wondered if it's possible during the round. Nice :|

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

      How? Don't you need division for that?

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

        let dp[ k ][ i ][ j ] denote number of sequences of length i that have exactly j elements with k maximums (e.g. as in the number of maximums in the process defined in statement, e.g. the variable m). Then dp[ k ][ i ][ j ] is the sum over all i1 , i2, j1 , j2 , such that i1 + i2 == i-1 , j1 + j2 == j of ((i-1 choose i1) * dp[k-1][i1][j1] ) * dp[k-1][i2][j2]. This thing can be done with 2d FFT. E.g. we are fixing the position of the maximum element.

        Edit: right, the modulo isnt guaranteed to be prime, not too sure.

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

          No, its wrong.

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

          1) it should be i1+i2=i-1, though that's pretty easy to handle

          2) you forgot an (i-1 choose i1) factor, which requires dividing by i! before the convolution.

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

            ohh right

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

            I am not too sure i understand part 2). Do you mean calculation of (i-1 choose i1) mod p needs division ? If so, we can pre calculate that with pascal's triangle equality.

            Edit : I see, makes sense.

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

              No; you can divide by i! before convolution so you just do m convolutions of size nk; unless I'm missing something, directly calculating (i-1 choose i1) requires you to do mn^2 convolutions of size k, which is slower than the complexity interlude mentioned.

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

How to solve A ?? Intution ??

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

    Most people just deduced it from the given sample cases

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    $$$ans=\begin{cases}1&n=1\\\prod\limits_{i=3}^{2n} i&n\geq 2\end{cases}$$$
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why ?? i need intution not just the plain answer :_:

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

        You can find this rule by directly calculating the result when $$$n=3,4,5$$$

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

        It's in fact $$$\frac{(2n)!}{2}$$$. For any permutation with $$$k(k>=n)$$$ such $$$i$$$, you can reverse the permutation and get another unique one with $$$2n-1-k(2n-1-k<n)$$$ such $$$i$$$. So answer should be half of number of permutations.

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

    the answer is (2*n)!/2, because each permutation whose the number of pi < pi+1 is no less than n corresponds to another permutation whose the number of pi < pi+1 is less than n after you reverse this permutation

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

Tight ML in div2 C ;(

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

Sometimes I miss the old times when this assumption at least sometimes was incorrect.

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

    The data of this task is actually difficult to make, and I can't come up with all the wrong solution too. Maybe we could communicate more about this task.

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

      maroonrk what's incorrect in your code?

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

        My solutions is like this:

        The essential part of this problem is to make in-degrees of all vertices except the root no less than 2. For each vertex $$$i$$$, we know to which vertex $$$j$$$ we can span an edge. Valid $$$j$$$'s form a set of ranges if we order vertices by their distances from the root, and the number of ranges is at most the degree of the vertex $$$i$$$. My solution consumes O(number of ranges of the queried vertex) time, so it's a $$$O(NQ)$$$ time algorithm. However, it passed somehow.

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

          Well, doesn't look like "we can't come up with all the wrong solution".

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

I didn't enjoy this round very much,not only because I got a negative delta.

(For div2) The problems are way harder than a typical Div2 round,Problem ABC are not very suitable for their place and Problem DEF are so hard that very few people can solve them during the 2h contest.

Also the statement is kinda hard to understand(maybe it's my fault for not reading the statement that carefully but).You have to read it mutiple times to find certain words like "connected" or figure out what the problem is asking.

Contests are used to seperate contestants into two parts:Those who are very good at Problem Solving and those who are not that good.They are NOT used to find out who are better at English reading and typing.

upd: obviously the pretests are weak too but I blame myself

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

one of the worst contests with worst pretests with hard problems

at all, you won the worst contest

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

Every Time I think I am now good enough to become CM , My Rating Starts Falling Until it reaches Specialist Range

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

Sincerely, this round is not a good round. I have taken nearly 40 contests, and this contest is the first contest that I downvote.

1, the problem are so unbalanced, for div1, so many people are not able to solve A, and for div2, difficulty gap between B and C are too large, so as C and D.

2, div2 B is the worst problem I have ever met. It is so tricky, and description are soooooooo uncomfortable. What is "less than k-1" mean? Could you just write less than k" or even better "no greater than k". "n=1" is meaningless because we cannot pick two points from n=1, and "k=0 or k=1" is even more meaningless because, who want to discuss a graph with negative k?

3, div2 A are so unfriendly to newbies.

4, weak pretests

5, Except for the balance and description, a good contest should be educated. Even I cannot solve the problem during the contest and get negative delta, it doesn't matter. We can learn something after the contest, and improve our ways of thinking or coding skills.

But in this contest, I just want to say, what the hell of this ?? just a bunch of mind tricks or brain teaser? Can I learn something in the contest?

In all, getting up at 5:30 AM and take part in such contest is the most wasteful thing I have ever done.

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

    systest is pretty weak too? I uphacked myself with a case with obvious 32-bit integer overflow...

    130380959

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

I'm wondering if the pretest is too weak. I see many people got FST on 1C

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

In Div2 B, what is the expected answer for case: n = 1, m = 0 and any k. I guess according to definition of diameter given in the problem statement, diameter is not defined for n = 1 (we need at least 2 nodes to define diameter). I think the answer for this case is ambiguous and the problem should accept both "Yes" and "No" as the correct answers for the above-mentioned case.

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

    totally argee

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

    I think they made it quite clear the if n=1 the diameter is 0 by putting an example with n=1 and a note that says in this case the diameter is 0.

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

      I agree but this thing should be mentioned in the problem statement itself, most people don't see the explanation of the sample test case.

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

Why condition in div2 B use less than k-1 instead of less than just k? It just creates some confusions.

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

what is test 61 in DIV2 C/ DIV1 A ?

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

This contest has :

  1. Super bad statement. I saw a line in problem b "less than k — 1" which is completely unnecessary. The writer could try to reduce the value of k initially.

2.Super weak pretests.

  1. A bad timing for the contest as the number of participants are also low.

Thanks for the undeserving downfall.

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

Why do you set n=100 for n^5?

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

This contest feels harder than other div 2. It was really hard to understand the problems for me.

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

Nothing hurts more than "FAILED SYSTEM TESTING" utmost useless pretests after utmost annoying explanation!

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

THCE (The hardest contest ever)

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

FSTForces helped increase my delta from -3 to +30.

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

very weak testcases on Div2C, if you implement just some search with prefix sums beginning from every index and trying just a = 5 -> 20 and b = 4 -> 15 a x b matrices plus considering only cases when first and last rows of given matrix are only 11111... and others 100........001, it will be accepted :(

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

Allowing $$$p=1$$$ in B is just too evil, while it seems like there is no case where this really matters in the testdata.

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

As i said before with my other alt account named Akbar Covid you always make trouble and you caused to CF ban my other account ! This contest was a shity hard contest in the other words hackforces round 745 ! ! ! Please don't make more contests thanks :) And also again i have to notice that this contest was the worst contest in the year :)

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

    You deserve it.

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

    Your comment exhibits an acute amount of immaturity. Competitive programming is hard. Don't inculpate your own incompetence on the problem setters. The round was studied and tested by multiple people. You make it seem like they purposely decided to set a high threshold for the contestants.

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

I only read the problems in div2 and found out that it's too hard for me. :( It took me a long time to solve A in div2 so I gave up submitting the code.

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

As a Chinese, I think I'd better stay up late for a 22:30 contest in order to avoid a 18:30 Chinese Round next time.

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

Pretests in Div2 B be like: This

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

What is the intended time complexity for D1B? I could only come up with a O(n^5) solution.

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

The constraint $$$n\le 100$$$ in d1b is really frustrating. I like B, but don't like its constraints. Also I have no idea why C's point value is so great, as I think it's much easier than B.

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

I need a help in Question B my submission 130361322 . I am unable to figure out where my code fail. Thanks for the help

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

    You should do long long z = ((long long)n)*((long long)(n-1)))/2; problem with long long conversion. because n*(n-1) convert into int only before giving value to z. better way declare n as long long.

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

    when you run: n*(n-1)/2, n is a int, so it overflows. Then you assigned an overflowed result to int64, it brings wrong result.

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

Wow!!! Scored a lot, happy!

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

The contest problems were good and tricky. However, there was no relevant difficulty jump between problems B and C.

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

I am literally crying （>﹏<）

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

Problem A didn't even have a N = 400, M = 400 max pretest, and I ended up with a MLE in system tests. I don't know the exact line of thought of the setters, but I'd personally feel that a max-bound test is among the most important things to put in pretests.

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

    Even polygon will notify writers if test cases don't contain maximum data ranges. I really wonder how they make pretests for this contest lol

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

I went through a painful time during the contest. Looking forward to the next div2.

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

Goodbye Grandmaster,too sad,hahahahahahahaha

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

Odd contest, A and B were harder than usual, while C and D after them were much easier. I think I've seen a problem with the same idea as C before (square root decomposition on length of cycle), and D is just the standard $$$\mathcal{O}(n^2)$$$ tree merge with the tree hidden and a bit unusual cost function. I wish I had time to think about E since it looks more interesting, but I was too slow this time :(

At least I got to LGM somehow? I feel pretty bad getting there by just solving the easy problems slightly faster than others for many rounds in a row :/

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

    How do you solve D? What do you mean by "$$$O(N^2)$$$ tree merge"?

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

      So say you have a tree, and some random condition like "What is the maximum sum you can get by taking at most k nodes in the tree, such that no two of them are adjacent" to make the problem not completely trivial. Let's handle a binary tree since we have one in this problem, but it doesn't really matter.

      You can do this in $$$\mathcal{O}(N^2)$$$ by computing for every subtree, for every amount of selected nodes in the subtree, the maximum sum (for both if you take and don't take the root of the subtree). Then, you can merge children in $$$\mathcal{O}(L \cdot R)$$$ time where $$$L$$$ is the size of the left subtree, and $$$R$$$ the size of the right subtree by looping how many you take from the left and right subtrees and taking / not taking the root node itself.

      This runs in $$$\mathcal{O}(N^2)$$$ time since every node multiples the sizes of the other subtrees on the path from it to the root, and the sum of those sizes is at most $$$\mathcal{O}(N)$$$. I think this is a pretty standard technique.

      In this problem, we take the minimum as root, then build the trees for both the left and right sides and take their roots as the left and right children of the root. To merge, we loop over the amounts $$$x$$$ and $$$y$$$ of nodes we take from the left and right subtree, and do


      DP[i][x + y] = max(DP[i][x + y], DP[le][x] + DP[ri][y] - val[i] * 2*x*y);
DP[i][x + y + 1] = max(DP[i][x + y + 1], DP[le][x] + DP[ri][y] + val[i] * (m - 2*x*y - 2*x - 2*y - 1));

      as those are the updates when we do not take and take the root of the current subtree (which is the minimum of its interval) to the set.

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

        Thanks very much. If someone explains such way for every question than we noobs(as I think I'am) may learn a lot faster ... respect :D

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

        Thanks! 1499 F also uses that same complexity analysis you're talking about, and the editorial has a very nice explanation of it. Unfortunately I forgot about it.

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

        let dp[i][x]=maximum sum of pairwise distances between x number of nodes in the subtree rooted at node i,

        any idea on how to merge left and right subtree in this case?

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

    shared the same feeling while became expert:\

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

I still don't know the logic behind Div.2A. I only know that the answer is (2N)! / 2 (figured this from the inputs), have no idea how...

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it 
The diameter of a graph is the maximum distance between any two nodes.
The distance between two nodes is the minimum number of the edges on the path which endpoints are the two nodes

This is the diameter of a graph according to the question. And for the case n == 1, its not clear at all what the diameter should be. So, I think there should be no constraints on k(which is not defined at all) and hence every k should be valid

Can you please look into this interlude CQXYM and see if tests could be ran once again on B. Surely, this is much ambigous

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

    In the case of n == 1, the diameter of the graph is 0 so any K <= 1 isn't valid.

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

      DarkTigerFAF Its good to read the comment well before replying. In short, I want to say that the diameter is not defined at all when n == 1 and hence, there should be no constraints on something which is not defined or exists.

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

        Oh sorry about that, thought u were just asking why it's an invalid answer. But yeah I agree with you.

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

        The sentence you've copied well defines diameter for n=1 as 0. I don't see anything wrong with it.

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

          [Deleted]

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

            Yes I meant picking two same nodes. If the statement didn't specify that two nodes should be distinct, you don't add such condition. I do not believe the author is at fault for participants' inability to understand mathematical statements.

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

      Diameter is maximum distance between any pair of nodes. When N==1, we cant form any pair.

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

    Sorry but this problem is prepared by CQXYM. Maybe you shold ask him.

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

      Thanks! Edited my comment to tag him too!

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -25 Vote: I do not like it
      Now we should ask CQXYM ?
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +58 Vote: I do not like it

        No I don't mean that. I would like to bear all the criticism or something like that. But I really can't answer his question so I suggest him to ask CQXYM.

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

Only 6 persons passed 2D in div2. I passed 2D but didn't pass 2C, then I'm rk 185. Is this really resonable???

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

    because you take too much time and also 2 wrong submissions and since 1500 and 1750 are near so 2 wa makes it equal to those who submit it in one go.

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

20,000 thousands registered for contest but only 5600 participants solved A because many of the registered participants couldn't solve A and many participant's rating will be badly effected for this but they don't deserve it. I think A should be more easy to make sure the actual number of participants because the rating change depends on number of participants I guess.

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

    I don't think this A is difficulter than it should be. It's very easy to find that the answer is A(n,n)/2.

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

very poor round, div 2 c is much harder than normal, D is near impossible for div 2 writing problem B is very confusing, why make it <k-1 why not <=k and just use a proper k? because the author wanted to confuse people to make it seem like it's a harder problem

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

Why "less than k-1"?Why not just "less than k" or "no more than k" or anything readable?

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

Problems themselves were not bad, rather good. But too unkind to participants

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

Meaningless 2E/1C with the time limit of 1 sec.

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

All in all, I think this round is not good.

  1. The description of div.2 B is not clear. Why not use "not less than k" rather than "less than k-1"?

  2. I think the case that k<=2 in this problem is meaningless, although I used this to hack someone.

  3. For div.2 D I couldn't find any solution under $$$O(n^3)$$$ or $$$O(n^3 \log n)$$$. In fact, I felt confused when I know that $$$O(n^5)$$$ is acceptable. How the $$$O(n^5)$$$ solutions works in $$$n=100$$$?

  4. For div.2 E, I was troubled with the data range, too. The solution works in $$$O(n \sqrt n)$$$, but I think it is too close to the time limit so I gived up to solve this problem :( . And what's more, will players who use python language got $$$TLE$$$ because of this? (python runs slowly than other languages)

All in all, I don't like this round very much although I got a nice ranking.

And hope the next round will be better.

Sorry for my terrible English.

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

    For div.2 E, I can't agree more. LOL

    Just two days ago, I got TLE in a contest, because I used an O(n sqrt n) complexity algorithm (the solution is O(n log n)).

    In div.2 E, I got a O(n sqrt n) complexity alogirhtm and of course I gave up to use it... What a pity!

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

    It's normal to have $$$O(n^4)$$$ Solution when $$$n=100$$$.$$$O(n^3)$$$ is for $$$n=500$$$.And this $$$O(n^5)$$$ Solution have constant factor no more than 1/16(maybe have lower bound).I think it's important to analyze the constant factor.

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

Why the solution of B is $$$O(n^5) (n \le 100)$$$ and the solution of C is $$$O(n \sqrt n) (n \le 2 \times 10^5)$$$? I think many contestants may be afraid to submit their solutions.

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

    For C it's completely normal for $$$O(n \sqrt{n})$$$ to pass, I'd be afraid to submit $$$O(n \sqrt{n} \log)$$$. Sqrt solutions are common stuff. The constraints in B are a shitty jebait where I only decided to try and constant-optimise based on a lot of experience with constant optimisation.

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

Can anyone tell me whats wrong in my solution to Div1 A. The link is https://codeforces.net/contest/1580/submission/130356049.

I tried stress testing it with a correct solution but couldn't find any failing test of reasonable size.

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

CodeFSTes Round #745

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

In div2B

testcase : 5 4 4 i think ans should be NO but everyone code is giving yes. could someone please explain ?

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

    1-2 1-3 1-4 1-5

    4 edges and the diameter is 2

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

    K=4 Which means you can have the diameter be 2 You can achieve that by making a star graph Connect all nodes to node number 1 You will use only 4 edges so answer is yes

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

It's a terrible round for me :(

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

I still have a question!!!!

For Div1 D, note on sample 1.

No matter how I calculate the answer, subsequence [15,2,18,12] has the sum of $$$97$$$, so it's not "also a possible answer".

Can anyone help me?

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

    Sorry. I make a mistake in the note. Subsequence [15,2,8,12] does have the sum 97. I'm very sorry for that.

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

      I spent nearly 30 minutes reading the problem over and over again to check if I read the problem wrongly:(

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

I can't understand why the author doesn't directly say "diameter is less than or equal to $$$k$$$" but "diameter is strictly less than $$$k-1$$$" in Div.2B. It can only be said that it is purely used to torture people.

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

Can a strong public opinion make this round unrated?

→ Reply
»
3 years ago, # |
  Vote: I like it +63 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!

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

    I think this round should be unrated for having so many problems including vital ones (like the wrong notes during the whole contest). The vote and comments of this blog also tell how contestants judge this contest.

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

    I also think this round should be unrated. Unlike Div2 contests, problems were harder and the statements of some problems were confusing. In Div1, the situation was even worse, there were wrong ordering and weak pretests. Also some users reported that Div1A or Div2C constraints were misleading.

    Overall, this was a badly authored contest. (We can see the effect on the announcement votes)

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

I'm missunderstanding the problem div2C/div1A The portal could be in any place? or its fixed on the (1,1)?

If it's fixed, where it's the portal of the second testacase?

If not, why it's say M_(1,1) can be of any type?

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

There is a room for missunderstanding, it can be read "sub rectangle start with(1,1)

conditions for the portal part made us to understand "subrectangle start with point (1,1). many people understood this problem like me. please consider this issue.

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

Never Have I ever Seen so many Downvotes on an Announcement of a Round

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

My screencast https://youtu.be/E6RXjEaf3W4 (solved A, C, then tried F and B).

I like B because for a long time I couldn't solve it in polynomial time. And I appreciate the non-trivial-to-understand time complexity in D. I didn't like constraints in C and A (would be easier to test with $$$a, b \leq 3$$$ instead of staying true to Minecraft).

F smelled like Berlekamp-Massey with FFT. The coefficients are indeed very easy to guess and compute (some binomial coefficients). Sadly, I couldn't solve the problem fast enough for $$$m \leq 50\,000$$$.

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

    I managed to solve it without even knowing Berlekamp-Massey, with OEIS and matrix analysis.

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

I am so happy because today I became pupil. it really feels good 😭 .

Any way, good luck for the next contest for every one.

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

Div. 1 A told us how the remaining problems look like:

The Nether.

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

I have proof for div2-A. First let's introduce some definitions:

For a given length of permutations ($$$2n$$$ for the problem), Let $$$X[i]$$$ be the number of permutations having exactly $$$i$$$ indices $$$j$$$ such that $$$P_j < P_{j+1}$$$

And $$$Y[i]$$$ be the number of permutations having exactly $$$i$$$ indices $$$j$$$ such that $$$P_j > P_{j+1}$$$

First observation: for any $$$0 \leqslant i \leqslant 2n - 1$$$ we have $$$X[i] = Y[2n-i-1]$$$ (pretty obvious if you have $$$i$$$ indices lesser than the next element then the remaining indices will be greater than their next element)

Second observation: for any $$$0 \leqslant i \leqslant 2n - 1$$$ we have $$$X[i] = Y[i]$$$ (why ? if you reverse any permutation having $$$i$$$ indices lesser than their next element you will get a permutation having $$$i$$$ indices greater than their next element)

Therefore we have $$$X[i] = X[2n - i - 1]$$$ for all $$$i$$$. Hence $$$ \sum_{i=0}^{2n - 1} X[i] = 2 * \sum_{i=n}^{2n - 1} X[i] $$$

The left part is the total number of permutaions which is $$$(2n)!$$$ and our answer is $$$\sum_{i=n}^{2n - 1} X[i] $$$, so $$$ANS = (2n)! / 2$$$

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

Can anyone hack this submission (or prove that it actually works)?

Submission: 130359855

Basically, the code above fixes two columns, and then greedily expands the rows one by one. It breaks whenever a worse answer is found. But even if the current answer is worse, maybe the future answer is actually better and hence this greedy approach fails? Please help.

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

In D1E, what is the intention of such a large constraint on $$$x_i$$$? It's really useless and forces us to use unsigned 64bit integers, which cost me 2 incorrect attempts.

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

I was wondering why CQXYM didn't post this blog. Now I know...

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

I was about to upvote this announcement earlier today because it looked short and clean, but luckily something happened with my brain and decided to wait and decide whether to upvote or downvote after the contest.

Ironically enough, I misclicked when trying to hit the red button, and upvoted it by mistake :(

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

Though I didn't participate in the contest, those downvotes show me the deep anger of the participants, considering the fact that competitive programmers usually upvote contest announcements because at least they know that it is very demanding to prepare a contest.

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

Sorry, not a fan of this contest tbh:

  • My totally legit solution to A in Java ($$$n^3$$$, low overhead) TLEs. I have no idea why there couldn't have just been a 3s timelimit on this problem, there's no way an $$$n^4$$$ will finish in 3s. It took me about 15% of the contest to do what should be unnecesssary speedups and convert this to C++ to get it to pass, when I'm basically 100% sure my solution is what authors intended. This is an indication of both bad time limit intuition and not having enough testers in other languages; having either of those things could have addressed this.

  • I was legit paranoid that C wouldn't be possible in java, since it had a sqrt factor on a 1s timelimit on $$$n = 2*10^5$$$. Again, I see no good reason why this time limit couldn't have been either 3s, or at the very least made $$$n = 10^5$$$ if you really need a 1s time limit.

  • For B, the author says: "$$$O(n^5)$$$ is the expected complexity." Seriously??? Why not just make bounds equal to at the most $$$40$$$ then? In contest I suspected I would have trouble with an $$$n^4$$$ even, because that's already $$$10^8$$$. $$$n^5$$$ with bounds of $$$100$$$ is way too big to be reasonable here imo.

  • I've heard people say that D was interesting, but I didn't even come close to getting a chance to work on it.

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

    Finally, I had witnessed SecondThread solving a problem in C++ ( *_* ) !!!

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

    Let me add some more points to this.

    • In problem A, I would emphasize in bold that the rules in this problem are not like they are in actual minecraft, as I suppose in minecraft only $$$5\times 4$$$ rectangles are portals. Usually something like this is written in problems based on some well-known game.

    • Pretests in A would be much worse without 17-th and 18-th, but it would be perfect if they were added before the contest.

    • As there is still no editorial, I wonder which cutoffs authors used in B. I guess I was quite optimal in terms of memory leaps, and I also used Barrett reduction, so it was enough for me to skip states with $$$n < k + m - 1$$$ (without it my solutions worked for 9s, with this it became 1.2s).

    • Actually I do not feel anything wrong with $$$n\sqrt{n}$$$ in C. I think it was quite obvious that this must pass. My solution worked about 300ms in custom invocation, and I didn't even adjust my block size. However, I don't know about other languages and $$$n\sqrt{n}\log{n}$$$. I still believe it should be fine if $$$\log{n}$$$ is from Fenwick.

    • C < B.

    • I have not read problem F till the end, but when I did, it reminded me some problem from project euler. I do not claim anything, but I wouldn't be surprised if it turned out to be a problem from pe.

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

      FYI, in recent versions of minecraft, you can indeed make portals of larger sizes than 5x4 (you can go up to 23 by 23, but nobody really knows that rule. It was only in old versions that only exactly 5x4 worked.

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

      Yes, problem F seems to be a harder version of this. Looking at the comments there may probably help (there is a cute characteristic polynomial in the second comment of the thread).

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

      Golovanov399 Hey, how is n.root(n) without any pruning supposed to pass? Can you clarify a bit? I am a little bit confused, as I remember the problem (https://codeforces.net/contest/1561/problem/D1), in this n.root(n) solution, was desired, but many test cases are taking time > 1s, hence accordingly time limit of 6s was given.

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

        Let $$$K$$$ be a fixed constant. Divide all trains into big (with $$$x + y \geq K$$$) and small (all others). We will maintain the following:

        • for all $$$s < K$$$ and $$$r < s$$$ we store the number of (small) trains with $$$x + y = s$$$ which are going to be in maintenance on any day which is $$$r$$$ modulo $$$s$$$;

        • an array $$$p$$$ of size $$$m$$$ so that for every day $$$t$$$ we have $$$p_1 + p_2 + \ldots + p_t$$$ is the number of big trains in maintenance on day $$$t$$$;

        • current prefix sum of $$$p$$$ till today.

        When we add/remove a small train, we need to update at most $$$x + y < K$$$ values. When we add/remove a big train, we need to update at most $$$m/(x+y)\cdot 2\leq 2m/K$$$ values. To compute an answer, we need to add $$$K$$$ numbers for all small sums to the current prefix sum of $$$p$$$. Therefore if $$$K\approx\sqrt{2m}\approx 650$$$ then this should be good.

        In my solution $$$K$$$ was $$$300$$$, and it still was fast enough.

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

          Got it! Thank you for the nice explanation.

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

      .

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

Downvoted because of "A few pretests were added, submissions were rejudged"

Why are people so afraid of hacks today and try to prevent them even by rejudge? Ridiculous.

I heard an opinion that the site will lose some traffic otherwise, but think who it will lose? I can't believe Mike can bend to satisfy this potentially lost traffic so he gives coordinators orders to prevent hacks.

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

    Please, don't downvote me, but I think that hacks doesn't make a contest more interesting.

    For example, I have participated in Technocup 2020. I have solved tasks A-E, and was about to solve G. Imagine my surprise when my solution failed system tests...

    Well, you can say "lol, just wrong solution". I haven't used double hashes, so I thought at first that I had got WA just for this reason. But imagine my shock when I had found out, that I have written SQRT-decomposition wrong, and this solution worked in O(N^2)!!!

    ($$$N <= 2 * 10^5$$$)

    Are you serious? One could pass pretests using just a bruteforce and one if statement to speed this up.

    I think, this is not normal.

    But, what about hacks now? Hacks are the same thing. I am here to solve tasks. I think that we need pretests as a 99.9% guarantee, that your solution is right. And running full system tests is just impossible during the contest because there are too much tests and there will be very big queue.

    I think that wee need hacks only to make sure, that there aren't any wrong solutions that are accepted after system tests, because every successful hack is going straight to the system tests.

    As a conclusion: yes, I am one of those persons who are afraid of hacks and weak pretests.

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

    Agreed.

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

So many grammar mistakes:

(Div2 A) CQXYM is counting permutations length of 2n.

(Div2 B) The distance between two nodes is the minimum number of the edges on the path which endpoints are the two nodes.

(Div2 C) A rectangle M size of a×b is called a portal if and only if it satisfies the following conditions:

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

Thanks for quick system testing and rating updates, even if I had a huge negative delta haha. I actually liked these tricky problems that are harder than usual (maybe unpopular opinion?). The only relevant problem with this round was a bad pretests set for some tasks/problems/questions/bugaboos.

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

Painforces

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

Div.2A is quite hard since you should use some mathematical knowledge to solve it.

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

    How to solve it?

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

      ans is ((2*n)!)/2 it want pi<pi+1 no less than n which is also no more than n pi>pi+1. intersection of both of these is null. total cases are (2*n)!. so and is ((2*n)!)/2

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

      The answer is $$$\frac{(2n)!}{2}$$$.You can try to reverse $$$p$$$ and count the number of $$$i$$$ satisfying $$$p_i<p_{i+1}$$$.

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

It's so ridiculous that my $$$a=5,b=4$$$ solution to div.1 A passed the previous pretests. The pretests are likely to be generated by the problem setter's feet I guess. I will think twice before participating in a Chinese round again (last time when I participated in a Chinese round I said so. My rating went down in every Chinese round before lol).

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

i wish i knew some ordure in Chinese to comment here

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

I don't want to be rude or anything like that but I just wanted to know what is the job of a coordinator?.

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

All in all,it's interesting but really hard.

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

Congratulations mango_lassi for LGM.

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

$$$O(n^4)$$$ can pass div1 A and $$$O(n^5)$$$ can pass div1 B!

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

.

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

Why no stress tests in pretests on Div1C? I belive, that there should be some tests that at least will break some popular SQRTs, like 500.... In task which main solution I belive is SQRT decomposition. It's pretty disapointing, when you change root after contest, and it works.

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

To sum up my feelings about the contest in the nicest way I can, let's just say I didn't have fun today.

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

Make this contest unrated!

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

Come on man, problem A is not of 800 Rating.

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

It was an interesting contest. It will be really fun to upsolve this one. :)

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

i understand and agree on the fact that contest was too tough than it should be,but still the kind of comments that we are posting is not at all healthy from a community point of view,so lets give feedback's but in a constructive way as everyone is a human here,so we can at least give one more chance to the author's.Hope u understand my point:)

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

Nice Contest!

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

It would be great if they can provide the editorial very soon.

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

I don't understand the point of having so many testers!

Did none of them mention issues like too hard Div2 A, unbalanced problemset, $$$T \geq 1$$$ constraint xD, unnecessarily strict TLs, negative diameter, < K - 1 condition, unintelligible grammar etc...

I'm sure they do provide feedback, as I can see from pkpawan's comment at top. In that case why are their suggestions not heeded?

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

just curiously asking..
last education round 113, my rank was about 2303 and got +63 (1325-1388)
today in this contest my rank is around 2068 but got just +22 (1349-1371)
isn't it something weird....
i mean, i thought i will get at least 40-50,

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

    No. It's not so weird to get less rating change while you have more rating on the almost same place

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

    number and rank of ppl you passed in contest also matters

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

    because educational round is rated for purle, but this div.2 round is not.(maybe)

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

Problem div1A has very weak tests.

The following solution gets AC.

Spoiler

And there's obviously a very simple counter-test: A very big portal that don't touch the borders of the matrix.

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

Can anyone explain how to solve problem Div1.B?

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

C is 1700 rating???

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

.

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

Well, when will the editorial be available?

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

when will editorial out??? Some recent rounds were hard for me. I am so bored now and hope next round will be more interesting

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

I think downvotes for this contest are a little unfair. And downvotes are bridges for upvotes. I hope that interlude have great contests in future.

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

interlude now has the 3rd least contribution, with only Good.Stone and Sparky_Master_WCH1226 beating him.

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

MikeMirzayanov do smth about this bulling, community is too cruel. Yeah, of course round was not very pleasant by opinion of many people, but cmon authors do not deserve such treatment. Feels bad for them

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

A really amazing set of problems to think on. It was a nice and different experience, to have a rather difficult round than usual. Some amazing work by authors to make a contest that no one could complete XD.

Thanks a lot to the authors for the round and some interesting problems.

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

No way A is 800. I only solved it bc I noticed a pattern of n!/2 in the examples. But proving the correctness is at least a 1000+ problem.

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

    every div 1. participant: eh, 800, 1000, what's the difference

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

why does this post have so many dislikes? because of hard problems, that lot of participants didn't solve? is is the problem of author, or a problem of participants?

guys, do not dislike. better try to improve yourself

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

    The problems were harder than they should be, but this is extreme overreaction IMO. The authors do not deserve this kind of treatment.

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

    Yeah I agree, I think people got frustrated due to the statement "strictly less than k-1" which was kind of vague but I think authors gave that just to confuse(or help?) as people who would have basic ideas of trees and graphs would tend to pause and think in direction of n nodes, n-1 edges(what I feel).

    All in all, I guess mostly people are frustrated due to FST, odd times, n^5 solution passing but seeing at the number of downvotes, it made me quite sad as preparing DIV 1 problems are not everyone's cup of coffee :(

    I upvoted though :)

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

    the problems are great (and I like it). But there are a lot of thing little things that can be done to make the contest much better - no reason to have n = 100 while the intended solution O(n^5) (some people said that they did not pass with O(N^5))

    • O(n sqrt n) solution for n = 200000 in 1s very tight. I don't understand why the time limit is not 3s or n = 100000.

    • wrong ordering for 1B and 1C.

    • super hard 2A (and quite hard 1A) A(s) problem should not be hard so people are encouraged to participate)

    • very high difficulty jump from 2B to 2C

    • rejudging of 1A during contest

    • not to mention some grammar and note error(s) made.

    Creating too difficult/unbalanced problem is okay to be criticized or else someone can just make contest with 5 3000-rated problems and say "hahaha, get gud brrrrrrr" when everyone had a hard time solving it

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it
    • Bad readability and grammer (maybe intended)
    • difficulty issues(Div 2 D being 2600, WAY more harder than Div 2 E 2200)
    • quite questionable constant ranges(O(n5)(n≤10), O(nsqrtn)(n≤2×105))
    • too weak pretest, also weak systests (fenwick nsqrtnlgn passes E, brute forcing a<=20, b<=20 passes C)
    • wrong notes

    I dont get why people are downvoting.

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

Can anyone help me find what's wrong with my solution for Div2B ? Here

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

[deleted]

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

Please stop this guys....Everyone is criticizing to0 much and if this goes on many authors will be afraid to make contests on codeforces....I know how it feels.I performed badly too but why criticize this much in first place?? is it because they wasted 2 hr of your time.You can manage 2 hr but dont bring his morale down... $$$No$$$ $$$one$$$ $$$deserves$$$ $$$negative$$$ $$$votes$$$ $$$for$$$ $$$making$$$ $$$a$$$ $$$contest!!!! $$$.Please show your dissatisfaction in comments but atleast upvote the announcement.Its request from one coder to another

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

Div2D's data range is too large for O(n^5). Finally I removed an extra %MOD and runtime reduced significantly. Does that impact so much?

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

I don't know why many people criticize 2A. It's quite straightforward to know that for any pair of permutation and its reversed version there must be one and only one in the final result. I agree that the description < k — 1 of 2B is too confusing. I read more than 10 times to confirm I have understood it. The data limitation of 2D and 2E is too large.

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

F**k, I submit a wrong code of A and get a TLE then I headed to an Expert.

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

Reminded me of div1A.

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

This round is much better than round #810.

→ Reply