TeaTime's blog

By TeaTime, 7 weeks ago, In English

Hello, Codeforces!

We are proud to finally invite you to participate in Codeforces Round #815 (Div. 2), which will start on Aug/18/2022 16:35 (Moscow time). You will be given 5 problems, one of which contains a subtask and 2 hours to solve them. We greatly encourage you to read all the problems.

Round is completely set by SIS (Summer Informatics School) students. During the camp our students did their best to prepare interesting and creative problems. You can check previous rounds prepared by SIS students: Codeforces Round #612, Codeforces Round #530, Codeforces Round #694.

People who participated in the creation of the round:

  • Special thanks for testing to: Dmitry Sweezy Pugachev, Alexey Mangooste Mikhnenko.

Also, we would like to thank:

  • Artyom123 for the brilliant coordination.
  • fastmath for improving one of the tasks!
  • meshanya for improving the structure of the contest!
  • MikeMirzayanov for great platforms, Codeforces and Polygon!

Scoring distribution: $$$500-1000-1250-(1500-1000)-2750$$$.

Good luck & have fun!

UPD1: Editorial

UPD2: Winners!

Div 2:

Div 1:

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

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

Gl Hf

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

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

      :'

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

      why in system testing our answer is get TLE or wrong? because of it's added new test cases?

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

        During the contest time, your code successfully run agnist some test case. After the contest, your code again run agnist rest of the data set. But it took extra time than time limit, that’s why you got TLE.

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

Waiting for it!

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

Not as a tester, I know that the problem is good since the last contest by SIS students was great.

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

    So is your spacecraft on the orbit?

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

    so next time I see your comment about problems are good without testing, I don't participate in that round...

    xd

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

    ObservationForces

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

Unusual time, I like this! However, there are only five questions. My friends may be able to finish all in one second and then start sleeping. :O zzZ

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

[Deleted]

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

As an author, I am author.

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

    As a SlavicG fan, I will hope that this will not be another speedforce round.

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

    Why 1 hour earlier?

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

    It seems to say everything, and it seems to say nothing

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

      Greet from China!

      It's very good for Chinese because it's 9:35 p.m in China at this time, Not 10:35 p.m. !

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

    Username checks out

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

as a tester, I tasted this round.

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

Artyom123 5 problem round. Have to participate!

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

hope to specialist in this round

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

Hope to pupil in this round

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

    Oof, 1199. You'll get to it next time, keep it up!

    Also, there will be recalculation presumably. So, probably you will get +1 after it :D

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

I think problem C has a subtask.

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

Hell yeah! its TeaTime!!

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

As a participant, I will participate.

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

I hope to use this round to go back to Master.

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

Great!This Unusual time allows me not to sleep so late :)))

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

Hope to candidate master in this round

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

Good luck to every one!

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

Hope to pupil in this round

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

Coders Time.

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

As an entrant, I think I should now go and write the question

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

Finally there is a round of normal time for UTC+8! But,there is only 2h but not 2h+15min.May I think it's a little bit easier than round #814(Div.2)? I am just guessing,so it's may easily wrong(

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

    Also,hope to Expert(even though there's 167 between my rating and the base rating of an expert(1600) in this round.

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

      hope to expert ++;

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

        I can't get $$$\color{blue}{\tt{Expert}}$$$, because I'm slow on C.

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

          I nearly reached expert yesterday.Finally my rating is 1594

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

Hope to expert in this round

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

Why the announcement does not mention that the time is unusual, and why is it not displayed as client local time?

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

Hope that the round provided by SIS students is really friendly. Everybody +154!

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

This will be my first contest which is set by SIS students :))

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

Wow! It's TeaTime round!

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

I just need 17

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

Note the unusual time

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

[Not relevant]

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

As a participant, I am excited for this round :)

