Is it Div.3?

2 года назад, # ^ |

-12

As a contestant, contest is just a prefix of contestant

→ Ответить

null_awe

2 года назад, # |

+122

As a useless problemsetter, I hope you enjoy this round!

→ Ответить

The_crawler

2 года назад, # ^ |

+22

As a contestant, waiting for the score distribution...

→ Ответить

lunchbox

2 года назад, # |

+73

As an author, BucketPotato orz.

→ Ответить

wavelets

2 года назад, # |

+57

BucketPotato round orz

→ Ответить

2 года назад, # |

+83

BucketPotato orz.
As a tester, I can confirm that the problems are very interesting and would recommend everyone to participate in the contest.

Also

→ Ответить

TimDee

2 года назад, # ^ |

+19

So you want to say I won't loose cm first round after I reached it? :thinking:

→ Ответить

2 года назад, # ^ |

+16

Congratulations for CM!
Yeah, hopefully you will not lose CM just after you reached it.

→ Ответить

TimDee

2 года назад, # ^ |

+17

Thanks, then I'm like 2 times calmer to participate xdd

→ Ответить

lce4113

2 года назад, # |

+53

BucketPotato hard carry orz

→ Ответить

sus

2 года назад, # |

+59

As a tester this round is extraordinary

Take it or BucketPotato will come to your house and enact his revenge

→ Ответить

WalrusRamen21

2 года назад, # |

As a CFer, BucketPotato orz

→ Ответить

Jasonwei08

2 года назад, # |

Seeing sus as a tester makes me feel really excited about this round!!

→ Ответить

chenyanlin

2 года назад, # |

Through the last two competitions, I have reached “pupil”. I hope my rating can reach 1300 in this competition!

→ Ответить

shreyas_171

2 года назад, # |

Can anyone tell me how to become a tester for cf contest? What are the criteria for it ?

→ Ответить

Bungmint

2 года назад, # ^ |

How to become a CodeForces tester 101:
Step 1. Become friends with some setters
Step 2. Profit

→ Ответить

2 года назад, # ^ |

How to become friend with some setters?

→ Ответить

ScarletS

2 года назад, # ^ |

+42

Seduction works

→ Ответить

Bungmint

2 года назад, # ^ |

+21

Unspoken rizz

→ Ответить

2 года назад, # ^ |

← Rev. 2 →

+10

I don't know how to seduce :( probably just gonna make myself an e-girl

→ Ответить

2 года назад, # |

As a contestant I hope I can become Specialist

→ Ответить

NTTilted

2 года назад, # ^ |

as a contestant I hope I can become expert :D

→ Ответить

2 года назад, # ^ |

Nice we are far 31 exactly. Good luck today!

→ Ответить

NTTilted

2 года назад, # ^ |

good luck <3

→ Ответить

Perpetually_Purple

2 года назад, # |

+39

BucketPotato orz

→ Ответить

_Habibullo_

2 года назад, # |

I hope this Div2 gets easier!

→ Ответить

OccDreamer

2 года назад, # |

Good luck everyone. I hope this round is easier than the last round.

→ Ответить

sailikpandey

2 года назад, # |

+110

→ Ответить

Nxxlt

2 года назад, # ^ |

Ahahahahhahahahha. U made my day, get like XD

→ Ответить

jsyz

2 года назад, # ^ |

Ahahahahahahahha

→ Ответить

guluguluboy

2 года назад, # ^ |

hhhhhh

→ Ответить

sailikpandey

2 года назад, # |

-11

Best of luck everyone! Lets's give our best in this contest.

→ Ответить

hunter_of_alts

2 года назад, # ^ |

Ok but please stop cheating

→ Ответить

Codula

2 года назад, # |

+26

:pkinghi: BucketPotato Orz. Master of hugs.

→ Ответить

zezoo050

2 года назад, # |

You will be given 2 hours to solve 5 problems, one of which will be divided into 2 subtasks Can someone explain what divided into 2 subtasks means.

→ Ответить

Batman_love_dp

