DS007's blog

Codeforces Round #695 (Div. 2)
By DS007, 11 days ago, In English

Hello Codeforces!

I am pleased to invite you to my first contest Codeforces Round #695 (Div. 2), which will take place on 08.01.2021 17:35 (Московское время). The problems were written by alimq and DS007. The round is rated for all users with rating less than 2100, while other users can participate unofficially.

You will be given 5 problems and 2 hours to solve them. You are strongly advised to read all the problems.

I would really like to thank:

  • BledDest for his amazing coordination of the round.
  • Aggu_01000101 and infinitepro for helping me in shortening the problem statements and solving one of the problems.
  • MikeMirzayanov for creating the Codeforces and Polygon systems.
  • The following people for testing the round:
Geothermal
sahil_k
dorijanlendvaj
eggag32 awoo
Roms Java
stefdasca Aggu_01000101 kostia244
fishy15 Gilgameshx vrooooom
T1duS wabadabakalakaboo neko_nyaaaaaaaaaaaaaaaaa
SleepyShashwat BRCode infinitepro
flamestorm saarang123 geekpradd
Jellyman102 manish.17 1_2_oatmeal
anuragbhatt socho kshitij_sodani

We hope you will enjoy the problem set! Good luck!

The scoring distribution will be added shortly.

UPD: Also thanks to nooinenoojno for testing the round.

UPD: The scoring distribution is: $$$500 - 1000 - 1500 - 1750 - 2500$$$.

UPD: Congratulations to the winners

Of div 1:
1. kort0n
2. Suiseiseki
3. peti1234
4. fastmath
5. wrinx

And of div 2:
1. raingirl
2. xsdns
3. Mister5
4. o.a
5. wudi2016

Thank you all for participating! My apologies for misjudging the difficulty of B.
Editorial

 
 
 
 
  • Vote: I like it
  • +408
  • Vote: I do not like it

Comments Comments (435)
»
10 days ago, # |
  Vote: I like it +722 Vote: I do not like it

As a tester, I have a proof that upvoting this comment will lead to positive delta. But the proof is too long to fit the margin.

→ Reply
»
10 days ago, # |
← Rev. 2   Vote: I like it +184 Vote: I do not like it

As a tester there are 1 AI and 4 DS problems

Spoiler
Spoiler
→ Reply
»
10 days ago, # |
  Vote: I like it +104 Vote: I do not like it

As a tester, I Can confirm that DS007 is a wonderful dancer.

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

As a tester, I'll edit this comment later and add something witty.

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

    Seems like it was quite difficult for DS007 to fit you in the above tester arrangement, which itself is pretty cool, I hope there would have been more diversity in color(given we have new year magic)

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

      Isn't the colour arrangement pretty cool though? It's the CodeForces logo!

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

        Indeed it is, but would be much better if we can have you also in that arrangement :P

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

        Ahh my bad, seems like you are already there in expert's color :P

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

          Yes :( The real CodeForces magic was that the website somehow detected my true skill level :(

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

            As a tester, I can confirm I'm actually red

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

            As a tester i also agree with you all. All the best everyone and do tell me if my testing was worth it

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

Indian round means unrated round

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

This should be great contest. Good luck to everyone!

→ Reply
»
10 days ago, # |
← Rev. 8   Vote: I like it +162 Vote: I do not like it

I'm the (official) meme supplier for this contest. For every 69 upvotes, I'll upload a new, original content, cp related meme.

#1

Free Sample #1

#2

See this post for latest memes.

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

Good luck to everybody and to me also

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, no wonder you said, You had a lot of testers for this round earlier. Looks like a lot of effort went into the preparation of the round, looking forward to it. Also any authors of future rounds who are looking for testers, I would be happy to help.

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

Let's wait till 11/01 to see the tester table messed up. Unless it will be changed later.

→ Reply
»
10 days ago, # |
  Vote: I like it +119 Vote: I do not like it
Spoiler
→ Reply
»
10 days ago, # |
  Vote: I like it -7 Vote: I do not like it

only 192 more for pupil rank :D (lmao I'm not still good and I don't know why I'm happy)

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

(bccf)

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

I tested this contest and it was good.

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Last round was great. Problem statements were short & crisp and without unnecessary stories to read. As you mention that the problem statements have been shortened, eagerly awaiting the next round :)

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

As a tester, give me contribution! Also suggest me a new profile photo, I removed mine temporarily.

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

    You got contribution even as a non-tester! Not positive though, but still you didn't specify what kind of contribution. May consider doing this in future myself.

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

Your Ceiling is My Floor!

© tourist

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I like how the testers' names are arranged in order of the lights to the left of the logo!

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

    Imagine getting rejected as contribution farmer tester just because cf logo will not look good in the announcement.

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

      LMAO. Still, you gotta appreciate the effort though XD! For the testers to change their ratings so much and for DS007 to properly format it.

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

Indian Round .

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

pog

→ Reply
»
10 days ago, # |
← Rev. 7   Vote: I like it -51 Vote: I do not like it

Hello :)

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

I hope everyone rating goes up in this contest

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

    you seriously lack hoping skills

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

    we don't do that here

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

    Well its impossible. Someone's rating has to decrease for someone's rating to increase.

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

    You better never hope anything positive from the next time

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

As a non tester Chaliye Fodte hai ;)

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope a good result for everyone !

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