»
6 weeks ago, # |
Rev. 6   Vote: I like it -14 Vote: I do not like it

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

    Son, there are other CP websites other than this amazing platform so if you are so mad just don't come here again it is that simple.

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

    finally someone said it. this toxic behaviour is promoted on codeforces just so they can "get back at you" and put you in a bad light. now you're getting downvoted because people are mad. classic codeforces russians but what can you expect

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

Just a simple question: is the link of "Codeforces Round #815 (Div. 2)" in "We are proud to finally invite you to participate in Codeforces Round #815 (Div. 2), which will start on Thursday, August 18, 2022 at 13:35." from the post above correct? It says "https://codeforces.com/blog/entry/103966" here.

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

    yeah, that's a clear copy-paste error... that they still haven't corrected... (said after mistakenly clicking on it n times)...

    edit: and now it's been fixed to link to this announcement post...?

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

5 problems and 14 authors :/

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

Hope to master this round!

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

hopefully fast A,B,C

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

Almost woke up late, didn't realize the one hour early unusual timing, almost missed the contest.

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

    Me too. I hate the changes in the time of the contest. At least they should write "Please Note the unusual time"

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

Was waiting for the contest to have some fun, turns out that can't even solve problem A.

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

    And now feel very stupidly for forgetting 5th grade math.

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

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

    Me after 1 hour after not even able to solve A:

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

      A little joke : I wrote p % q when q = 0 when I solve A.

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

    D2*

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

      can u plz give some hints for d1 i was totally blank for it during contest no Clues and how to think for this kind of problem??

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

        I thought because all a[i] < 200 it won’t matter a lot in the xor operation because the 8th bit and higher will not be affected (2^8 xor a[i] ≈ 2^8), so i divided the array in blocks of size 2^8(256), then cannot exist a subsequence in more than one block (indices i < j) then a[i] xor j < a[j] xor i, and finally eliminate a[] because its small and j < i its false, so you only need to run a standard LIS algorithm inside every block and return the largest subsequence among them.

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

missed the contest because of unusual start time, thanks.

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

I am so tilted in this round. This is my first time giving up when there's still an hour left. I spent 20+ mins but still can't solve A. It takes me much less time to solve B and C. For D, I dont even understand the problem statement for the first test case.

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

    How did you approach B? Took me a long time (~50mins) for B.

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

      Just use Max and sec Max and min and secMin elements for ans

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

Please highlight in bold about unusual start time. Missed the round >︿<

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

Problem D, what about the array B meaning?

It looks like array B is a index of array A, but I find all page with ctrl+F, not found the word "index" in problem statement(found in problem note, but not useful).

So, the problem writter, do you know what "subsequence" mean? Read about your sentence: "is a subsequence of length m of the array a.", the reviewer of this problem really think that express the meaning correctly?

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

    I asked a similar question and it turns out that b is actually a index of array A.

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

      Only after reading this thread, I understood the question properly. But, is it allowed to discuss about the problem statement during the contest ? Just wondering. :?

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

        I know it so I just repeated the problem writters' words. Seems lots of people got stuck on it.

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

    I asked the same thing in dashboard help window and author replied "Read statement again". Like seriously???

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

    sameeee. I wasted around 1 hour coding the solution and later realised it's index array.

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

I think the problem A is harder than problem B&C...QWQ

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

speedforces, penaltyforces, guessforces.

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

    Not really, but I actually did fail on D1 for 4 times. For misunderstanding!

    I just think the gap between D1 and D2 is a bit big.

    B and C are much easier than A!!!

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

      for me c>A>B i don't know how u feel C easier than A

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

        I just spent 2 min thinking about C. But I spent 6 min to think of the answer of A!

        Maybe just for me... Stuck on A

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

The arrangement of difficulty is really puzzling.

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

I can't solve A !! ◑﹏◐

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

    Same !! only got the base case if one of the numerartor is 0 print 1 and if both numerator 0 then 0 lol:<

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

    1 hour not solving A and finally gave it up

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

