Codeforces Round #429

5 years ago, # |

+32

Short announcement, short problem statements. Hopefully.

→ Reply

akulgoel96

5 years ago, # ^ |

Boy you were so wrong.

→ Reply

5 years ago, # ^ |

Unfortunately yes. Though long statements wouldn't be a big problem themselves...

→ Reply

vntshh

5 years ago, # |

+49

There is a codesprint on Hackerrank one hour in the midway of this contest.

→ Reply

teja349

5 years ago, # ^ |

+48

→ Reply

5 years ago, # ^ |

+236

→ Reply

bktl1love

5 years ago, # ^ |

← Rev. 2 →

-32

Is he from Game of thrones?

→ Reply

5 years ago, # ^ |

+37

It's from LotR. See here.

→ Reply

JiK

5 years ago, # ^ |

+38

One doesn't simply walk into Mordor from Westeros.

→ Reply

chb19

5 years ago, # ^ |

+53

→ Reply

MazzForces

5 years ago, # ^ |

+65

Assuming that any contest clashes with a CF contest, It can only be bad for the clashing website and not for CF.

If HackerRank care enough about their own, they should change timings, not CF.

→ Reply

5 years ago, # ^ |

+11

I kinda disagree as there is prize money for the top 7, so those top rated participants might go for that instead.

→ Reply

drexdelta1

5 years ago, # ^ |

just look at the leaderboard on hackerrank. and then say a word bro...

Gennady finished the entire contest in 29 minutes. It took me more than half hour to understand all the problems properly.

→ Reply

5 years ago, # ^ |

It's a two day contest, that's probably why this round didn't yield way.

→ Reply

5 years ago, # ^ |

+18

but the first hour is the important timing for those who wants to win top places(not me of course)

→ Reply

Baklazan

5 years ago, # ^ |

← Rev. 3 →

+21

Never mind.

→ Reply

enoone

5 years ago, # |

-6

Who will be the main character of the round?

→ Reply

Wael.Al.Jamal

5 years ago, # |

-19

New round, means new chance for better performance and improving our rate.

→ Reply

DonMichaelCorleone

5 years ago, # ^ |

Chance of learning new things

→ Reply

5 years ago, # |

+118

I think the winner is obvious.

→ Reply

5 years ago, # ^ |

-37

Not after Rudy404 registred.

→ Reply

5 years ago, # ^ |

they are not even the same division

→ Reply

5 years ago, # ^ |

-46

He just doesn't want to scary tourist, that's why he participate in div 2.

→ Reply

I_LOVE_METSUKA

5 years ago, # ^ |

← Rev. 2 →

+74

Why so salty man? Still mad that you sucked at IMO?

UPD: WTF I was not expecting upvotes.

→ Reply

5 years ago, # ^ |

-33

Why is it salty? Did i offend aomeone?

→ Reply

I_LOVE_METSUKA

5 years ago, # ^ |

-13

Anyone who knows sarcasm will understand it. Can't understand if you really hate him, because he did better than you at IMO or you're joking too hard.

→ Reply

Rudy404

5 years ago, # ^ |

nibabin registered too so I got no chance :'( Although I heard there are problems that even he can't solve

→ Reply

Sahashoo

5 years ago, # |

← Rev. 2 →

-6

tank you all for contest. and hope for statement be as short as blog.

→ Reply

SmartCoder

5 years ago, # ^ |

-33

R.I.P English

→ Reply

Sahashoo

5 years ago, # ^ |

Sorry for bad english :)

→ Reply

windazz

5 years ago, # |

+11

Where is KAN?

→ Reply

SleepyShashwat

5 years ago, # |

Hi , I just wanted to ask that whats the difference in div 1 and 2 like can we say that Div 2 E,F > Div 1 A,B,C,D in terms of difficulty?

→ Reply

smartandlean

5 years ago, # ^ |

+20

Usually, Div 2 C/D/E.. is the same as Div 1 A/B/C.. and so on. The difficulty is in the increasing order.

→ Reply

codeedoc

5 years ago, # |

this is the shortest announcement I have ever seen !!

→ Reply

5 years ago, # |

Are 2 hours good for 6 problems ?

→ Reply

nima10khodaveisi

5 years ago, # ^ |

-6

do you want to full ?

→ Reply

5 years ago, # ^ |

+12

What do you think bro, my color still f*ckin gray :3

→ Reply

Sharon

5 years ago, # ^ |

We don't judge people by their color here <3

→ Reply

5 years ago, # ^ |

+13

Sharon are you sure ? :"D link1 link2

→ Reply

Sharon

5 years ago, # ^ |

+25

All colors are equal, but some are a bit more equal.

→ Reply

Online Economics Assignment Help from Professionals

5 years ago, # ^ |

Good, I'll try make website and make the rate by hair color so you know overages coders will be gray newbies

→ Reply

Nurlykhan

5 years ago, # ^ |

Animal farm..

→ Reply

Baklazan

5 years ago, # |

+68

I wonder what is the story behind your rating graph, totsamyzed. Are you going to be our next dreamoon_love_AA?

→ Reply

quotitquot

5 years ago, # ^ |

+11

I think this guy is also hero

→ Reply

Michael_1

5 years ago, # |

-116

Thanks a lot for sharing it, that’s truly has added a lot to our knowledge about this topic. Have a more successful day.

→ Reply

MrCode

5 years ago, # |

← Rev. 3 →

-32

I hope we will have an interesting contest tonight:) GL

→ Reply

AwesomeGuy

5 years ago, # |

+18

OMG :O GoodGuy Registered for this contest :O

→ Reply

RapperGuy

5 years ago, # ^ |

+19

Who is he? :/

→ Reply

AwesomeGuy

5 years ago, # ^ |

← Rev. 2 →

+24

he is sad ,he is hurt ,he is dying ,he is lonely ,he is a mess ,he is judged ,he is ignored ,he is suicidal ,he is depressed ,he is misunderstood ,he is tired he is SmSS

→ Reply

Mizofix

5 years ago, # |

-12

Kool(Sorry for my bad english)

→ Reply

5 years ago, # ^ |

+15

→ Reply

Mizofix

5 years ago, # ^ |

London is the capital city of Great Britain

→ Reply

5 years ago, # ^ |

→ Reply

zadrga

5 years ago, # |

Why was number of problems changed?

→ Reply