2 года назад, # ^ |

I think we could have same two problems with different constraints as b1 b2 for example

→ Ответить

vitosevskich

2 года назад, # ^ |

It doesn't always mean different constraints. That means we will have 6 problems, but two of them will be very similar.

→ Ответить

_Aryan_

2 года назад, # |

as a participant I am participating

→ Ответить

100POINTS

2 года назад, # |

I hope all participants will write this round good! I also wish good luck everyone!

→ Ответить

karanarjunjr

2 года назад, # |

-14

I hope this is a Codeforces round and not a Mathforces one.

→ Ответить

XG0000

2 года назад, # |

As a Rating-rapid-decline-er, I hope I can enjoy this round.

→ Ответить

SpadeA261

2 года назад, # ^ |

As a Master, I hope today is not still a Candy Date.

→ Ответить

XG0000

2 года назад, # ^ |

Candydate Master orz

→ Ответить

thangdz2k7

2 года назад, # |

Hope there will be more contests in the near future <3

→ Ответить

badluck_1441

2 года назад, # |

I think codeforces have best userInterface amongs all comptetive coding platform.

→ Ответить

2 года назад, # |

+17

Scoring distribution when

→ Ответить

ronnyait

2 года назад, # |

It's time for Pupil :)

→ Ответить

2 года назад, # ^ |

Good luck

→ Ответить

mnkp

2 года назад, # |

How do I become a tester?

→ Ответить

shriganesh83

2 года назад, # |

for proposing problems that didn't make it to the final version of the round. XD XD.

→ Ответить

rishisgsits_22

2 года назад, # |

hoping not to become pupil again

→ Ответить

DestroyCopyright

2 года назад, # |

Looking forward to this round! After this round, I should become green.

→ Ответить

vitosevskich

2 года назад, # |

I like B.

→ Ответить

adityagamer

2 года назад, # |

What's the backstory of naming D1 as Chopping Carrots?

→ Ответить

2 года назад, # ^ |

+65

Originally, the statement looked something like this (this is a very condensed version of it):

You are preparing carrots to cook. The carrot can be modeled as a non-decreasing array, and your chopping skills are represented by an integer k. The roughness of an array p is max(a / p) — min(a / p), find the minimum roughness of the carrot you can achieve.

The flavor text was ultimately taken out since testers found it made the statement more confusing.

→ Ответить

grayhathacker

2 года назад, # |

← Rev. 3 →

B is way harder than C to me.

→ Ответить

lkjhgfertyul

2 года назад, # ^ |

B is greedy

→ Ответить

spookywooky

2 года назад, # ^ |

How? I see only dp solution.

→ Ответить

introart

2 года назад, # ^ |

How can you please explain your approach?

→ Ответить

lkjhgfertyul

2 года назад, # ^ |

← Rev. 2 →

difference between index of 2 same colors should be odd so that we can put them in same tower

→ Ответить

Fuehrer

2 года назад, # ^ |

← Rev. 2 →

We need to have odd distances between indexes of each frequency to build

→ Ответить

spookywooky

2 года назад, # ^ |

Yes, wiered named friend, but how is this greedy?

The dp is more or less simple:

    vvi dp(2, vi(n+2));
    vi ans(n);
    for(int i=n-1; i>=0; i--) {
        dp[i%2][c[i]]=dp[1-i%2][c[i]]+1;
        ans[c[i]]=max(ans[c[i]], dp[i%2][c[i]]);
    }

→ Ответить

lkjhgfertyul

2 года назад, # ^ |

It's dp because you solved it using dp and its greedy because I solved it using greedy.

→ Ответить

Rikitexh

2 года назад, # |

How to solve D1?(Just some hint)

→ Ответить

Olympia

2 года назад, # ^ |

Fix the maximum (or minimum) element.

→ Ответить

impressionnante

2 года назад, # ^ |

https://codeforces.me/contest/1706/submission/164793681 I did that! But WA on pretest 3 :(((

→ Ответить

Olympia

2 года назад, # ^ |