wasted all my time on D1 by assuming that b array contains elements of array a such that elements belongs to [0, n). After seeing tc 1 realised that it's a index array. Was it mentioned in the problem?

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

What's the pretest 3 of D fix? Pretty convinced my 2D DP solution is correct (trying to match bits one by one and storing maximum for each pairing of index 'bit prefix' and 200 last values). Thanks.

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

    I can't see your solution, but seems you overcomplicated. Just do these loops:

    for (int i = 0; i < n; i++) {
        for (int j = i - 400; j < i; j++) {
            ...dp transition...
        }
    }
    

    $$$a \oplus b \in \{a - b, a + b\}$$$ hence $$$a_j \oplus i < a_i \oplus j \implies i - 200 < j + 200 \implies j > i - 400$$$. Probably, there is some $$$\pm 1$$$ mistake.

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

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

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

Implementation wise, this one was the easiest contest in recent times . (Considering A, B and C problems)

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

what subsequence mean???

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

Div2 D Ok, we can use dp to find the longest sequence, but how do we find all such pairs of numbers that meet xor restriction in a good time? Or there is another approach?

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

    Use 01-Trie to optimize the transition.

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

      What are transitions? and how we can optimize them?

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

    I couldn't solve $$$D2$$$, but you definetely can't find all transitions (pairs, that satisfy inequality). Simple test gives, that there are $$$O(n^2)$$$ transitions.

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

    using 01-trie is a good choice

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

I always fall behind on problems like A because people submit random guesses. Honest thanks for the weak pretests, they are good from time to time for punishing this strategy.

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

In B

$$$max(a_{1}, a_{2}, ..., a_{l - 1}, a_{r + 1}, a_{r + 2}, ... ,a_{n}) - min(a_{1}, a_{2}, ..., a_{l - 1}, a_{r + 1}, a_{r + 2}, ... a_{n}) + max(a_{l},...,a_{r}) - min(a_{l},...,a_{r})$$$

I don't know if it's just me but it took me a while to notice that $$$a_{l}...a_{r}$$$ were missing in the first $$$2$$$ expressions. Stating it in words would have been nice. e.g. The max/min without the subsegment $$$a_{l},...,a_{r}$$$.

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

    +1

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

    What was your understanding of the meaning of the formulars instead?

    I mean, at first I did not understand them at all for more or less same reason. But there is also no other meaning possible, so I understood after second or third reading.

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

I don't understand Problem D.

In the example 1,the last factor is equal to n.

But the Note says "In the first test case, we can pick the whole array as a beautiful subsequence".

Why?

Please forgive my poor English.

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

    In the first test case, you can pick the whole index array [0, 1] as a beautiful subsequence, not the array itself.

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

      I see. Thank you.

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

      Thanks, I was not able to understand the problem until I read your comment.

      The words is a subsequence of length m of the array a. were confusing me so much that I didn't even think that it could be an index array!

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

The word "subsequence" in D is quite misleading...

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

Why does the subsequence of an array is its index array???

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

What is the intended complexity of $$$D1$$$? I tried an algorithm of $$$O(N*log(N)*max(a[i]))$$$ using trie but it was not enough to pass the time limit.

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

    I think it is O($$$n \times 200 \times log(200))$$$).

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

    For each i try only such j that ij <= 600 (this constant is even less).

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

    Maybe $$$O(n\cdot 256)$$$ ?

    By seperating $$$a$$$ into blocks with length of 256, and do $$$O(n^2)$$$ dp.

    Because $$$a_i\le200$$$, index>>8(divided by 256) doesn't change by $$$\oplus=a_i$$$, so we can't choose any indices from different blocks.

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

    Thanks everyone. Your insights are appreciated.

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

What is the hack for A? Is it related to precision issues?

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

    +1

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

    There is no "the hack". I hacked four times, each time in a different way. There was no typical mistake, each wrong solution was just random wrong logic.

    My hacks:

    1 1 2 3
    1 5 3 10
    3 5 1 7
    3 1 5 1
    

    Precision is definitely not an issue unless you actually calculate in floats/doubles, in which case you 100% can be hacked.

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