It's advised in the post to read all the problem statements. Does that mean the problems won't necessarily be in increasing order of difficulty?

→ Reply
»
10 days ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

As an idler, there are too many useless spoilers on this page, so one can use this script in the console to expand them all:

$(".spoiler-content").map((i,val)=>{val.style.display="block";})
→ Reply
»
10 days ago, # |
  Vote: I like it +5 Vote: I do not like it

SPOILERFORCES

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

Guys don't waste your time in B and C like me. There is always an easier approach and everytime I think of an overkilled solution.

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

    You may consider rethinking your strategy after this contest...

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

    I feel you bro :'(

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

    ALways start from harderlike D or E onwards as cheaters can't ruin them easily. Also you may get first to solve award for a problem with that startegy, Last contest I would have solved Div2 D as the first person to solve but I got a silly error thus finished it after 7-8 people.

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

    Guys guess what?? Again I overkilled the solution of problem B. Although i solved it but wasted a lot of time. XD

    → Reply
»
10 days ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

Love this comment section

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

hello im from viet nam

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

There are only 3 ratings left before I can be a Master(without using "magic")!Hope I can do it!

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope no one cheats in today's contest.

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

Just two hours left in the contest and still not able to see the score distribution for problems.

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

Ok

→ Reply
»
9 days ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

If the contest gets 20k participants, I'm going to post 25 high quality memes.

Plus, DS007 promises a div1+div2 contest in the near future if this contest is well received...

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

F

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

scoring PLS

→ Reply
»
9 days ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

Is it rated for newbie?

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

    i think u did not read the contest announcement (The round is rated for all users with rating less than 2100)

    → Reply
»
9 days ago, # |
← Rev. 2   Vote: I like it -53 Vote: I do not like it

.

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

    Don't generalize a bad deed to many people, especially when lots of them are helpful and honest :D

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

    Indians aren't cheaters. Don't generalise something to whole community. It's not a good thing.

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

good luck

→ Reply
»
9 days ago, # |
← Rev. 4   Vote: I like it -18 Vote: I do not like it

div2A is kind of diffcult >_<

I think we could add a problem in front of this and make a 6 problem round.

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

it's been only 30 minutes and I already hate this contest.

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Long queue?

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

I think authors should not make problems anymore

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

Describe the contest in 1 line: Wrong answer on pretest 3

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

The round of Wrong answer

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

deleted

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

Contests 2021 is so boring !!!

→ Reply
»
9 days ago, # |
← Rev. 3   Vote: I like it -52 Vote: I do not like it

Deleted

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

I am in doubt this is a div2 round ...

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

    I have a similar doubt too. Looks like a DIV 1 I guess. One thing which presents always while submitting my code i.e--"W.A on pretest 3". Disappointed after giving today's contest. :(

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

well there goes my expert

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

As I can see from my friends standings this contest has been a total mess.

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

to the admin of this contest please don't do the same for the next time.

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

it is been more than half of the contest and less than 3000 one solved b :o , i can say that this is a big mess

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

Pretests for B are too damn strong. Kudos.

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

    Better strong than weak. Would you really want to fail a system test?

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