nima10khodaveisi

5 years ago, # ^ |

because time was not good for N4553R !

he want to full :D

Link

→ Reply

5 years ago, # ^ |

+10

→ Reply

5 years ago, # ^ |

Probably they found an issue with one of the problems.

→ Reply

MrCode

5 years ago, # ^ |

why not ?:)

→ Reply

e-shubh

5 years ago, # |

+18

→ Reply

MrCode

5 years ago, # ^ |

+103

someone hack your code is so better than judge do it :D

→ Reply

egor.okhterov

5 years ago, # ^ |

+32

He'll find and kill the judge.

→ Reply

VladaMG98

5 years ago, # |

Not the right place for this post, but could some of the contest organizers or idk inform CF staff that email system isn't working. Thanks

→ Reply

Alexxx

5 years ago, # |

+91

Did Um_nik save rated contest? :D

→ Reply

5 years ago, # ^ |

+27

Not all heroes wear capes.

→ Reply

nibabin

5 years ago, # ^ |

← Rev. 2 →

+47

I hope this time the tests were weak instead of author's mind.

→ Reply

cronenberg

5 years ago, # ^ |

I don't think a lot of people get that reference.

→ Reply

nileshjha19

5 years ago, # ^ |

Check this

→ Reply

square1001

5 years ago, # |

+34

totsamyzed, don't make us sleep during the contest.

→ Reply

kuldeepfouzdar

5 years ago, # ^ |

+10

and during system tests as well. :)

→ Reply

kr_abhinav

5 years ago, # ^ |

+10

Wish not granted :D

→ Reply

olegts

5 years ago, # |

+18

Please open additional registration! Why is it even closed? I have not expected it would be impossible to register after the competition started

→ Reply

KKpoker

5 years ago, # |

← Rev. 4 →

+64

so many spelling mistakes.

having trouble guessing the meaning of div2D

and even no explanation of the Sample

→ Reply

brurrito

5 years ago, # ^ |

+10

took me a good 10 minutes to get it too, but what do you want, it's all part of the challenge !

→ Reply

I_love_Captain_America

5 years ago, # ^ |

I asked for clarification of sample cases. Reply was "read the statement". No i'm asking for clarification without reading the statement -_-

→ Reply

Zacle07

5 years ago, # ^ |

KKpoker me too the statement was not clear for problem D

→ Reply

5 years ago, # |

+64

RIP English

→ Reply

vilim_l

5 years ago, # |

+98

I'm sorry, but these problem statements are all cancerous. When you see a red squiggly line below your text, that means you have a problem. Don't submit text with a red squiggly line under it.

→ Reply

Rudy404

5 years ago, # |

+35

What the heck is F(n,k)???? So much broken english...

→ Reply

I'm going from one extreme to another :/

5 years ago, # ^ |

← Rev. 2 →

+60

I don't get it, why do you need F(n, k) if you can guess the solution by sample cases -_-.

→ Reply

chenmark

5 years ago, # |

+79

English is my first language and I can't understand Div1 B. It's riddled with typos and the grammar doesn't make sense.

→ Reply

chenmark

5 years ago, # ^ |

Can someone clarify: "Subset is calling «good», If we save in a graph only edges from subset , and for every vertex i will correct, taht di = - 1 or it's degree modulo 2 is equal to di."

→ Reply

HBK_Wasi

5 years ago, # ^ |

The English in the statement is very much "LOL".

→ Reply

brurrito

5 years ago, # ^ |

G=(V,E) is a graph, with V its vertices and E its edges. A subset S of E is called "good" if in the new graph G'=(V,S) we have the following property: for any vertex i in V of G', we either have d_i = -1, or deg(i)%2 = d_i ("deg" meaning degree, the amount of edges in S that are incident to vertex i).