How to solve D1, D2?

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

    trie, think of $$$(i, A[i])$$$ as one thing, at bit $$$b$$$ you will have $$$(i_b, A[i]_b)$$$ which you can think of as a number in base 4, these four numbers form a partially ordered set where each number has exactly one number less than it (so check that in dfs) and two numbers equal to it so recurse on them, to reduce the complexity from $$$\mathcal{O}(n \times MAXA)$$$ to $$$\mathcal{O}(n log(n) + n log(MAXA)))$$$ notice that you can group 0 with 3 and 1 with 2.

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

    D1 直接暴力

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

it took me 1 hour to understand that the sequence b in problem D is the index of a, and i solved it 3 minutes after the end of the contest. confusing description ruined my contest! worst contest I've ever attended

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

This is literally my first time not able to solve any of the problems :’)

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

Imagine 30 high rated programmers preparing a round and everyone agree with a wrong definition of subsequence :/

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

A fuckload of TLs for C INCOMING!!!

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

    Okay, solutions that do not use cumulative sums seem to pass. Probably, TL should have been more strict.

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

Despite the confusing description, D2 is the best problem I've seen in CF div.2 rounds. I think using 01-trie to optimize the transition is quite tricky for me :)

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

Had an idea for D1, but was not able to debug it in time D:

Finally positive delta, so i am not complaining. Nice set overall, regardless B and C being easier than A.

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

Get really confused.

In problem D, the statement says that b is a subsequence of length m of the array a. How can $$$b$$$ be a subsequence of $$$a$$$? In the first case of the sample, how do $$$[0,1]$$$ turn to be subsequence of $$$[1,2]$$$?

I spend more than an hour on the version of $$$b_i$$$ is an element of sequence $$$a$$$, not until finding my long code not outputing the correct answer to the sample test. There's even no update or clarification!

It's maybe true that this is explained in the sample. However I do think this kind of description is annoying, as I, urgently, was in a hurry trying to solve the problem and not aware of the misunderstanding.

I should have got an increase in my rating. Anyway... I'm realy down in the dumps. :(

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

    I think probably not only me were confused with the description. Why none of the numerous writers and testers pointed this out? More than 30 names are mentioned, that's a large number even compared to other contests.

    I'm pissed off a bit because there is neither descrition updates nor clarifications during the two-hour contest.

    In the previous contests, I find the clarifications really detailed, sometimes even nagging. However I got nothing this time, when I really nead them. I think a simple short clarification can get me back to track.

    Problems in contests are not like normal training problems, a slight misunderstand can have significant influence on some (maybe one or two, but probably a few) participants.

    Sorry for the bad mood brought to the comments. I promise I will make more contribition to the codefoces society to make this up.

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

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

    My solution to the misunderstood version of D1 has come out. The link is here. :)

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

NO WAYYYY T-T JUST GOT FST ON B CAUSE OF JAVA SORTING I'm so sad. ;(

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

Many fst in problem A...

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

The pretest of A is so weak!

If you don't use long long,you will also pass the pretest!

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

took 10 minutes to figure out what problem D means, tried and failed to solve it in the rest hour, and realized that I misunderstood it after the contest:)))))

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

I'm quite sure there must be a severe mistake in the D1 statement. It describes $$$b$$$ as a subsequence of $$$a$$$. By definition of subsequence, the elements in $$$b$$$ must be in $$$a$$$, and the relative order of the elements in $$$b$$$ are the same as the relative order of the elements in $$$a$$$.

However, right away from sample-input #1, we have a contradiction. The example shows $$$1 \oplus 1 < 2 \oplus 0$$$, which means the $$$b$$$ values are $$$1$$$ and $$$0$$$. But 0 isn't in the array! How can a subsequence of an array with no zero contain a zero???