Just waiting for time to end and someone tell me all I did was miss an edge case to get Wrong Answer on Pretest 3 :(

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

    You can try this;

    1
7
1 10 5 2 7 4 1

    output:2

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

I am actually curious to see the standing of the testers' virtual participation.

→ Reply
»
9 days ago, # |
  Vote: I like it +98 Vote: I do not like it
CF #695 IN A NUTSHELL
→ Reply
»
9 days ago, # |
  Vote: I like it -6 Vote: I do not like it

is it only me or is anyone else also struggling with pretests of DIV2 A?

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

    Use patience there is a little trick in it. I have given 5 wrong answers for div2 B.

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

Div2-B Pretest 3 is KILLER !!!

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

What the hell is this Pretest 3 in B

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

SOLVED C but Failed B. this is CODEFORCES EFFECT

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

No way this was a DIV 2 round

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

Too hard!!

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

Really confusing statement for A, or so it appeared to me. Although they explicitly mentioned $$$|x-y|$$$, I had considered array to be circular in my mind. Even the examples satisfy the circular array assumption.

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

    Same, I to get WA on pretest 3, not able to solve a single question, RIP my ratings ;-; :( ;-;

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

WA on pretest 3

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

The most evil: "Problem B pretest 3"

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

I probably misread Div 2

→ Reply
»
9 days ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

To the people complaining — Div2B is all about a simple brute-force, so yes — you've read that right — perfectly suitable problem for Div2B. As for the Div2C I believe it has to do something with finding the two minimum elements and a few corner cases, but wasn't able to solve it fully.

Overall a great contest! Really challenging and interesting problemset! Thanks to the authors for such an amazing contest!

EDIT: Again downvoted for saying truth — newbies go be real mad. Y'all expect to solve 3 problems and stay pupil? No, that's not how it works. Back in the day, people who solved 2 problems fast could reach 1700 — because problems used to be tough. Trust me — no improvement if you do only easy problems.

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

    I don't know about rest of the comment but yes challenging problems must be welcome

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

    Downvoted, I don't like when D2B is bruteforce. Am I newbie?

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

      I didn't call people newbies for not liking D2B bruteforce — just not being able to figure it out in 2 hours really doesn't deserve any higher rank. I was very scared when It took me over 30 minutes to get such an easy problem right. It's really a standard thing these days to see D2B done using brute-force.

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

      D2B was not a bruteforce, it was $$$ifififelseifelseelseififelseelseififelse$$$.

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

        It was brute-force without many ifs if you are smart about it. Take a look at my code and compare it to yours.

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

        not at all https://codeforces.com/contest/1467/submission/103806657

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

        Writing a score function like this would have saved you a lot of time and efforts : 

         int score(const vector& a, int i) {
          if (i <= 0 || i >= a.size() — 1)
            return 0;
          if (a[i] < a[i — 1] && a[i] < a[i + 1])
            return 1;
          if (a[i] > a[i — 1] && a[i] > a[i + 1])
            return 1;
          return 0;
        };

        → Reply
  • »
    »
    9 days ago, # ^ |
    ← Rev. 2   Vote: I like it -13 Vote: I do not like it

    Agree that this was a nice contest. Couldn't complete finding C corner cases. It was a hard fight and annoying.

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

    In my opinion B was "hard" for the wrong reasons. Most people at the Div 2B level can definitely understand the solution for B. The most pleasant word I would use to describe today's B is not "hard", but "tedious": had the right idea and most of the details early on, took forever to find the missing corner case.

    Also, it wouldn't be such a big deal if the very next problem, C, wasn't yet another "figure out the cases" problem 0_0.

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

      Again i will say — no special case exists in Div2B. Take a look at my accepted code.

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

        Ignoring template my code is shorter than yours .___.

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

          But it's more bug prone. I was 100% convinced my solution would not fail, while it took you more attempts to get it right.

          I'm not disapproving your knowledge in any way, just to be clear.

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

      I don't think B had a special case... You just needed to implement it carefully.

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

    did you lost your mind??

    Div2 B are generally of rating 1200-1300 and this contest's div2B is of rating 1700. This is the most unbalanced contest.

    Its easy for you to say these things because simply you are expert.

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

Got stuck even on B. As a result, return to the cyan :(

How to solve B and C?

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

    B is brute force. Change each character so that it is equal to one of its neighbors and "carefully" calculate the change of cost for only the subarray where the change has an effect. Then do the same for the other neighbor.

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

      Change the character $$$a_i$$$ to previous $$$a_i$$$ or to the next $$$a_i$$$? I did so, and got WA 3 :(

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

        I got a nasty bug where I did not check if the neighbors that were previously not a hill/valley became a hill/valley after changing the value of a[i]

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

        Change to both, and see which one gives you a better result.

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

        Also, if $$$a_{i-1} \neq a_{i+1}$$$ you might try something between them, like $$$\frac{a_{i-1} + a_{i+1}}{2}$$$

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

      With this exact approach I submitted 7 wrong answers, still unsolved. Can you share a clean implementation?

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

        Brother you might be missing that after changing A[i] to A[i-1] what is the impact of A[i-1] on A[i+1]. initially I was also missing this but got AC after i checked it.

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

          I did realize this later but i guess i suck at implementing. Thanks

          → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

getting wrong answer on pretest 3 for B question ,can anyone give any test case

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

quite a peculiar contest many people had the first problem wrong in the first attempt and even the second question. loved the contest by the way

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

Those who failed B, try this

Testcase

2

6

1 5 10 4 6 12

6

10 8 5 15 7 6

Answer should be 1 1

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

fuck you mother fuckers[user:alimq][user:DS007]

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

Who made these problems is an evil person ...

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Since contest is over, may I get some hints on how to solve problem C?

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

    I replaced a[i] for 1<i<n with both adjacent elements one by one and then counted minimum for all the 1<i<n. It passed.

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

    Without loss of generality, lets assume that the final element will belong to bag A.
    Now, think of the problem as ans = a1 + a2 + ...an + -b1 + b2 + ...bn + -c1 + c2 + ... cn
    (Move all but 1 element in A to B. Move all but 1 in C to B. Move all but one in B to C. Now move all back to A. So all the elements except the ones unmoved in B and C will have a -(-) positive contribution to the sum.

    There is one more possibility. Assume c1 was infinite, so a -c1 is not affordable. So we move all Cs to B and then to A, and ignore moving B twice.
    Answer in this case will be Sum(A) + Sum(C) — Sum(B).
    Swap A, B, C and find the max case. 103801386

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

      This outline makes complete sense. Such a short solution for such difficult problem! Beautiful

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

My mistake from past 30 or so minutes

if(!isValley(idx, arr) && !isValley(idx, arr)){
}

instead of

if(!isValley(idx, arr) && !isPeak(idx, arr)){
}

and that happens despite using an IDE that warns against this :)

→ Reply
»
9 days ago, # |
← Rev. 2   Vote: I like it +135 Vote: I do not like it

Who wants to hear how we, the testers, trolled the cheating telegram group? Lot's of WA are cause of our efforts.

To those who want to help: Search for solutions of B that have a -25 anywhere in the code. Post their names here, they are all cheaters...

Reason why? Will make a blog post "soon".

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

    Upvote for calling testers of this round to be called batmen/women

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

    Yes, interested to hear that.

    → Reply
  • »
    »
    9 days ago, # ^ |
      Vote: I like it -50 Vote: I do not like it

    Couldn't you have made some good problems instead of doing this? Many masters have struggled to solve A, B?? The problems were too random. The setters of this contest should not be allowed for any further rounds.

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

      No they weren't. The problems were actually on easier side as later ones were standard. But it was diverse round.

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

Some thoughts after solving B:

If you wrote exactly once in bold why couldn't you write or let the sequence remain unchanged in bold as well?

Why can't n be just greater than 2?

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

    Agreed. Why would you want us to handle n = 1,2 separately? Just make n > 2.

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

    "In the second test case, the best answer is just to leave the array as it is." This is the sample explanation so it was mentioned there.

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

      The second test case will give the same answer when you do exactly one change (change the last 2 to 3). I agree that we should be more careful while reading the problem statement but I just thought it would have been better if it would have also been mentioned in bold that we can perform no changes also...

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

        spooky's comment would make more sense then. It was still mentioned in the explanation of sample cases.

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

        why is mentioning that no change is allowed sush a big issue. if u really wanted to do that you could just increase or decrease a particular number such that it does not make any difference. it was asking to print the minimum intimidation number not the steps required for that

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

    It says "You can change exactly one integer...", which has the meaning you can do, or do not.

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

    LMAO lol I had no idea what was wrong with my program and yeah, it was the fact I did not account for n = 1 and since I now use c++ instead of Java it did not say index out of bounds.... That's honestly stupid.

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

Why were almost all of the wrong answers related to test case 3 in Problem B ?!

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

    same bro

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

    I don't understand what's wrong with my question that I got 8 downvotes ! I just was curious about it And I just asked a question

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

Fcuk My Life

→ Reply
»
9 days ago, # |
← Rev. 2   Vote: I like it -33 Vote: I do not like it

tricky contest XD

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2 C I think I figured out... I was not sure though: is it just total — 2*(smallest + second_smallest) ? D was easier I thought...

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

    Nope for C counter example 1 1 1 3 4 5 Answer 6

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

      What is the counter-example? Like which ones belong to which list?

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

        It's like each list is of length 1. Take 3, 4 and 5 as elements of different lists.

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

        i dont know how to put "newline" in this comments. You have 1 element in each bag,in the first one is 3,the second 4 and the last one si 5.

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

          Two spaces after line is newline here

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

          All good — I understand your test. Looking at the submissions that seem to be passing for problem C, it seems like they used what I mentioned but adjusted it a bit for the edge cases :(

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

    No, I did that and failed test 3.

    Counter example can also be:

    1 1 1

    1 1 1

    Correct answer 1, we print -1.

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

    will fail on this

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

    except when smallest and second smallest are from same bag. In that case its min of that and total-2*(min sum in any bag). correct me If am wrong.

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

    You have two cases.

    1. total sum-2*(smallest + second smallest) (as you said). (Find the minimum of all 3 sets and take the smallest and second smallest)
    2. sum of two largest sets — the smallest set sum.

    Take the maximum of both cases

    → Reply
»
9 days ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

→ Reply
»
9 days ago, # |
← Rev. 3   Vote: I like it -6 Vote: I do not like it

In my opinion only fault was it was of 2 hrs . It should have been half or 1 hour more.

Problems weren't straight forward and samples didn't gave any hint and that's why accuracy in this contest was low. But contest wasn't that bad.

→ Reply
  • »
    »
    9 days ago, # ^ |
      Vote: I like it -41 Vote: I do not like it

    This is the worst contest I have ever seen

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

      Problems were difficult thus i think more time would have worked. Except difficulty was there any other issue ?

      Please don't down vote the blog , no one intentionally wants people to perform bad . At least we can appreciate that it was not typing test.

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

    Ya, even i solved the third problem exactly 2 minutes before the end of the contest and couldn't even read problem D

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

I am eagerly waiting to see the 3rd test case of problem "B".

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

Problem solved

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

I'm not exactly in a position to say this, but I think pretests for E were too weak. Let's define an array occ[1e9], where occ[i] represents the number of nodes with assigned number equal to i. Then my solution worked in O(sum(occ[i] ^ 2)), which on worst case is O(n ^ 2), and for some reason pass the pretests without much problem. I guess that's because my solution is too counter-intuitive to even think of, but allowing any kind of O(n ^ 2) to pass is in my opinion a sign of very weak testcases.

Note: I'm not saying anything about the main tests, I do hope that some in-contest hacks will be added to break my solution (post-contest hacks will surely break it). However, I suspect this is not the case since there were only around 100 accepted solutions for E, and I've not seen a hacked solution in-contest.

UPDATE: So thankfully (or not?), a new test was introduced to break my solution. My opinion holds though.

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

My wait for cyan continues....

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

;(

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

Respect ! To those who solved B from the first submission !

→ Reply
»
9 days ago, # |
← Rev. 3   Vote: I like it -10 Vote: I do not like it

Excuse me for saying this .. There are two points that make this contest bad : You have underestimated it as Div2 ,,,, The tests were not enough to fully understand problems

→ Reply
»
9 days ago, # |
← Rev. 4   Vote: I like it -14 Vote: I do not like it

Very interesting round, first time I've had to write a brute-force for A and B to debug my fast-but-WA code.

For those facing WA in B, here is a brute-force solution and a test harness in python.

Brute-force solution
def is_hv(A, i):
    if not (0 <= i-1 < i+1 < len(A)): return False
    if A[i] > max(A[i-1], A[i+1]): return True
    if A[i] < min(A[i-1], A[i+1]): return True
    return False

def count_hv(A):
    ret = 0
    for i in range(len(A)):
        if is_hv(A, i):
            ret += 1
    return ret

def ans_slow(A):
    ret = count_hv(A)
    for d in range(min(A), max(A)+1):
        for i in range(len(A)):
            new_A = A[:]
            new_A[i] = d
            ret = min(ret, count_hv(new_A))

    return ret
Test harness
import random
for _ in range(10000):
    N = random.randint(1, 50)
    tc = [random.randint(1, 20) for _ in range(N)]
    assert(ans(tc) == ans_slow(tc))
→ Reply
»
9 days ago, # |
  Vote: I like it -12 Vote: I do not like it

And we all thought 2021 will bring us happiness and positive delta

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

On the positive side, fast system testing.

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

system testing on nitros. so much lesser submissions relatively.

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

In C, can we take a and b from the same bag? The problem statement makes it sound like we can't, but then I don't really see how the answer to the second test can be 29...

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

    (7 5 4) (7 1) (2 9)
    (7 5) (7 (1 — 4)) (2 9)
    (7) (7 (1 — 4 — 5)) (2 9)
    (7) (7 (1 — 4 — 5 — 9)) (2)
    (7) ((1 — 4 — 5 — 9)) (2 — 7)
    ((7 — (1 — 4 — 5 — 9))) () (2 — 7)
    ((7 — (1 — 4 — 5 — 9) — (2 — 7))) () ()
    (7 — (-17) — (-5)) () ()
    (29) () ()

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

    Put the 9 in 2nd bag with the 1 in 3rd bag making it -8

    Put the 7 in 3rd bag with the 2 in 2nd bag making it -5

    So the bags now have

    7 5 4

    -5

    -8

    I think you will be able to make 29 from here.

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

For Task $$$B$$$ The maximum no of hill/valley we can destroy by changing a number is $$$3$$$ right?

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

    The best possible case is when changing an element, the answer decreases by 3, however, you have to be careful because many corner cases may exist.

    What I did was: for each position $$$i$$$, I have some options. Keep the value of $$$v[i]$$$ the same or for each $$$j$$$ $$$(i - 2 \le j \le i + 2)$$$, assign $$$v[i] = v[j] + 1$$$ or $$$v[i] = v[j] - 1$$$ or $$$v[i] = v[j]$$$.

    Therefore, I just have to iterate over all these possibilities and see which one is the best.

    Note that for each possibilty, I just need to recalculate the answer in the interval $$$[i - 2, i + 2]$$$.

    My code: https://codeforces.com/contest/1467/submission/103779093

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

is my idea for B totally wrong ? We can at most decrease the hills and valleys by 3 because at most we can affect 2 hills and one valley or 2 valleys and one hill how could I be wrong about that

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

    Can most decrease by 3 — correct.

    Code with too much ifs must not exist never. Sure thing either one case is missing or misprinted.

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

      I guess there's a stupid bug in my code that I didn't notice the idea is correct

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

    yes but when you have a hill and valley adjacent, flattening a valley may give rise to a new valley eg: 15 10 5 20 17, here when you try to get rid of valley 5 , you must make it >=20 but that would make 10 a new valley

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

      Yeah I tried to change the hill or valley to one of the two adjacent values and took the best change
      my code is just terrible I should have found a better way to code it

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

    Well that part isn't wrong

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

    Your code is so beautiful.

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

This contest was a trap. :))

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

Another Div 1.5 Contest.
Those who submitted A and B in one go without wrong answer on pretest 3. Hats off to their accuracy.

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

Rozen Maiden one-two finish with Suiseiseki :)

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

Next time Don't believe on a new setter too Quickly!!!:(

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

    Dude, he is making contests, actually making actual contribution to the community. What have you done to do the same? It's pathetic to see the entitlement which participants seem to have. Even I had a terrible contest, but I wouldn't take it out on the authors. Try to give constructive criticism, if possible or don't comment at all :)

    → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Very weak pretests for C :(

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

The contest is fun and annoying at the same time as "WA on pretest 3", corner cases killed my rating :)) Anyway, I like it :D

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

why contest div2 was too hard ???

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

Petition to not allow these setters ever again. The problems were too random and confusing.

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What type of div2B has <30% passing rate smh

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

    Yeah, many people got stuck on QB... QC is relatively easier imo

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

      If you don't spend a lot of time on B, that is...

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

Fastest system testing.

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

Just asking, did the testers give no feedback about the difficulty? It would be much better if there were one more problem between A and B.

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

Problem B WA3: When you replace a number, you may not improve the answer, but rather make it worse. Most likely, you only checked the destruction of valleys/hills.

Example:
1
6
6 7 10 5 7 9
answer(1), your answer(0)

Your program will replace the number 10 with a smaller number X. Then most likely there will be a hill (6, 7, X). It was necessary to make a separate check for this

→ Reply