Codeforces Round #815 (Div. 2)

2 years ago, # ^ |

absolutely right，up vote this round!

→ Reply

2 years ago, # |

+44

as a tester, I tasted this round.

→ Reply

Nxxlt

2 years ago, # ^ |

+25

How does it taste?

→ Reply

Luminolic_Black

2 years ago, # ^ |

I bet it's sweet and spicy ;)

→ Reply

2 years ago, # ^ |

you’ll find out:)

→ Reply

2 years ago, # ^ |

like a shit

→ Reply

Nxxlt

2 years ago, # ^ |

Why? I tasted it too, but it was so spicy and good

→ Reply

2 years ago, # ^ |

too small points for d2

→ Reply

Nxxlt

2 years ago, # ^ |

hm, if u solved D2, you solved D1 too, so you get 2500 points, its pretty much

→ Reply

efimovpaul

2 years ago, # ^ |

nice profile pic bro

→ Reply

chromate00

2 years ago, # ^ |

are you sure you are a tester and not a sommelier?

→ Reply

kozliklekarsky

2 years ago, # |

-21

Artyom123 5 problem round. Have to participate!

→ Reply

Halym2007

2 years ago, # |

← Rev. 2 →

hope to specialist in this round

→ Reply

Number_72

2 years ago, # ^ |

hope to pupil

→ Reply

aniketrajput25

2 years ago, # |

Hope to pupil in this round

→ Reply

AVdovin

2 years ago, # ^ |

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

→ Reply

Tushar11

2 years ago, # |

-18

I think problem C has a subtask.

→ Reply

Number_72

2 years ago, # ^ |

How come?

→ Reply

PaulMsk

2 years ago, # |

As a participant, I will participate.

→ Reply

L1nn

2 years ago, # ^ |

orz

→ Reply

Tom66

2 years ago, # |

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

→ Reply

Tensei8869

2 years ago, # ^ |

Amen

→ Reply

fscbti

2 years ago, # ^ |

You will do it ! :)

→ Reply

wangxinyue

2 years ago, # ^ |

Best wish to you :)

→ Reply

Tom66

2 years ago, # ^ |

Oh I missed this round and used the next round to go back :)

→ Reply

TheCliffSwallow

2 years ago, # |

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

→ Reply

tht.onepunchac168

2 years ago, # |

Hope to candidate master in this round

→ Reply

Karatinos

2 years ago, # |

← Rev. 3 →

Good luck to every one!

→ Reply

actual_truthseeker

2 years ago, # ^ |

it took you 3 edits to type 5 words

→ Reply

eugalt

2 years ago, # ^ |

← Rev. 2 →

When there are supposed to be four words.

→ Reply

rion_cse

2 years ago, # |

Hope to pupil in this round

→ Reply

rick3300

2 years ago, # ^ |

Congrats bro on becoming pupil!!

→ Reply

ajstyle_

2 years ago, # |

Coders Time.

→ Reply

nowadays-

2 years ago, # |

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

→ Reply

LiveDreamer

2 years ago, # |

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（

→ Reply

LiveDreamer

2 years ago, # ^ |

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

→ Reply

2 years ago, # ^ |

hope to expert ++;

→ Reply

Eric12

2 years ago, # ^ |

← Rev. 2 →

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

→ Reply

2 years ago, # ^ |

I nearly reached expert yesterday.Finally my rating is 1594

→ Reply

2 years ago, # |

Hope to expert in this round

→ Reply

karanarjunjr

2 years ago, # ^ |

Wish you the most of luck :)

→ Reply

2 years ago, # ^ |

← Rev. 2 →

+18

I didn't have enough luck to read the starting time... woke up an hour too late.

→ Reply

eugalt

2 years ago, # |

← Rev. 3 →

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

→ Reply

2 years ago, # |

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

→ Reply

Go8

2 years ago, # |

I just need 17

→ Reply

SalmaHatem_

2 years ago, # |