I was also confused by test-case #2, where they selected indices 1, 2, and 4. Okay, these are in the array this time, but not in that order! The relative order in array $$$a$$$ is 2, 4, 1. So [1, 2, 4] is not a subsequence of $$$a$$$. I thought they might have meant $$$[2, 4, 1]$$$, but they also wrote that $$$b$$$ is strictly increasing. How does this make sense?

I had over an entire hour after solving C, and could not understand this. Asking a question yielded the generic response of "Read the problem statement", but no matter how much I read it, I couldn't make sense of these.

It was only after the contest, from another comment, that mentioned that $$$b$$$ is actually simply an increasing set of indices of $$$a$$$, completely independent of the values of $$$a$$$. This is not a subsequence. Nowhere in the problem does it mention that $$$b$$$ was a set of indices.

This is an enormous mistake that prevented me (I'm sure many others), from being able to even understand the problem. Not only was there a severe mistake in the original statement, but what's even worse is that this was never corrected throughout the contest, and even the inquiries about this issue were responded with a generic "Read the problem statement". If you're getting questions about a statement, maybe you should like, actually read the statement yourself and figure out why people aren't understanding it, and then correct the problem statement and humbly clarify the issue, as opposed to giving a generic "Read the problem statement" response, as if the questioners are too stupid to understand that a "subsequence" actually refers to a set of indices!!!

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

    But the meaning of subsequence in this problem is given in the problem statement?

    Spoiler

    Just because the word "subsequence" usually mean some element of array in same order doesn't mean it will be the same in this problem. But yeah i agree it can be confusing. Maybe it will be better if without the word "subsequence", just array B.

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

      My understanding was that it defined $$$b$$$ as a subsequence of strictly increasing elements of $$$a$$$ such that they are all in the range $$$[0, n - 1]$$$. This is entirely consistent with the statement you highlighted. In other words, I interpreted it as a restriction on what constitutes a valid subsequence for this problem as opposed to redefining subsequence.

      The definition of beauty referred to $$$a_{b_p}$$$ and $$$a_{b_{p + 1}}$$$, so restricting $$$b$$$ as being a subsequence with values in range $$$[0, n - 1]$$$ was perfectly justified. There was nothing in the problem statement that hinted that my interpretation was flawed. My interpretation was a perfectly valid problem that I would probably have written in the exact same way as this given problem statement, but it was not actually the interpretation that was intended.

      What would have been correct is if, instead of "a subsequence of length $$$m$$$ of the array $$$a$$$", they wrote "a subsequence of length $$$m$$$ of the indices in array $$$a$$$.

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

        I see, i get your interpretation is that array B is :

        • Subsequence of array A (using the usual definition)
        • Increasing
        • Value [0, n - 1].

        But actually the sentence i highlighted mean array B, with property increasing and value between [0, n - 1] is the definition of subsequence, nothing else.

        Anyway now we know the problem, lets upsolve it! :D

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

I wasted more than half an hour on D1 because of the problem statement. Still don't get how a subsequence of 'a' implies a collection of indexes rather than the elements themselves.

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

Why the output in E is always either 1 or 2 if number of distinct elements in the input is greater than k? Any way to prove that?

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

    Off the top of my head.

    You can increase length of the first square in top-left (red square) until increasing it one more time reduces the number of distinct values below $$$k$$$ (green square). Then as the second square, you can take the blue one and increase its length until you reach the requirement. As the blue square reduces the number of distinct values by at most $$$2$$$, you might be off by one. But you can choose to write a completely new value or an existing value in the square depending on the situation you're in, so you can meet the requirement.

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

    You want to choose 2 squares such that by removing these squares, you remove all but $$$k$$$ or $$$k - 1$$$ colors from the grid.

    Consider for each $$$\ell$$$ the square that has the top left corner at the top left corner of the grid. Each of these squares removes at least as many colors as the previous one. The first square removes 0 or 1 colors and the last square removes all colors. If one of these squares removes exactly the correct amount of colors, we are done.

    Otherwise, there must be a point where the $$$\ell$$$-th square removes too few colors and the $$$\ell + 1$$$-st square removes too many colors. Now you can make all of those shapes with 2 squares:

    At each step you remove at most 2 more colors and transition from the $$$\ell$$$-th square to the $$$\ell + 1$$$-st square, so at some point exactly $$$k$$$ or $$$k - 1$$$ colors are left after removing.

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

looks like if you use division on A it will FST

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

Problem A was more difficult than problems B and C for me

I managed to solve B and C but could not solve A

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

weak pretest for problem A.

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

Solve A in 10min — As problem A, not good enough.

Get FST — Good job.

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

About D's statement:

Obviously, neither "b is a subsequence of [0, 1,... n — 1]" nor "b is a subsequence of indexes of a" is way more precise than "b is a subsequence of length m of the array a". So why does someone writes things like "b is a subsequence of a" in the statement and don't make any public clarification?

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

    You pointed it out and yet they didn't bother updating the statement? Wow.

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

Confusing sample descriptions+weak system tests, gonna have a lot of fun losing 100+ points

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

    D was so confusing spent 1 hr just reading it.

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

I don't think the description of problem D is reasonable. It writes that array $$$b=[b_0,b_1,b_2,...,b_{m-1}]$$$ is a subsequence of the array a. However, according to the exapmle, we can find that the elements in array b are indices but not elements in array a, which means array b isn't a subsequence of array a. To be honest, this bothered me a lot during the contest.(╥_╥)

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

Sad view don't open it

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

TeaTime could you update link to contest? Now it refers to 804 contest blog

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

    Now it refers to current blog but still not to contest

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

168821144

Problem B, why this submission is TLE. Java

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

this is my first time commenting in CF discussion section this is my code for div 2 C Corners... but I got a fail on pretest 2. I tried debugging and solving but wasn't able to do it.

below i have also explained my code... if you can have a look. And tell me what's wrong with it. thanks

. . . . .

from collections import defaultdict

def solve(): t = int(input())

while t:
    t-=1
    R, C = [*map(int, input().split())]
    grid = [ [ 0 for i in range(C) ] for _ in range(R) ]
    count,zero  = 0, []
    # taking string as input and putting them in grid
    for r in range(R):
        temp = input()
        j = 0
        for c in temp:
            grid[r][j] = int(c)
            if c == "1":
                count  += 1
            else:
                zero.append([r,j])
            j+=1
    # if count of 1 == 0 printo 0. if count == R*C print (R*C -2)
    if count == 0:
        print("0")
    elif count == (R*C):
        print((R*C)-2)
    # else there are some zero in the matrix 
    else:
        # directions are to check if we can make a L shape that contains all 0's
        #   D1: |     D2:   |         D3: 0--        D4: --0 
        #       0--       --0             |                |
        dir1 = [ [0,1], [-1,0] ]  
        dir2 = [ [0,-1], [-1,0]]
        dir3 = [ [0,1], [1,0] ]
        dir4 = [ [0,-1], [1,0] ]
        temp = 0 # to count maximum Zeros in L shape

        for i,j in zero:  # list contains x-y co-ordiate of Zero 
            p = 0
            for dx, dy in dir1:
                if 0 <= i+dx < R  and 0 <= j+dy < C:
                    if grid[i+dx][j+dy] == 0:
                        p += 1

            temp = max(p,temp) # temp to store max number of Zeros
            if temp == 2: # if we get a L shaped Zero we terminate
                break

            p = 0
            for dx, dy in dir2:
                if 0 <= i+dx < R  and 0 <= j+dy < C:
                    if grid[i+dx][j+dy] == 0:
                        p += 1

            temp = max(p,temp) # temp to store max number of Zeros
            if temp == 2: # if we get a L shaped Zero we terminate
                break
            p = 0
            for dx, dy in dir3:
                if 0 <= i+dx < R  and 0 <= j+dy < C:
                    if grid[i+dx][j+dy] == 0:
                        p += 1

            temp = max(p,temp) # temp to store max number of Zeros
            if temp == 2: # if we get a L shaped Zero we terminate
                break

            p = 0
            for dx, dy in dir4:
                if 0 <= i+dx < R  and 0 <= j+dy < C:
                    if grid[i+dx][j+dy] == 0:
                        p += 1

            temp = max(p,temp) # temp to store max number of Zeros
            if temp == 2: # if we get a L shaped Zero we terminate
                break

        if temp == 0:  # there are no Two zero Adjacent so maximum move will be count - 1
            print(count-1)
        else:    
            # if temp is 1 it means two 0 are neighbors so we perform (Number of 1 in input) i.e count operation
            # if temp is 2 it means L shape is found. so we perform (Number of 1 in input) i.e count operation
            print(count)

solve()

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

B has more accepted solutions than A::) ...Weak Test cases but still, IMO it was a good question.

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