The minimum element is not necessarily of the form $$$\frac{a[0]}{j}$$$...

→ Ответить

variety-jones

2 года назад, # ^ |

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

→ Ответить

Aravind

2 года назад, # ^ |

I got TLE by doing that but may be inefficiently. I stored all possible values for a number in a 2-D array and iterated 1 to 3000 fixing it as maximum and got maximum possible number of each element less than fixed maximum using binary search!

How did you do that?

→ Ответить

Olympia

2 года назад, # |

Is the main idea for $$$E$$$ to maintain a DSU and for each 'root' node mantain the set of intervals covered and then merge them appropriately?

→ Ответить

Geothermal

2 года назад, # ^ |

+57

This wasn't my approach. I used DSU with small-to-large merging to find the earliest time at which vertex v is connected to vertex v+1, for all v. Then, queries can be answered by storing these times on a segtree and storing the maximum values within the range [L, R-1].

→ Ответить

2 года назад, # ^ |

This is exactly what I did, only difference is I used when v is connected to v-1.

→ Ответить

the_hyp0cr1t3

2 года назад, # ^ |

That was what I thought of during contest (164782058), but realized only after that a much simpler solution exists.

→ Ответить

impressionnante

2 года назад, # |

Hi, I have a hard time debugging my code. For example, today's Div2D1, I felt I had made it but then I had WA on pretest 3 and I couldn't debug fast. Here is my submission. https://codeforces.me/contest/1706/submission/164793681 Any tips on fast debugging? Thanks!

→ Ответить

variety-jones

2 года назад, # ^ |

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

→ Ответить

Stoiic

2 года назад, # |

In problem C when n=6 there will be 3 possibilities right (2,4) or (2,5) or (3,5)?

→ Ответить

21NOYA13

2 года назад, # ^ |

if n = odd, it becomes trivial. If n = even: For every tower we want to make cool we can pick it up from 2 array:

1) 2,4,6,8,... 2) 3,5,7,9,...

Suppose you pick i from 1) then you need rest (n/2-1-i) from 2). Just iterate over i and take the min.

→ Ответить

songtianyi

2 года назад, # ^ |

← Rev. 2 →

I saw many guys use dp to solve problem C, i don't know why. The problem description says "maximize the number of cool buildings."

I think we have 1 option for n % 2 == 1, and 2 options for n % 2 == 0.

n == 6 is a special case and has 3 options.

So what I missed?

→ Ответить

O_Vladimir

2 года назад, # ^ |

You can "skip" a building in case of n % 2 == 0
Consider the case of
10 9 7 7 7 7 9 10

"odd" and "even" options use 2 + 1 + 3 = 6 floors

10 (9->11) 7 (7->8) 7 (7->10) 9 10
10 9 (7->10) 7 (7->8) 7 (9->11) 10

while optimal solution

10 (9->11) 7 (7->8) 7 7 (9->11) 10

uses only 2 + 1 + 2 = 5 floors.

→ Ответить

drdilyor

2 года назад, # ^ |

← Rev. 3 →

If n is even: For some building x, choose all odd indexed in the left to x, and all even indexed buildings to the right of x. So there is a gap of two non-cool buildings near x.

→ Ответить

songtianyi

2 года назад, # ^ |

← Rev. 2 →

10 9 7 7 7 7 9 10

0 1 0 1 0 1 0 0

0 0 1 0 1 0 1 0

there are only two options, right? I need an example which has more than 2 options except n == 6, cause (6 — 2)/2 = 6-4

→ Ответить

O_Vladimir

2 года назад, # ^ |

← Rev. 2 →

3 options:

01010100 (6 floors)
00101010 (6 floors)
01010010 (5 floors)

→ Ответить

physics0523

2 года назад, # |

+35

Easier Div2?

I like B, it's good D2B
I saw some tasks similar to C somewhere
Why so tight ML for D2? I have a painful work making the memory of my solution < 64MB

→ Ответить

brunovsky

2 года назад, # ^ |

+10