+20

Note the unusual time

→ Reply

YariKartoshe4ka

2 years ago, # |

← Rev. 2 →

[Not relevant]

→ Reply

Acclerated_Coder

2 years ago, # |

← Rev. 6 →

-14

‎

→ Reply

Koka

2 years ago, # ^ |

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.

→ Reply

Satrpx

2 years ago, # |

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://mirror.codeforces.com/blog/entry/103966" here.

→ Reply

bjy

2 years ago, # ^ |

← Rev. 2 →

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...?

→ Reply

Satrpx

2 years ago, # ^ |

← Rev. 3 →

Yeah. Please fix it TeaTime. (Now it's https://mirror.codeforces.com/blog/entry/106074)

Edit: Now fixed :)

→ Reply

TeaTime

2 years ago, # ^ |

Sorry, fixed it in russian version but forgot to fix in english. Now it should work!

→ Reply

Rudro25

2 years ago, # |

+28

5 problems and 14 authors :/

→ Reply

Graygoo_401

2 years ago, # |

Hope to master this round!

→ Reply

2 years ago, # ^ |

+16

Congrats!

→ Reply

Graygoo_401

2 years ago, # ^ |

← Rev. 2 →

thanks!

→ Reply

2 years ago, # |

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

→ Reply

Omar_Hafez

2 years ago, # ^ |

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

→ Reply

ldyllic

2 years ago, # |

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

→ Reply

ldyllic

2 years ago, # ^ |

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

→ Reply

black_trees

2 years ago, # |

← Rev. 3 →

+16

→ Reply

frissky9

2 years ago, # ^ |

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

→ Reply

black_trees

2 years ago, # ^ |

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

→ Reply

mc._cari

2 years ago, # ^ |

D2*

→ Reply

rishisgsits_22

2 years ago, # ^ |

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??

→ Reply

mc._cari

2 years ago, # ^ |

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.

→ Reply

kriepiekrollie

2 years ago, # |

missed the contest because of unusual start time, thanks.

→ Reply

DreamingTheDream

2 years ago, # |

+21

Please highlight in bold about unusual start time. Missed the round ＞︿＜

→ Reply

Pentonic

2 years ago, # ^ |

+10

You lucky bastard!....saved from suffering..xD

→ Reply

shellspicker

2 years ago, # |

+39

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?

→ Reply

2 years ago, # ^ |

+19

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

→ Reply

arutsudar

2 years ago, # ^ |

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. :?

→ Reply

2 years ago, # ^ |

← Rev. 2 →

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

→ Reply

harpreet1237

2 years ago, # ^ |

+11

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

→ Reply

aKILLL

2 years ago, # ^ |

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

→ Reply

sdnu_dawn

2 years ago, # |

+11

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

→ Reply

FC_Viiiiictor_K

2 years ago, # ^ |

→ Reply

Eason9002

2 years ago, # |

-35

speedforces, penaltyforces, guessforces.

→ Reply

HappyIvan

2 years ago, # ^ |

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!!!

→ Reply

rishisgsits_22

2 years ago, # ^ |

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

→ Reply

HappyIvan

2 years ago, # ^ |

← Rev. 2 →

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

→ Reply

Black_Fate

2 years ago, # |

The arrangement of difficulty is really puzzling.

→ Reply

Black_Fate

2 years ago, # ^ |

Not to blame the problems themselves, only the arrangement.

→ Reply

SalmaHatem_

2 years ago, # |

I can't solve A !! ◑﹏◐

→ Reply

ooh_my_code

2 years ago, # ^ |

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

→ Reply

SalmaHatem_

2 years ago, # ^ |

Yes that's right !!{{(>_<)}}

→ Reply

aKILLL

2 years ago, # |

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?

→ Reply

nichke

2 years ago, # |

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.

→ Reply

Igor_Parfenov

2 years ago, # ^ |

+14

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.

→ Reply

LZX_OVO