(hope it helps, though it's a bit too late now i guess)

→ Reply

flash_7

5 years ago, # |

+45

With due respect to the setters, seriously, what is that? I haven't yet understood the statement of problem A and B -_- RIP English.

→ Reply

poomas

5 years ago, # |

+319

Does anyone even proofread the problems?

→ Reply

cyand1317

5 years ago, # ^ |

+44

Neu languache unlokt für CF: German

→ Reply

SameerGulati

5 years ago, # |

+19

Was excited for a rated round :/ 6 more days i guess.

→ Reply

ko_osaga

5 years ago, # |

← Rev. 2 →

+64

After reading ABD, I had no option other than withdrawing participation.

→ Reply

Neil

5 years ago, # |

+35

Worst problem statements I've seen on codeforces in a long time. Very disappointing. The proofreaders are all on vacation or something?

→ Reply

sdpsarker88

5 years ago, # |

Div2 D is a total disaster. Can't understand anything! RIP English!

→ Reply

joaquimnt_

5 years ago, # ^ |

Same here! This question was a disaster =(

→ Reply

Mohaimin66

5 years ago, # |

Horrible problem description! :/

→ Reply

5 years ago, # |

+30

Delinur, where u at when we need you?

→ Reply

bringBackTheGlory

5 years ago, # |

+23

You should really make this unrated. This is not English.

→ Reply

Dalisyron

5 years ago, # |

Horrible statements, and they're also not answering my questions. Not to mention zero shts were given with regards to the statements' coherence and story.

→ Reply

5 years ago, # |

+14

As if we could "save in a graph only edges" from a subset... Really, how old are the proofreaders? Freaking 5?

→ Reply

5 years ago, # ^ |

← Rev. 4 →

+23

Okay, this is getting ridiculous. This is what I get when I translate from English to Russian to English.

Lech plays a computer game where at each level a connected graph with n vertices and m edges is given. Graph can contain multiple edges, but can not contain loops. Each vertex has an integer di, which can be 0, 1, or -1. To pass a level, it needs to find a "good" subset of the edges of the graph or say that it does not exist. A subset is called "good". If we save only edges from the subset on the graph and correct for each vertex i, that di = -1 or the degree modulo 2 is equal to di. Lech wants to pass the game as soon as possible and ask you to help him.

At least that's understandable.

→ Reply

joaquimnt_

5 years ago, # ^ |

← Rev. 3 →

And yet the last Announcement says "Loop is an edge like (u, u). Loops are not allowed. Cycles are allowed."

→ Reply

5 years ago, # ^ |

+14

Loop is an edge similar to (u, u). Cycles are not allowed. Cycles are allowed.

Not like this. Not like this...

→ Reply

-is-this-fft-

5 years ago, # ^ |

What is the problem with that?

→ Reply

sdnr1

5 years ago, # |

+15

Never seen so many announcements in a single contest :/

→ Reply

nima10khodaveisi

5 years ago, # ^ |

+27

when an announcements published I thought my solution hacked :\

→ Reply

Melnyk

5 years ago, # |

Thanks for closed registration

→ Reply

5 years ago, # |

+35

Man dis, shit is aw full following time I am save Russia probs text in, google translate and read 'from they're.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Man, shit, complete, after I save Russia, ask for the text, translate and translate the text "from them."

Well I think the best method of reading grammatically incorrect sentences is to translate to Russian and then back, I guess.

→ Reply

5 years ago, # |

← Rev. 2 →

+50

When your problems' themes are so thin like that (really, Leha somehow found arrays and queries in pockets?), you'd better off not using any theme at all. Just state the problem without involving Leha in any way. For example, Div1D (what I mentioned above) should just be stated as "You are given an array of n numbers and q queries l r k...", so you don't need to stare awkwardly at why Leha's pockets are of any relevance.

→ Reply

WolfBlue

5 years ago, # ^ |

+38

Say what you will, I still think that

"Mom brought him two arrays A and B"

Is the funniest thing I've read in a long time

→ Reply

tsttkgnus

5 years ago, # |

+20

Hands down one of the worse contests. Close to 2000 people passed pretest in C but less than 50 is able to solve D. The difficulty is so low in A,B,C that difference in ranking is explained by whoever understands the statement first.

→ Reply

joaquimnt_

5 years ago, # ^ |

← Rev. 2 →

The ones who did 841D - Leha and another game about graph are the ones whose speaks Russian. That's the explanation

→ Reply

5 years ago, # ^ |

← Rev. 3 →

+19

Codeforces has just pulled off a codechef.

→ Reply

ShowStopper728

5 years ago, # |

← Rev. 2 →

+14

the predictor isn't working for me .

does anyone have the same problem ?

→ Reply

T1duS

5 years ago, # ^ |

yeah

→ Reply

priyanshupkm

5 years ago, # |

+17

I jumped directly to the Problem D, its been an hour and still I am not able to understand the question at all. So many mistakes in the spelling and explanation, I am leaving this round :(

→ Reply

hephaestus

5 years ago, # |

can someone give me brief idea of sample test 2 of Problem D , how is the answer 0 ??

→ Reply

zjuwyz

5 years ago, # ^ |

← Rev. 6 →

+15

It means: Find a sub graph of the given graph, such that for every vertices i, if d[i] != -1, then the degree of vertices i in the sub graph module 2 should be d[i].
And you're asked to output the number of edges in the sub graph k in the first line, then k lines follow, indicating which edge you'd decided to remain in the sub graph. Edges are labeled in the input order.

So, for test 2, a simple answer is to leave nothing in the sub graph, so 0 is acceptable. Another proper answer can be
4
1
2
3
4

BTW, this is the worst description I'd ever seen. I believe even google translate can do a better job :(

→ Reply

hmrockstar

5 years ago, # ^ |

Isn't 0 good for every graph then?

→ Reply

MrMorning

5 years ago, # ^ |

So why 0 isn't good for sample 1?

→ Reply

always_4ever_5_25__21_SS

5 years ago, # |

Problem C and D (div2) are awful. They didnt even provide good sample test explanations as well. And I dont know who are the heads of CF?? I mean, come on, after all this time you should at least look at the problems before deciding it is "contest-worthy".

→ Reply

saisurya027

5 years ago, # |

My code gave TLE in C++11 and got PRETESTS ACCEPTED in C++14 :( Is it my fault or Is their any way so that my penalities are taken back.

Please someone suggest me on this.

→ Reply

jamienguyen

5 years ago, # ^ |

yeah I lost 150pts for penalty and 160pts more for wasting time until I see this comment :<

→ Reply

5 years ago, # ^ |

time run of 2 version is different. If you use "cin/cout" in problem B without something else, I think it must be TLE...

→ Reply

saisurya027

5 years ago, # ^ |

I used Fast I/O but the result hasn't changed

→ Reply

5 years ago, # ^ |

For me it is the same. C++14 is working well for the task Div2-B. I suppose it can be a compiler issue. If it is true, maybe it is better to remove some compilers from the testing system.

→ Reply

5 years ago, # |

← Rev. 2 →

What a shit contest. Div 2 D is hardly being understood and C is being solved by even those who might have never solved any other C in their lifetime.

→ Reply

we7d

5 years ago, # ^ |

true, still made it harder for myself didn't read a[i] >= b[j] , hope i don't get a tle .

→ Reply

5 years ago, # ^ |

← Rev. 2 →

-7

I also got myself fucked in A because of a fucking reading mistake. And the sad part is that I locked the problem as soon as I submitted. :(

Moral of the story ; Dont lock the problem unless you don`t see one or two hacks in the room.

→ Reply

Enigma27

5 years ago, # ^ |

you haven't solved any C in any contest so far, so you dont have any right to comment like this

→ Reply

5 years ago, # ^ |

← Rev. 3 →

-8

I have solved C twice before too.

The only thing is that, I got WA in systest in either A or B in those contests.

Do your research properly from the next time.

Just because someone has solved 2 problems in the past doesn`t mean that it needs to be A and B only.

And I was not talking about this in-fact, I meant that there are people who haven`t solved a C even in practice sessions, and even they have solved C today.

→ Reply

5 years ago, # ^ |

I never solved E . Not even today. It looked easy today :p

→ Reply

I_LOVE_METSUKA

5 years ago, # |

Was expecting short statements but not this short...

→ Reply

Livw08

5 years ago, # |

+84

I passed Div2 C just by reading examples :D

→ Reply

har_vi

5 years ago, # ^ |

+23

I think most did same:)

→ Reply

zjuwyz

5 years ago, # ^ |

So.. Is there a necessarily proof that it's correct to do...whatever we did?

→ Reply

Adhami

5 years ago, # ^ |

Me too

→ Reply

Mahilewets

5 years ago, # ^ |

F(n, k) =(n+1)/(k+1)

→ Reply

Mahilewets

5 years ago, # ^ |

+11

I have just generated values and observed the pattern

→ Reply

BeardAspirant

5 years ago, # ^ |

why is that so? I tried to see the explanation given below but still fail to understand what is meant by the question

→ Reply

Mahilewets

5 years ago, # ^ |

← Rev. 2 →

We should do something like this

Each element X of 1,2,3,...,N is the smallest element in some Y(X) combinations

Y consists of elements X, X+1, X+2,... N

So we should somehow compute Y's

Then apply following formula :

F=sum(X*Y(X))/Z

Where Z is number of k-combinataions from N elements

→ Reply

Ahmad

5 years ago, # ^ |

The function F(n,k) is largest when k is 1 and smallest when k is n. So you want the difference between n and k to be as large as possible so you can maximize F(n,k). So just pair the numbers so that the sum of differences is as large as possible (I think greedy pairing works for that).

It's not exactly a formal proof but I think it's correct.

→ Reply

5 years ago, # ^ |

I think this would give you the sum of expected values

$\text{[math]}$

We can naively say that in order to maximise sum we need to maximise A[i] - B[i] + 1 . But that's not a rigorous proof either

→ Reply

rishus23

5 years ago, # ^ |

yeah, as a intuitive proof — [ more elements -> keep them in smaller groups so that each element will have more influence over the summation.]

→ Reply

https://en.wikipedia.org/wiki/Rearrangement_inequality

5 years ago, # ^ |

Once you prove/guess that F(n_i,k_i)=(n_i+1)/(k_i+1), the question is how to maximize the sum. The answer:

So to maximize in this case, we need to sort (n_i+1) and 1/(k_i+1) in the same order, which is equivalent to sorting n_i and k_i in opposite orders.

→ Reply

5 years ago, # ^ |

how is $\text{[math]}$ ?

→ Reply

5 years ago, # ^ |

For each m<=n, look at the subsets of {1,...,n} whose minimum element is m. There are (n-m)C(k-1) of those (because once you choose m, you have to choose k-1 remaining numbers from {m+1,...,n}.

Thus, the weighted average is the sum of m*(n-m)C(k-1) , 1<=m<=n, divided by nCk.

Using some basic identities (hockey stick), this simplifies down to (n+1)/(k+1).

→ Reply

5 years ago, # ^ |

Yeah I was able to derive the formula , but how do you get all terms cancelled . Also what do you mean by hockey stick ?

→ Reply

https://en.wikipedia.org/wiki/Hockey-stick_identity

5 years ago, # ^ |

+19

But after thinking a little bit... it's not even needed! There's a simple bijective proof that the numerator equals (n+1)C(k+1).

If we choose k+1 numbers from {0,...,n}, and throw away the lowest number, we get k numbers from {1,...,n}. How many times does each k-set get repeated? Precisely its minimum-element number of times!

→ Reply

5 years ago, # ^ |

← Rev. 2 →

DELETED (Sorry for my mistake , I get it) .

→ Reply

5 years ago, # ^ |

Nope, if you take a subset of size k+1 of {0,...,n} and remove the lowest element, you will always get a subset of {1,...,n} of size k.

→ Reply

5 years ago, # ^ |

+10

I love this proof as it is so elegant and straight forward, yet, I still want to know how would you get rid of the (j*) prefix from this formula.

→ Reply

5 years ago, # ^ |

+14

$\text{[math]}$

Then use the hockey stick formula for the inner sum, and again for the outer sum.

→ Reply

5 years ago, # ^ |

Thanks, got it now. :)

→ Reply

jbaramidze

5 years ago, # ^ |

"Thus, the weighted average is the sum of m*(n-m)C(k-1) , 1<=m<=n, divided by nCk."

1<=m<=n? why till n? shouldn't it be till n-k+1?

→ Reply

5 years ago, # ^ |

Sure. But it doesn't matter, since if m>n-k+1, the binomial coefficient will be 0 anyway.

→ Reply

Pancake

5 years ago, # ^ |

← Rev. 3 →

+13

This is one of the frustrating things about competitive programming that make me hesitant to participate again. It is possible to get a problem accepted without being able to argue about the correctness. In mathematics and real CS, this is nonsensical, useless and completely unacceptable.

→ Reply

5 years ago, # ^ |

+14

Competitive programming is not math/CS. (I myself am a math/CS person, but I know that in competitive programming I might not need to prove correctness. On the other hand, having math/CS background helps to give intuition whether an approach will likely be correct or not.)

→ Reply

Pancake

5 years ago, # ^ |

← Rev. 6 →

+15

It can be mathematics/CS if one takes the time to understand the reasoning. The fact that it sometimes encourages non-sense (by not requiring the contestants to actually understand their solutions) is one of the reasons I think it's sort of overrated. There have been times when I got introduced to some graph algorithms and was able to code them in a competitive programming environment without having a clue about why they worked. It's a relief that those times are over. I think many competitive programmers just use "pattern recognition" (of the form "I have encountered a similar problem before" or "the samples reveal a plausible approach") and end up ACing problems with a minimal or even nonexistent amount of the much-needed rational thinking. (Yes, I believe that is the case too for a number of competitive programmers who are highly rated on this site or even scored IOI medals and the like). Over the time, I realized that writing formal proofs and good code is more enjoyable for me than competitive programming.

→ Reply

5 years ago, # ^ |

← Rev. 3 →

+11

I think this is somewhat a fault on the problem setter's part — had they asked for the value of sum(F(A, B)) it would requires a prove for it. (Maybe they didn't asked for it since it's just Div2C .... but yeah I would rather ask for full feedback and use it as 2D or 2E)

→ Reply

4k1502

5 years ago, # ^ |

Worst Div2C ever!

→ Reply

always_4ever_5_25__21_SS

5 years ago, # ^ |

same here. but C and D had the worst sample explanations ever.

→ Reply

MrMorning

5 years ago, # ^ |

← Rev. 2 →

Spent plenty of time Prooving $\text{[math]}$ and the greedy is correct during the contest, although I had observed the feature in the sample. Sad.

→ Reply

BeardAspirant

5 years ago, # ^ |

how?? I am still confused as to what the question means and a lot of people have seemingly solved it by seeing the samples.

"Consider all possible k-element subsets of the set [1, 2, ..., n]. For subset find minimal element in it. F(n, k) — mathematical expectation of the minimal element among all k-element subsets."

This statement does not make any sense to me

→ Reply

5 years ago, # ^ |

Consider all k-element subsets of the set {1, 2, ..., n}. For each subset, look at the smallest element in it. For example, when n = 4, k = 2, you have the following:

{1, 2} with smallest element 1
{1, 3} with smallest element 1
{1, 4} with smallest element 1
{2, 3} with smallest element 2
{2, 4} with smallest element 2
{3, 4} with smallest element 3

Define F(n, k) as the average of all these smallest elements. So $\text{[math]}$ .

→ Reply

5 years ago, # |

+38

You know you are 100% sure of your solution when you lock your problem even after getting hacked

photo

→ Reply

SlowDecay

5 years ago, # ^ |

+14

Actually I got that "hacked" notification real late. After making an unsuccessful hacking attempt on someone's code, I got the notification that my code has been hacked -_- . Don't know if it was my internet problem or something else.

→ Reply

5 years ago, # |

← Rev. 2 →

+45

I should have read the Russian statements.

I don't know how to speak Russian but it can't be worse than the English statements.

→ Reply

Adhami

5 years ago, # |

D is easy if you can understand it. I understood it but I can't solve it :'(

→ Reply

servesh196

5 years ago, # |

Is there anyone who got TLE in B div-2 just reading input and printing output

→ Reply

Adhami

5 years ago, # ^ |

what is your language if C++ use scanf and printf

→ Reply

5 years ago, # ^ |

use

ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

→ Reply

Steady_Bunny

5 years ago, # ^ |

change language to c++14 if using c++11

→ Reply

zjuwyz

5 years ago, # ^ |

Yes T.T

→ Reply

EbraM96

5 years ago, # |

+18

Me seeing the succinct statements>>>> hell yeah!

After reading statements>>>> wait, what ?

→ Reply

madn

5 years ago, # |

+10

Problem D blew up my brain, how to solve it?

→ Reply

floatingfowl

5 years ago, # ^ |

I think if there is a -1 node, then an answer can always be formulated. But other than that, no clue

→ Reply

Deanamic_Programming

5 years ago, # ^ |

← Rev. 2 →

When there is a -1 vertex, you can simply do a dfs and solve it greedily. When there isn't any, if the number of 1 vertex is odd you can't solve it (the sum of degrees of the subgraph should be odd which is impossible). This is as far as I got, in the case which is left I believe you can greedily solve it aswell but I'm not sure.

→ Reply

Deanamic_Programming

5 years ago, # ^ |

← Rev. 3 →

I'll call d[i] == 1 vertices black and d[i] == 0 vertices white.
So given the case where the number of black vertices is even we can solve it greedily.
We can consider any spanning tree of the graph and do a dfs, let it return 0 if the subtree is solved or 1 if it is unsolved. Hence Black vertices are unsolved and white vertices are solved. Then we will put the edge to the parent if it is unsolved.

If the parent is solved but not the subtree, after putting an edge the parent will become unsolved and the subtree solved.
If the parent is unsolved and the subtree aswell, both will become solved.

We can see that the parity of unsolved vertices is always the same, while running this dfs is simply pushing these unsolved vertices up. Then if the black edges are even at the start, we can simply push them all up the root of our spanning tree.

→ Reply

Paul-Andre

5 years ago, # ^ |

There is an answer iff there is a -1 or there is an even number of 1's. You can then get the solution by doing a dfs and just greedily selecting edges you need on your way back up.

→ Reply

kabirsahni8

5 years ago, # ^ |

Can you please elaborate why is there always an answer when d[i]=-1 for some i.

→ Reply

5 years ago, # ^ |

It doesn't matter what degree the -1 node has, so all of it edges can be arbitarily choosed or not choosed. By using this we can fix every adjacent nodes to have correct parity degree, because we can either choose it's edge to the -1 node or not. After that we can make sure the nodes adjacent to the nodes adjacent to the -1 node are good, and so on. Because the graph is connected, we can make every node's degree good.

→ Reply

kabirsahni8

5 years ago, # ^ |

← Rev. 5 →

Going by that logic if we satisfy parity of 3 using 1(the -1 node) we get stuck,don't we?

4 3

-1 0 1 1

1 2

1 3

3 4

→ Reply

5 years ago, # ^ |

At the beginning of the algorithm you can replace "-1"-s for necessary values (see my comment below).

→ Reply

5 years ago, # ^ |

I think the better approach is to calculate the sum of "1"-s and "-1"-s and if we have "-1"-s, to change them for "1"-s or for "1"-s + one "0" depending on the parity of the sum. So we will move to the graph which has "1"-s and "0"-s only.

→ Reply

Ashishgup

5 years ago, # |

Why does this submission give WA on TC 5 and this submission give AC, when the only difference is the equality sign in the comparator function?

I think that the first one should also give AC..

→ Reply

Len

5 years ago, # ^ |

Compare function must return 0 if they're equal.

→ Reply

Ashishgup

5 years ago, # ^ |

Why? How does it make a difference?

→ Reply

5 years ago, # |

Do you think 1 million number 10e9 can be read with ONLY "cin" in 2 seconds?

→ Reply

LoDThe

5 years ago, # ^ |

← Rev. 2 →

ios::sync_with_stdio(false);
cin.tie(NULL);

before reading

→ Reply

5 years ago, # ^ |

Yes, I know it. But someone don't write it and still get AC pretest with 1800-2000ms ._. ._.

→ Reply

LoDThe

5 years ago, # ^ |

Maybe they use different compilers?

→ Reply

5 years ago, # ^ |

I think pretest don't have 1 million number 10e9 :)) it have smaller :))

→ Reply

hiddentesla

5 years ago, # ^ |

i forgot to use ios_base::sync_with_stdio(false);

but i tested my code on local machine with 1000000 10e9 and got 1.53 ms (my machine is way slower then cf machine)

→ Reply

kuldeepfouzdar

5 years ago, # ^ |

here is the victim http://codeforces.com/contest/841/submission/29559824

→ Reply

5 years ago, # |

+85

WHY

→ Reply

5 years ago, # ^ |

condolence! I am in the same boat

→ Reply

Sharon

5 years ago, # ^ |

+54

→ Reply

brettfazio

5 years ago, # ^ |

-14

Typically I would be unappreciative of the meme, but I feel it has real value here. Thank you for positively contributing to the Codeforces community!

→ Reply

ihumaunkabir

5 years ago, # ^ |

← Rev. 2 →

-8

→ Reply

marcospaulo

5 years ago, # |

+12

I got Unexpected verdict on my hack in the solution on problem A and receive this result. What does it mean?

→ Reply

TooNewbie

5 years ago, # ^ |

Probably someone hacked before you and you didn't reload page to see that. It happened to me in some contests too.

→ Reply

marcospaulo

5 years ago, # ^ |

+12

That was not the case.

I tried to hack Mr.Donaldo three times using the following testcase: 5 2 aaaaa

and then received this verdict.

→ Reply

marcospaulo

5 years ago, # ^ |

KAN

→ Reply

bojika_420

5 years ago, # ^ |

I also had the same problem, at first I got unexpected verdict,but after 30 minutes i tried again and got succesful hack

→ Reply

kilimanjaro2

5 years ago, # ^ |

I too had the same problem, in fact with the exact same person.

→ Reply

ista2000

5 years ago, # ^ |

Both of your profile pictures also...

Dont get me wrong, Mr. Bean is <3

→ Reply

xuanquang1999

5 years ago, # |

How to solve D?

→ Reply

5 years ago, # ^ |

pick K elements which are different and remove them from the array permanently , keep repeating this process , in the end , we will have atmost K-1 elements left , those are the only possible candidates for our answer , this can be simulated with a segtree easily.
Note that K=2 version has appeared before several times.

→ Reply

kingofnumbers

5 years ago, # ^ |

Version with K>2 is also well-known and even appeared in some companies interviews

→ Reply

satyaki3794

5 years ago, # ^ |

← Rev. 4 →

+55

I think you can just check the frequencies of all the possible candidates for the answer. Sort the subarray. Let sz = (R-L+1)/k. Then the only possible choices are the elements at indices sz+1, 2*sz+1, 3*sz+1... while <= R. Check frequency of each and if any of these satisfy the condition, then that is the answer.

Time complexity is O(N*K*logN)

Code

→ Reply

xuanquang1999

5 years ago, # ^ |

Elegant solution.

→ Reply

5 years ago, # |

Is there a better solution to D that NlogNKlogK if no , then why is the time limit so strict.

→ Reply

PlayWithWind

5 years ago, # ^ |

+39

There's funny solution to Problem D which it's complexity is O(cnlogn) or O(cn).

First, We randomly choose the answer in interval [l, r], then check it.

For even k = 5, there's nearly 0.2 probability that we can find it.

Assume we randomly choose 90 times, we can deal with each query with correct probability 1 — (0.8)^90 = 0.99999999810286240993581145418021.

So for a each testcase, the probability for all the queries are right is 0.99999999810286240993581145418021^{300000} = 0.99943102065261594539434408072871.

We need to pass several testcases, assume there're 100 testcases, We can get accepted with probability 0.99943102065261594539434408072871^{100} = 95%.

That's our destiny.

→ Reply

5 years ago, # ^ |

i would have definitely submitted this if we had full feedback with all test cases , but with pretests i preferred not to do this.

→ Reply

PlayWithWind

5 years ago, # ^ |

Sure, I do not have the ability foreseeing the risk

→ Reply

mnaeraxr

5 years ago, # ^ |

How do you solve it in O(c·n). How do you find the frequency of an element in an interval [l, r] in O(1)?

→ Reply

5 years ago, # ^ |

offline

→ Reply

xuanquang1999

5 years ago, # ^ |

How to do this offline?

→ Reply

djq_cpp

5 years ago, # ^ |

← Rev. 2 →

29579955 UPD:My friend's PRETEST-PASSED submission.(despite getting TLE)

→ Reply

PlayWithWind

5 years ago, # ^ |

And you can use some simple technology to reduce the complexity to O(cn). Something like Random for each query at first, then get the answer while inserting the elements to a hash-table.

→ Reply

vsp4

5 years ago, # ^ |

← Rev. 2 →

I did with something like sqrt decomposition and it atleast passes in pretest < 500ms

Set Freq = 300. Max Number of heavy elements having > Freq = 1000

Process all queries on heavy elements independently. Elements having freq <= 300 can only be answer where r-l+1 <= 1500. So bruteforce on those light queries.

Something like O((N+Q)*1000 + (N + Q)*1500)

→ Reply

SirirNicheBirirDokan

5 years ago, # ^ |

← Rev. 2 →

Probably to defend $\text{[math]}$ straightforward Mo solutions.

→ Reply

prophet_ov_darkness

5 years ago, # ^ |

I couldn't pass $\text{[math]}$ with some constant factors. I'd say TL is definitely more strict than it should be.

→ Reply

Rafbill

5 years ago, # ^ |

It is possible to solve it in time O(NKlogN) using a wavelet tree.

→ Reply

5 years ago, # |

← Rev. 2 →

-15

Interesting questions!! Loved it Dont you get my ironical statement downvoters??

→ Reply

linkret

5 years ago, # |

Can anyone provide a proof for Div1 C?

I got nowhere by trying to analyze the expected value.

→ Reply

5 years ago, # |

← Rev. 2 →

Ok so I almost hacked V--o_o--V's solution for D but I couldn't submit the file because it was too big...later on, I got the answer to my question that I should send the generator...I guess nothing else can be done, now, can it? generally, what sort of syntax should the generator have? I mean does it write the test to standard output? What language should it be written in?

→ Reply

5 years ago, # ^ |

+18

You can choose among many languages. Yes, it should print the test to standard output. Once I luckily got 7-th place in Div2 which could have been 5-th if I knew this. I guess we both learnt it the hard way :d

→ Reply

Na2a

5 years ago, # ^ |

How to hack his solution? And what's the probability of hacking? :)

→ Reply

5 years ago, # ^ |

A test with 60001 of 1 and the other values all distinct that's querying the interval [1, 300.000] 300.000 times would be just enough. The probability for his solution to work on one query is P = 1 — (4/5)^40. The probability for all the queries to work at once is P^300000 ~= 1e-14. It was failing on my machine after less than 20.000 queries usually. So it was sure deal:))The constant that he chose made it easy to hack. On the other side, if it were much larger than that, he'd get TL

→ Reply

Na2a

5 years ago, # ^ |

I have 80 as constant :D
Had pretests passed, not sure about TLE.
But seems like it's going to fail as well.

→ Reply

5 years ago, # ^ |

On my test, you get 99.4 percent probability of correctness, which is pretty much enough I think. Even if this extreme test were used 100 times in a row, you'll still have a 58 percent chance of getting AC, and for sure there won't be more than 5 or so tests like this one. Also, this test is the worst scenario, so it seems your solution will pass. If they really wanted to make sure it wouldn't pass, they'd have put K <= 8-9 which would destroy any such approach. Honestly, though, I find the randomized approach quite elegant

→ Reply

Na2a

5 years ago, # ^ |

I had tle on pretests in systesting lol

→ Reply

adamant

5 years ago, # |

+39

CF admins, why do you let it happen? 674G - Choosing Ads

→ Reply

tupko

5 years ago, # ^ |

← Rev. 2 →

-8

Man, now the TL is 2.5 seconds! It's harder!

→ Reply

C137

5 years ago, # |

+34

Am i the only one who solved Div.2 C by just looking at the samples, without understanding what the author wanted???

→ Reply

NirShalmon

5 years ago, # ^ |

I did that too.

→ Reply

saisurya027

5 years ago, # ^ |

Me too :)

→ Reply

fmota

5 years ago, # |

+71

Waiting Petr screencast to see myself being hacked. :)

→ Reply

Petr

5 years ago, # ^ |

+122

Sorry, wasn't recording today :)

→ Reply

fmota

5 years ago, # ^ |

+48

:( . I hope you have another chance to hack me.

→ Reply

karanbatra

5 years ago, # ^ |

haha xD

→ Reply

VovanF98

5 years ago, # ^ |

What kind of screencast do you provide?:)

→ Reply

5 years ago, # |

-13

Very bad statements (Guys using the Russian statements have an advantage), Long queue at the first 30 mins, Very weird hacking/locking problems bug in my room (not sure about the others).

This contest will be unrated right ?

→ Reply

always_4ever_5_25__21_SS

5 years ago, # ^ |

rated or unrated, I really hate to say this (cause CF really helped me improving a lot) but last few CF contests were really awful and not to forget that there were back to back two unrated contests.

→ Reply

TooNewbie

5 years ago, # ^ |

Anyway it was understandable, mistakes were grammar mistakes.

→ Reply

chenmark

5 years ago, # ^ |

+16

Usually I don't complain about grammar if it costs me a few minutes. But today's B took me 45 minutes to understand, and only after backsolving from examples. When variance in read times dominates variance in solve times, then we're measuring the wrong thing.

It's not like I didn't try either; I asked very early on for clarification, and got no response.

→ Reply

TooNewbie

5 years ago, # ^ |

Yes, you are right. Div2D/Div1B statement was very bad.

→ Reply

5 years ago, # ^ |

even A

→ Reply

5 years ago, # ^ |

and C was modified so many times I opt not to do that. But now I see people just guessed the solutions LOL

→ Reply

unused

5 years ago, # |

+37

Am I the only person that all problems felt too hard? T_T

→ Reply

saksham2405

5 years ago, # |

← Rev. 2 →

I was trying to hack @MrSoab B solution with ai=10^9 and n=10^6 it was giving me invalid input why?

then I tried with ai=10^7 and n=10^4 and got unsuccesful even though his sum variable should overflow as he declared it as integer

→ Reply

5 years ago, # ^ |

1) Because you can upload only 256KB input test (maybe) 2) overflow don't mean result is wrong :))

→ Reply

Deanamic_Programming

5 years ago, # ^ |

Exactly, even if it overflowed the parity was the same, so depending on the language it wouldn't get hacked.

→ Reply

walnutwaldo20

5 years ago, # |

Div. 2 C and D were both shots in the dark for me

→ Reply

Paul-Andre

5 years ago, # |

I guessed a solution for div 2 C based on the examples and it passed the pretests. I sorted A and sorted B in reverse and paired them. But is it actually the solution? How does one prove that this works?

→ Reply

http://codeforces.com/contest/840/submission/29578088

5 years ago, # ^ |

Prove that if n₁ ≥ n₂, k₁ ≤ k₂, then F(n₁, k₁) + F(n₂, k₂) ≥ F(n₁, k₂) + F(n₂, k₁), so it's always at least as good to assign n₁ to k₁ and n₂ to k₂, instead of n₁ to k₂ and n₂ to k₁. This means if you sort B in increasing order, you always want to have A sorted in decreasing order, since otherwise you can do better.

→ Reply

we7d

5 years ago, # ^ |

← Rev. 2 →

it works because we have min(A)>=max(B) and we have to maximize the sum of A'[i]-B[i] .

→ Reply

jonathanirvings

5 years ago, # |

+67

Achievement unlocked : Successfully challenged a randomized solution

Phew, I pressed the hack button while hoping that I won't be very unlucky.

→ Reply

anveshi

5 years ago, # ^ |

+35

And I pressed the submit button while hoping that I won't be very unlucky :P

→ Reply

MiteshAgrawal

5 years ago, # ^ |

That statement seemed so apt for 'L' to say, with that profile picture. :D

→ Reply

droneKingxiiiiiiiDaddy

5 years ago, # |

How to solve Div 2 D ?

→ Reply

5 years ago, # ^ |

If it's a tree, the problem is trivial. But it turns out that the extra edges don't have to be used... so just treat the graph as a tree.

It's possible if and only if the number of "1" labels is odd. So if there are any "-1" labels, it can always be done (replace all "-1"s with "0"s, except for possibly one "1"). Then do a depth-first search; the edges adjoining the leaves are forced, which forces all the edges all the way up to the root.

→ Reply

nirvana

5 years ago, # ^ |

Can you give me some similar problem to this, which you called trivial? I wanna try to solve that problem

→ Reply

5 years ago, # ^ |

What I meant is the following.

Suppose we have a tree (connected graph with no cycles). In this tree, the vertices are labeled 1 and 0; the goal is to choose a subset of "special" edges such that the vertices labeled 0 have an even number of special edges adjoining them, and the vertices labeled 1 have an odd number of special edges adjoining them.

This problem is quite straightforward, and once it's solved, it's easy to extend to a generic connected graph (even with multiple edges: it makes no difference).

→ Reply

arasmus

5 years ago, # ^ |

can you explain why the extra edges don't have to be used..

→ Reply

vilim_l

5 years ago, # ^ |

+11

In a cycle, every node has degree 2. That means that if you remove all cycles from your solution, it will still be correct.

→ Reply

har_vi

5 years ago, # |

Why don't we have different time limits for different languages. Solved C in python , got TLE but same solution in cpp passed. At-least for interpreted languages like python, ruby etc. we should provide 2X time limit.

→ Reply

Alexxx

5 years ago, # |

+10

Div2 e. Kirchhoff's theorem + Gauss method? I just couldn't find matrix determinant.

→ Reply

majk

5 years ago, # ^ |

+10

The answer is not determinant of the adjacency matrix, it is the permanent. Computing permanent however, is NP-hard.

→ Reply

NirShalmon

5 years ago, # |

+19

The task statements were very bad, but I think that the tasks were still understandable after reading them a few times. It's very annoying and should have been fixed before the contest, but it's really not a reason to make the contest unrated.

→ Reply

scorpion_guy

5 years ago, # ^ |

then you might have ended up solving them successfully X_X

→ Reply

Momentum

5 years ago, # |

← Rev. 2 →

+48

That moment when you don't understand any of the problem statements and manage to solve them successfully. xD

→ Reply

5 years ago, # ^ |

Read test and write solution :)) :))

→ Reply

EbraM96

5 years ago, # |

How to solve problem E? It gave me a headache!

→ Reply

5 years ago, # |

The task 841B How is it possible to have TLE on the pretests for the loop from 0 to 10^6, used to input data anyway, with the task's limit of 2 sec. GNU C++ 11 Thanks.

→ Reply

5 years ago, # ^ |

Maybe it's an issue with cin/cout being slow? Use ios::sync_with_stdio(0) and cin.tie(0) .

→ Reply

supernova.

5 years ago, # ^ |

Or just use scanf/printf instead of cin/cout. I had a friend who had TLE on the same pretest, and just changed cin to scanf and passed.

→ Reply

Evro

5 years ago, # |

+14

The Problems' statement was understandable to some degree,maybe was below average this time,but you could understand it.. that's how it was for me, It shouldn't be unrated :D

→ Reply

5 years ago, # ^ |

Sorry, I didn't understand your comment.

→ Reply

Evro

5 years ago, # ^ |

I can see where the problem lies now :)

→ Reply

5 years ago, # ^ |

I know that in practice, I didn't face such the problem for cin and cout.

2 secs and 10^6. This cycle must be finished before 1 sec is expired.

→ Reply

chunky_2808

5 years ago, # |

Got TLE on B using simple input , output only Can't understand why???

→ Reply

5 years ago, # ^ |

mee tooooooo :(

→ Reply

matnakash

5 years ago, # ^ |

Apparently, you need to use the IO 'accelerating' lines at the beginning of your main (if using C++):

iostream::sync_with_stdio(false);
cin.tie(0);

to stay within the time limit

→ Reply

chunky_2808

5 years ago, # ^ |

Ya , I have Solved the problem using Fastscan() .

But i am asking why i m getting TlE even when time limit is 2 SEC

→ Reply

Petr

5 years ago, # |

+55

Any hints for Div1 E?

→ Reply

Mediocrity

5 years ago, # ^ |

+15

Divide all mask into two halfs.

→ Reply

Endagorion

5 years ago, # ^ |

+16

Process all numbers within path by blocks of 256. For each bottom vertex of a block and each value of biggest 8 bits of XOR we can precompute the partial answer in 8 * 256: for each number there is a unique value of biggest XOR bits that make 11111111... after XORing (these will obviously be largest answers in their groups), after that traverse a tree from bottom to top and fill still unknown values by swapping smallest bit possible.

→ Reply

Wael.Al.Jamal

5 years ago, # ^ |

-49

Hi tourist, some one needs your help !!

→ Reply

unused

5 years ago, # |

+34

How to solve Div1 C? Ok well we can divide the numbers into some equivalent classes.... and so what?

→ Reply

King

5 years ago, # ^ |

← Rev. 2 →

--nevermind, this is probably wrong solution

→ Reply

jtnydv25

5 years ago, # ^ |

← Rev. 2 →

+44

Say you divide the array in groups of sizes X₁, X₂, ..., X_k. For now, lets consider all of the members of same group identical. In other words label them, and add a constraint that they appear in that fixed order.

Then, say there exist x_i indices in $\text{[math]}$ group, which have next element in the permutation belonging to the same group. Then the number of such orderings is:

$\text{[math]}$

Now, we can just use inclusion exclusion on the total number of indices where the next element is in same group. Such a term must be multiplied by $\text{[math]}$ when added to the total answer.

To find the sum over all tuples of x_i, we can use polynomial multiplication.

In the end, multiply the answer by $\text{[math]}$ to account for orderings in same group

I think this could have made a good FFT problem.

→ Reply

newCEA

5 years ago, # ^ |

← Rev. 2 →

If I understand correctly the answer is:

$\text{[math]}$

but could you clarify how this can be calculated using polynomial multiplication? I can't think of how to separate $\text{[math]}$ .

→ Reply

jtnydv25

5 years ago, # ^ |

← Rev. 3 →

+20

Let $\text{[math]}$ ,

$\text{[math]}$

Then the answer is coefficient of xⁿ in $\text{[math]}$

So, we can actually solve the problem in $\text{[math]}$ instead of O(n³)

29575088. This one is O(n²)

→ Reply

newCEA

5 years ago, # ^ |

Thank you, that clarified a lot.

→ Reply

niquefa_diego

5 years ago, # ^ |

f(i, oldBad, curBad) = ways to place i, i+1, ..., n-1 if we have placed 0, 1, ... i-1 and there are curBad pairs of consecutive numbers of the same class as i and oldBad pairs of consecutive numbers of the same class, but different of the class of i

answer is in f(0,0,0)

I guess you can figure out the base cases and how to do the recursive step :)

→ Reply

5 years ago, # ^ |

+58

https://csacademy.com/contest/archive/task/distinct_neighbours then you solve this and you're done. It has an editorial, a really nice dp

→ Reply

TeaPot

5 years ago, # ^ |

← Rev. 4 →

+34

Lol, I opened that problem and it is solved by me. But I didn't manage to solve it again today [facepalm]

→ Reply

lsmll

5 years ago, # ^ |

What is the time complexity of the DP solution described in the editorial? I'm having a hard time trying to figure it out.

→ Reply