The editorial link is broken, says i'm not allowed to see the editorial

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

Can someone pls help me on this

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

Amazing. We have successfully made two LGM's massively overcomplicate a Div. 2B. Um_nik: 168820726 jiangly: 168847264

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

Can someone explain why my solution that just check for each i(0 ... 200) the last 3 indexes they were met in the array gives AC? I think the tests are just weak but maybe it can be proven in some way. 168854584

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

    Indices will grow larger than the elements themselves, and after every 256 elements, 8-bit will flip, and all previous elements are invalidated, because the most significant bits of new indices will be larger than any previous indices. Since a_i <= 200, they won't be affected by xor. So probably weak tests.

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

Editorial is not opening!!!!!!!!!!

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

ABC=500,500,500

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

Problem A: why does this code 168868045 gives me wrong answer in 13 with GNU C++20 (64)

while the exact same code gives me accepted with GNU C++14 168869739

not my fault i guess !!

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

    Because you are calculating with floating-point numbers, and they're different in 32-bit and 64-bit systems.

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

      how could i know ?

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

        The better lesson to take away from it is to never trust floats. Don't use floats unless you absolutely need to. And even then be very careful with them.

        It's pretty rare on CF to need to use floats, especially on easy problems. There's no need to use floats in this problem, for example the fractions are equal if and only if $$$ad = bc$$$.

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