Linear memory is intended I think. My submission with $$$3n$$$ integers on a BST (instead of heap) only used 6MB, so if anything I think it could have been 32MB

→ Ответить

Geothermal

2 года назад, # ^ |

← Rev. 2 →

Agreed re: D2. The process of solving D2 was very unpleasant for me--I came up with/recognized the main observation in <2m, then took the vast majority of my time dealing with the memory optimization. In particular, because $$$\sum a_n$$$ was unbounded, my approach to optimizing the memory was dependent on the fact that the number of tests was small, as it leads to a time complexity of $$$O(n \sqrt{n}) + a_n)$$$ per test case. The problem is solvable in linear memory, but the process of optimizing to linear memory is not at all interesting, and the linear memory solution doesn't feel any more clever than the $$$n \sqrt{n}$$$ memory solution.

→ Ответить

2 года назад, # ^ |

← Rev. 3 →

+49

Sorry for the trouble, there is a $$$n \sqrt n$$$ two-pointers memory solution in D2 that we wanted to cut off. We decided it would be fine since all of the correct $$$O(n)$$$ memory solutions (from testers, authors, and the coordinator, including in Python and Java) use less than 1/6 of that memory without any optimizations.

As for the difficulty, there was originally a problem F, but testing suggested that up to E was hard enough.

→ Ответить

oToToT

2 года назад, # ^ |

← Rev. 2 →

+14

My O(n) memory solution requires me to change std::vector to std::list, or free the memory of std::vector correctly (.clear() doesn't free the memory).

It's a bit annoying. :(

→ Ответить

2 года назад, # ^ |

I also MLEed once due to clear().

→ Ответить

2 года назад, # ^ |

+18

Sorry to hear :(

Our correct intended solutions take some more thinking, but have clean and easy implementations (no optimizations needed).

So I guess the difficulty of this task was in, do you want to optimize your code or think of a cleaner solution?

→ Ответить

oToToT

2 года назад, # ^ |

← Rev. 4 →

I believe the core idea of mine (the one changed to std::list 164802621) and the posted solution doesn't differ a lot. (to me, it's just some computation order)
Are there any more clever solutions?

I know knowing the programming language I used is also a part of CP, but just don't like it to be kinda the only point of a problem.

btw, what do u mean by optimizing my solution?

Anyway, other problems are not bad.
Thanks for the contest!

→ Ответить

2 года назад, # ^ |

+13

The main idea is the same, but the way you go about it is different:

Your solution uses a vector<list<int>> to help determine cmx (using variable names from your code), and has to update the lists as you sweep through.

The intended solution also finds all values of cmx, but uses the additional idea of prefix maxes on increasing functions to simplify the memory usage to a single int pf[100000 + 1].

→ Ответить

oversolver

2 года назад, # ^ |

I had MLE with vectors too, but during contest I forgot about std::list and wrote custom (164757358)

Changing vector to list in upsolving gives AC but sadly it is ~9x times slower than custom (164886835)

→ Ответить

prabowo

2 года назад, # ^ |

+37

I was using a linear memory solution, but it was using vector<vector<int>> and the memory still blew up and used > 64 MB.

Then I learned that .clear() does not necessarily reallocate to make the capacity back to 0. To "force clear" a vector, one can use vector<int>().swap(x)

→ Ответить

Flyed

2 года назад, # ^ |

I also agree about seeing C somewhere. I did try spending a little bit of time looking for it, but ended up not finding anything. I don't know how similar the problem I remember was, but it involved this idea of a[i] > a[i — 1] and a[i] > a[i + 1]

→ Ответить

robostac

2 года назад, # ^ |

https://codeforces.me/contest/1698/problem/B from round 803 is based on the same basic idea but asks a different question about it.

→ Ответить

M_bolshakov

2 года назад, # |

← Rev. 2 →

wow, memory limits in D1 are divine. I submitted with O(n*3000) time, using 2d arrays, but it got ml. I changed algorithm for 2d arrays to 1d, and it passed. 5 incorrect attemps, rest in peace. But i had to gain only 4 points to reach CM

164778279

→ Ответить

rep

2 года назад, # |

-28

Is it Div.3?

→ Ответить

vitosevskich

2 года назад, # ^ |

+14

No.

→ Ответить

hunter_of_alts

2 года назад, # ^ |

← Rev. 2 →

Did you know participating with alt account is forbidden in codeforces?!

→ Ответить

oToToT

2 года назад, # |

← Rev. 2 →

I think my solution to D2 only uses O(N) memory, but still can't pass TC11.

upd: std::vector is so hard (.shrink_to_fit() is stupid)

→ Ответить

chenyanlin

2 года назад, # |

In the end, I solved three problems, which made me very happy. But how to solve D1?

→ Ответить

Cereal2

2 года назад, # ^ |

I think you fix either the max or minimum value and use brute force, but I didn't solve it, so I'm not too sure.

→ Ответить

tch1cherin

2 года назад, # ^ |

Yes, but instead of brute force use two pointers.

→ Ответить

epsilon_573

2 года назад, # |

Video Solution for Problem C.

→ Ответить

mercyme

2 года назад, # ^ |

I did pretty much the same thing.

Here is my submission:164775959

Can anyone give me a fail-case.

→ Ответить

quickman

2 года назад, # ^ |

long long ans

→ Ответить

2 года назад, # ^ |

Testcase

Your output

Correct Output

→ Ответить

GrandSouris

2 года назад, # |

← Rev. 2 →

-10

I think the input constraints in problem D2 are really confusing. Why those $$$O(n\sqrt n\log n)$$$ solutions can get pretests passed but a $$$O(A\log n\log A)$$$ solution (my idea) can't get PP (only $$$\sum n$$$ is $$$10^5$$$ but $$$\sum A$$$ isn't) so I wasted a lot of time on this problem and I didn't solve problem E (or even carefully read the statement) which I found a solution just 5 minutes after the contest.