2 years ago, # |

what subsequence mean???

→ Reply

Torenu

2 years ago, # |

← Rev. 2 →

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?

→ Reply

Cgfyufsygsm

2 years ago, # ^ |

Use 01-Trie to optimize the transition.

→ Reply

Nurss

2 years ago, # ^ |

← Rev. 2 →

What are transitions? and how we can optimize them?

→ Reply

Igor_Parfenov

2 years ago, # ^ |

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.

→ Reply

HugeWide

2 years ago, # ^ |

using 01-trie is a good choice

→ Reply

2 years ago, # |

+50

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.

→ Reply

madlogic

2 years ago, # |

← Rev. 3 →

+19

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}$$$.

→ Reply

ashutosh_jha_

2 years ago, # ^ |

→ Reply

spookywooky

2 years ago, # ^ |

← Rev. 3 →

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.

→ Reply

jzcrq

2 years ago, # |

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.

→ Reply

mousebeaver

2 years ago, # ^ |

+10

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

→ Reply

jzcrq

2 years ago, # ^ |

I see. Thank you.

→ Reply

z1bbo

2 years ago, # ^ |

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!

→ Reply

DanielChangTW

2 years ago, # |

+33

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

→ Reply

Misuki

2 years ago, # |

+24

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

→ Reply

mohamedeltair

2 years ago, # |

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.

→ Reply

hcmusNHUCAILONdungvaopls

2 years ago, # ^ |

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

→ Reply

2 years ago, # ^ |

+21

I used O(256n)

→ Reply

opPO_fan

2 years ago, # ^ |

← Rev. 2 →

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

→ Reply

HappyIvan

2 years ago, # ^ |

← Rev. 10 →

+12

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.

→ Reply

2 years ago, # ^ |

Same.

→ Reply

mohamedeltair

2 years ago, # ^ |

Thanks everyone. Your insights are appreciated.

→ Reply

tch1cherin

2 years ago, # |

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

→ Reply

2 years ago, # ^ |

← Rev. 2 →

+16

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:

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

→ Reply

2 years ago, # |

How to solve D1, D2?

→ Reply

Noureldin

2 years ago, # ^ |

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.

→ Reply

zhiqiu

2 years ago, # ^ |

D1 直接暴力

→ Reply

ycy0731

2 years ago, # |

+11

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

→ Reply

bitcoin

2 years ago, # ^ |

So what is the solution for the hard version?)

→ Reply

Cgfyufsygsm

2 years ago, # ^ |

use a 01Trie to optimize the transition

→ Reply

ycy0731

2 years ago, # ^ |

I mean d1, I can't solve d2 either

→ Reply

HugeWide

2 years ago, # ^ |

DP, using 01-trie to optimize it

→ Reply

Graygoo_401

2 years ago, # ^ |

Try to use a 01-trie to maintain pairs.

→ Reply

Torenu

2 years ago, # |

← Rev. 3 →

+185

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

→ Reply

DonSilvio

2 years ago, # |

A fuckload of TLs for C INCOMING!!!

→ Reply

DonSilvio

2 years ago, # ^ |

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

→ Reply

Cgfyufsygsm

2 years ago, # |

+17

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 :)

→ Reply

AVdovin

2 years ago, # |

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.

→ Reply

2 years ago, # |

← Rev. 2 →

+67

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. :(

→ Reply

2 years ago, # ^ |

← Rev. 2 →

+19

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.

→ Reply

2 years ago, # ^ |

→ Reply

2 years ago, # ^ |

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

→ Reply

2 years ago, # |

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

→ Reply

Ynoi

2 years ago, # |

Many fst in problem A...

→ Reply

NoCommander

2 years ago, # |

← Rev. 3 →

The pretest of A is so weak!

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

→ Reply

CoCo_Candy

2 years ago, # ^ |

That's true.

→ Reply

cayaxi_orz

2 years ago, # ^ |

Yes. I'm waiting for FST.

→ Reply

Torenu

2 years ago, # ^ |

Int solution (WA) 168831736 LL solution (AC) 168832004

seems ok

→ Reply

Bronya147

2 years ago, # ^ |

what?my first code without long long even can't pass the example:(

→ Reply

Mkswll

2 years ago, # |

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:)))))