In problem D1 there is no test, where the answer is 1.

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

OFF topic question:VK Cup 2012 round. Problem:158B
Problem name: Taxi ive written almost 90 line code but ive seen lot people make an easy equation. here it is written below with code

include

using namespace std; int A[5],N,i,t; int main() { cin>>N; while(cin>>t) A[t]++; A[1]=max(A[1]-A[3],0); cout<<A[3]+A[4]+(A[1]+2*A[2]+3)/4; }

so the equation is A[3]+A[4]+(A[1]+2*A[2]+3)/4 may i know why they added 3 with A[2] ?? i mean how should i practice math to think like this and make this kind of equation. and still im confused why they added 3. if you have any suggestion and ans in your mind please share with us. regards.

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

Wasn't the 1st two test cases of the 2nd question wrong? In the 1st test case for l=7 and r=8 I think maximum should have been 6 and not 5. Sorry, if I am wrong

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

For the first time, I was able to solve 4 problems in a div 2 contest :)

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

Hi Where can I see discussion one each problem.

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

F*ckkk, failed problem A because dividing floating point error. a/b==c/d, I should have used a*d==b*c

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

In Problem C, based on the constraints, I first came up with a Greedy Set-based NlogN solution, and without looking for any observations, decided to start implementing it, only to narrowly get TLE on TC 8 (even after multiple failed attempts at optimization).
I think the unusual Time Constraint of 1 second was a deliberate thing to prevent these kinds of solutions from passing.
While I agree that the intended solution is a lot more simpler and elegant, because of only a slightly higher time complexity, and because it required a lot more effort, the authors should have also allowed the greedy NLogN solutions to pass.