Anyway, good contest & problems, hope the next round will be better.

→ Ответить

hgzxwzf

2 года назад, # ^ |

If $$$n=100000$$$,$$$\sqrt{n}\approx320$$$,$$$nlog^2n \approx 256$$$,but the constant of segment tree is so big that it is greater than $$$320$$$ after multipliying $$$256$$$.

→ Ответить

yqxt_

2 года назад, # |

I used DSU to get when each point is first added to the connected graph, and then use segment tree to query the maximum values within the range [L+1, R].Why I couldn't get a accepted?my submisson

→ Ответить

2 года назад, # ^ |

that's not correct. Added to connected graph does not mean connected to previous node.

→ Ответить

yqxt_

2 года назад, # ^ |

Thanks!

→ Ответить

__stick

2 года назад, # |

I used Overall dichotomous( $$$O(n \log^2 n)$$$ ) ，but TLE on 4. Am I wrong ? mysubmission

→ Ответить

rep

2 года назад, # |

-31

I think the most difficult problem in this contest is at most *2200 :(

so it like div.3.

→ Ответить

kozliklekarsky

2 года назад, # ^ |

+60

we heard you the first time now shut up jesus christ

→ Ответить

Aravind

2 года назад, # ^ |

Maybe most difficult one idk about that, but A, B and C's are not far from expected div2 difficulty

→ Ответить

Kartik.

2 года назад, # |

D seems to be an easy one but when I started I found it a bit complicated :)..

→ Ответить

leoncn

2 года назад, # |

Why problem B Complexity: O(n) can not pass?164782973

→ Ответить

O_Vladimir

2 года назад, # ^ |

← Rev. 2 →

I had same issue (but with Golang, not Java). I had to change standard output (fmt.Println) to bufio Writer. [Solution_1 TLE, Solution_2 AC]. It might have something to do with bufferization.

→ Ответить

leoncn

2 года назад, # ^ |

yes, this is ok 164798975

→ Ответить

Arisu_Sakayanagi

2 года назад, # |

-52

Well, problem E is better to be put in an edu round. And D2 is a totally trash problem I think.