→ Reply

Andalus

2 years ago, # |

← Rev. 3 →

+43

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!!!

→ Reply

mini4141

2 years ago, # ^ |

← Rev. 2 →

+10

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.

→ Reply

Andalus

2 years ago, # ^ |

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$$$.

→ Reply

mini4141

2 years ago, # ^ |

← Rev. 2 →

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

→ Reply

OptimalKnight

2 years ago, # |

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.

→ Reply

karanarjunjr

2 years ago, # ^ |

Exactly! How can a subsequence of an array be a collection of indices? TeaTime

→ Reply

goodred

2 years ago, # |

← Rev. 4 →

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?

→ Reply

Ant_Man

2 years ago, # ^ |

← Rev. 3 →

+61

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.

→ Reply

Screencast with commentary

2 years ago, # ^ |

← Rev. 2 →

+27

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.

→ Reply

ExpensiveAC

2 years ago, # |

looks like if you use division on A it will FST

→ Reply

Um_nik

2 years ago, # |

+38

→ Reply

Alice114514

2 years ago, # |

weak pretest for problem A.

→ Reply

magnirostris

2 years ago, # |

← Rev. 2 →

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

Get FST — Good job.

→ Reply

LinkinPony

2 years ago, # |

+22

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?

→ Reply

sahaun

2 years ago, # ^ |

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

→ Reply

2 years ago, # |

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

→ Reply

2 years ago, # ^ |

D was so confusing spent 1 hr just reading it.

→ Reply

YuxiangQi

2 years ago, # |

+12

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.(╥_╥)

→ Reply

MohamedAboOkail

2 years ago, # |

← Rev. 2 →

+10

Sad view don't open it

Spoiler

→ Reply

MrOtter

2 years ago, # |

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

→ Reply

MrOtter

2 years ago, # ^ |

Now it refers to current blog but still not to contest

→ Reply

leoncn

2 years ago, # |

168821144

Problem B, why this submission is TLE. Java

→ Reply

seraphimstreets

2 years ago, # ^ |

-10

For large inputs in Java, you'll need fast IO. https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/

→ Reply

2 years ago, # ^ |

Arrays.sort is $$$O(n^2)$$$ in certain cases.

→ Reply

notxkaran

2 years ago, # |

← Rev. 2 →

-16

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()

→ Reply

MohamedAboOkail

2 years ago, # ^ |

Put the code inside a Spoiler

→ Reply

sahaun

2 years ago, # ^ |

← Rev. 2 →

You should also check if there if two zeros are diagonally adjacent.

→ Reply

notxkaran

2 years ago, # ^ |

yess just find out my mistake thank you... tysm

→ Reply

Kartik.

2 years ago, # |

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

→ Reply

purupuddu

2 years ago, # |

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

→ Reply

HaccerKat

2 years ago, # |

← Rev. 2 →

+39

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

→ Reply

2 years ago, # ^ |

+31

At the same time, I think they know much better why their solution works than a large number of solvers.

→ Reply

2 years ago, # ^ |

jiangly's solution evidently didn't work

→ Reply

mesanu

2 years ago, # |

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

→ Reply

drdilyor

2 years ago, # ^ |

← Rev. 2 →

+14

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.

→ Reply

saransh_singh

2 years ago, # |

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

→ Reply

delete513

2 years ago, # |

ABC=500,500,500

→ Reply

Mostafa__Fouad

2 years ago, # |

-13

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 !!

→ Reply

2 years ago, # ^ |

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

→ Reply

Mostafa__Fouad

2 years ago, # ^ |

how could i know ?

→ Reply