My Submission

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

    but c can be solved by a o(n*m) solution...

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

My feedback (only ABC problems):

Good first three problems, especially B. I liked A too, but I don't understand why it got so few solves. C felt little easier that normal Div.2 C problem.

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

GreedyForces (?) It was a nice round, thanks!

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

It seems like A, B and C should be reordered.

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

so i came at 8 and so this round already running.

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

I like this round, problem D was really interesting! Although the description was a bit confusing.

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

@MikeMirzayanov Hello, I participated in Yesterday's Codeforce Round #815 (Div2) I solved the Question C, which was "Corners". I solved it using Python

And During System testing, it gave TLE. Why?????

The Constraints were simply mention that "n and m (2≤n,m≤500)". And my solution was of N*M. So how can i get TLE.

Just Because using Python, I'm getting TLE. And after the contest, when I tried using C++ the same logic, solution gets accepted.

Does it is a fair game. The one who use C++ get solution accepted but one using python get TLE. Question should be set according to every language. Not just keeping few languages in a mind. What Should I do Now?? The Contest is now over and rating gets decreases just because of that One Question Which was right but got TLE due to Language Barrier.

Hope to get some positive response from your Side Admin. And I need support from the community.

Solution:- https://codeforces.com/contest/1720/submission/168856963

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

    Try using PyPy I guess, although I have no experience with Python but I have seen many blogs and comments complaining about the slowness of Python and the answer always be: "Using PyPy instead"

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

You missed the part note the unusual time

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

Hello, the system says that I cheat on C but I don't what should I do? somebody help plz

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

Attention!

Your solution 168861333 for the problem 1720A significantly coincides with solutions saubhagyaprakash/168825261, ajis207/168825753, Raaghav909/168833485, gla_191550059/168835636, akm1002/168836385, 6615-Bhumeera/168858644, MARSHALMATHERS/168861333. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

This has happened because problem A of DIV2 rounds is trivial most of the times and the code is of 4-5 lines so it is just a coincidence that someone wrote a similar thing which I did even if you would go through a number of other submissions you would find that the logic is nearly same and since it is a small code it gets matching for a number of people.

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

    I agree. I've recieved similar mail, someone's code is very similar to mine. (168808729, 168826905)

    Looking at the skipped submissions of 1720A, the codes are all quite similar. It seems necessary to re-check the skipped submissions.

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

Just got a mail related to plag. Some The_MazeRunner;'s code for the first question of div2 got plag with my code. I dont know this guy and its was a total coincidence. The problem was based on the concept of modulo. Thus to shorten my code length I used some variables x and y. and to make the modulo good I added if else conditions. Which was obvious. The logic of the code was simple and this plag is just a coincidence. I am Sharing the comparison of the codes. The logic is same with some different variable names. Just see my other input techniques I used to write the codes as such. Please help me this time. I will be grateful. And roll my ratings Back.The photo of Comparison

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

Hello, this is itskartikp. I got a violation in Codeforces round #815. But all the code written is entirely mine, I haven't violated any of the rules. Maybe the questions were redundant, and most of the people came up with similar approach. I haven't violated any of the rules or used any unfair means.

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

i got mails regarding coinciding codes in two accounts but actually both the accounts are mine ebshu21 and rony19 both are my accounts and i submitted the solutions for the contest problems during the contest from both my accounts but now that contest is not rated for me i my rating got reduced. please help me out. i can give all sorts of proof i will also write this same comment from that other account.

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

i got mails regarding coinciding codes in two accounts but actually both the accounts are mine ebshu21 and rony19 both are my accounts and i submitted the solutions for the contest problems during the contest from both my accounts but now that contest is not rated for me i my rating got reduced. please help me out. i can give all sorts of proof

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

    now please roll back my rating points atleast for my rony19 account , actually this ebshu21 account is my new account please roll back my ratings in my old account rony21