→ Ответить

2 года назад, # ^ |

+35

Sorry to hear. What did you dislike about D?

→ Ответить

Arisu_Sakayanagi

2 года назад, # ^ |

-15

Too difficult to implementation.

→ Ответить

2 года назад, # ^ |

just about 10 lines except for careful memory management. Where is difficult?

→ Ответить

2 года назад, # ^ |

← Rev. 3 →

+26

Hi, the intended solution codes for D2 have now been posted (here and here). IMO, the implementation in both is very clean and easy, no optimizations needed.

As I said in a different comment, the difficulty in this problem seems to lie on whether you want to painfully optimize a simple idea or think a little more to find a nicer solution.

→ Ответить

plag-reporter

2 года назад, # ^ |

It says "you are not allowed to view the requested page" when I click on 2nd link(/here).

→ Ответить

2 года назад, # ^ |

Sorry, the link has been fixed

→ Ответить

plag-reporter

2 года назад, # ^ |

+19

Thanks for the contest!Awesome problems especially B,D2 and E!

→ Ответить

https://codeforces.me/contest/1706/submission/164815320

2 года назад, # |

+48

First time to AK a div 2 contest!

→ Ответить

Blinding_Lights

2 года назад, # |

← Rev. 5 →

Is the below statement true?
for integers a and p, where 1<= p <= sqrt(a) . floor(a/p) is unique.
Proof if any?

→ Ответить

Blinding_Lights

2 года назад, # |

How to get unique elements of a/p for an integer a and p <= k, efficiently for problem D2?

→ Ответить

oversolver

2 года назад, # ^ |

Iterate over segments:

start with [1, 1]

then next for [l, r] will be [r+1, a / ( a / l )]

in each segment a // i is constant (l <= i <= r).

→ Ответить

Blinding_Lights

2 года назад, # ^ |

Thank you very much. And are the number of unique a/ps around sqrt(a)?, if we consider k as infinity.
I wanted to calculate time complexity.

→ Ответить

oversolver

2 года назад, # ^ |

← Rev. 2 →

There will be no more than 2 * sqrt(a) such segments

First part where r <= sqrt have l = r

In second part a / p = sqrt ... 1

→ Ответить

geranazavr555

2 года назад, # |

+30

Ratings updated preliminary. As I said here: https://codeforces.me/blog/entry/104766?#comment-932270 cheaters will be removed later.

→ Ответить

3mara

2 года назад, # |

thx for specialist-1... im totally fine after today's contest

→ Ответить

csyakuoi

2 года назад, # |

div2.5

→ Ответить

lss_cat

2 года назад, # |

I'm sorry I missed the fight

→ Ответить

nowadays-

2 года назад, # |

How to become stronger quickly

→ Ответить

Harshil4442

2 года назад, # |

-13

Problems were somewhat hard in this contest.

→ Ответить

aayushdhankecha

2 года назад, # ^ |

Life is not easy as you are thinking.

→ Ответить

fwtt2

2 года назад, # |

Could anyone have a look at this code?

The solution got TLE before I added an early exit trick, then it got AC, I have no idea why. It seems that the early exit trick is wrong. So is the data too weak or the early exit is actually correct?

→ Ответить

valeriu

2 года назад, # ^ |

why are you glorifying this shenanigan by calling it a "trick"

→ Ответить

fwtt2

2 года назад, # ^ |

Is the word trick kinda glorifying? I don't think so.

And, if actually it can be proved at most a certain amount of updates lead to the minimized answer, then it's not a shenanigan. This is also why I am asking here. I'm not able to construct a case failing the solution.

Besides, early exit is sometimes useful in OI competitions.

→ Ответить

amos_aidoo

2 года назад, # |

For problem B:

I used std::vector and got TLE — https://codeforces.me/contest/1706/submission/164907546
I changed to normal arrays for the same solution and got AC — https://codeforces.me/contest/1706/submission/164916818

I understand vectors are slower than arrays but can someone help me understand why I got TLE. Thanks.

→ Ответить