Codeforces Round #339 (Div. 1 & Div. 2)

9 years ago, # ^ |

← Rev. 2 →

+73

Yes, i dont speak english very vell, but lately we'll correct this post. English statements will be created by Delinur, and she know English very well.

→ Reply

RostVel

9 years ago, # ^ |

But you translated Wikipedia...

→ Reply

9 years ago, # ^ |

← Rev. 3 →

From English to Russian Example This to This

→ Reply

strange_voice

9 years ago, # ^ |

← Rev. 2 →

-33

So this post can be better if you want Delinur to translate it to English, too.

→ Reply

ITDOI

9 years ago, # ^ |

Deliner->Delinur

→ Reply

Deemo

9 years ago, # ^ |

+14

Statements were pretty clear, thanks for that!

problems were also nice and interesting, I really liked C div1 and D div1 :)

my only complaint is A div1. there was no idea behind it, just a stupid geometry formula.

→ Reply

Reyna

9 years ago, # |

+80

i has very very good expect contest, so many prepared people and i like endagorion contest because they very very good.
best hope much good statements

→ Reply

tHE_kID

9 years ago, # ^ |

+68

isn't it rude to make fun of someone who just prepared a contest for you?

→ Reply

binary_eagle

9 years ago, # |

-40

Yeee, another codeforces round rated. Wishing ratings high to all, hope math problems to see.

→ Reply

9 years ago, # ^ |

-33

hope your english to learn

→ Reply

uc-nuts

9 years ago, # ^ |

This comment is actually funny! I like it!

→ Reply

tweety

9 years ago, # |

+83

Google Translate would have done better. :D

→ Reply

wafl

9 years ago, # ^ |

+23

=\ http://pastie.org/10686682

→ Reply

Xephy

9 years ago, # ^ |

+42

"we, its drafters — ordinary students, united by the fact that together are engaged in the circle in 179 schools"

Somebody help, my sides are leaving the orbit

→ Reply

9 years ago, # ^ |

Is this the original post? Hillarious!!!

because the problem will be solved, but even the tourist-y have to think about some

I bet touristy will scratch his head for the entire duration of contest, as to why the drafters have given solved problems in a contest :D

→ Reply

aka.Sohieb

9 years ago, # |

← Rev. 5 →

+32

The statement of problem B in the last round was horrible, i was not able to understand it till the contest ends.

and from the English used in this blog, I think this one will be worse :(

please make sure the problem statement be clear and concise to be fair enough for all contestants.

→ Reply

9 years ago, # |

I want to say the Tigutor-у that his knowledge of english is very good.

I'm not only fan of Ilya_MSU but fan of Tigutor too. What tasks have you created except Div1E?

→ Reply

9 years ago, # ^ |

← Rev. 2 →

+12

You will see the problems authors in the editorial when it is published :)

I will keep silence before.

→ Reply

9 years ago, # ^ |

+10

Div 1, F, certainly.

→ Reply

NaiveNaive

9 years ago, # |

+42

How do you know tourist will have to think it over..?

→ Reply

ifsmirnov

9 years ago, # ^ |

+62

Maybe they have asked him?

→ Reply

9 years ago, # ^ |

+10

Strong feeling about this : Some new algorithm/trick/concept from some recently published paper will be involved.

→ Reply

9 years ago, # |

+614

→ Reply

kuna

9 years ago, # ^ |

:D :D :D :D :D :D :D :D :D

→ Reply

9 years ago, # ^ |

He scared to participate in contest :D

→ Reply

9 years ago, # ^ |

+54

but..

→ Reply

9 years ago, # ^ |

← Rev. 2 →

+11

More upvotes on a comment than the post itself :) Tourist is gonna make the contest setter remember who he is.

→ Reply

9 years ago, # ^ |

→ Reply

Ir1d

9 years ago, # |

-20

It's really inspiring to me that someone with less rating than me could hold an CF contest. Thanks!

→ Reply

9 years ago, # ^ |

-51

I'm so sure in Tigutor that I'm going to cut my balls off if he won't be red in a month. Just like Ilya_MSU

→ Reply

yashar_sb_sb

9 years ago, # ^ |

+22

I'll remind You to do so. ;)

I'm waiting for next month.

→ Reply

viesis

9 years ago, # ^ |

-15

S/He seems careless! Maybe s/he is the girlfriend of IlyaMSU?

→ Reply

9 years ago, # ^ |

I'd like to but I'm not. :(

→ Reply

maximaxi

9 years ago, # ^ |

-22

Username relevant.

→ Reply

A.Magdy7

9 years ago, # ^ |

I don't want to underestimate from anyone but he has Registered 18 months ago and the maximum rate he can get 1514 and now you say that he will be red in a month do you actually think so

→ Reply

9 years ago, # ^ |

Thanks a lot for your research

→ Reply

A.Magdy7

9 years ago, # ^ |

research!! it just a click on his handle

→ Reply

microtony

9 years ago, # |

+25

I enjoy contests by lower rating writers. They usually contain interesting problems that involves creative thinking.

→ Reply

9 years ago, # ^ |

-28

Has Endagorion too low rating for you?

→ Reply

nuhu_ius

9 years ago, # |

-23

I think there are at least 3 problem eassy in CF round 339.

→ Reply

kajol_cse

9 years ago, # ^ |

No buddy. All problems are solvable by you if you are coder like Tourist :)

→ Reply

saliii

9 years ago, # ^ |

why you must compare with tourist... you must do better and you must solve problems even tourist cant... you must make it solvable.

→ Reply

kajol_cse

9 years ago, # ^ |

It is quite impossible for him . I know him very closly

→ Reply

rng__58

9 years ago, # |

← Rev. 2 →

-52

Your code here...

→ Reply

9 years ago, # ^ |

Spam detected :P

→ Reply

rng__58

9 years ago, # ^ |

-14

thanks!

→ Reply

9 years ago, # |

A contest prepared by so many people is my worst nightmare. Hope for the best though.

→ Reply

TsukiZombina

9 years ago, # |

+12

I'm new here, could you tell me if there's a difference between Div. 1 and Div. 2? Thanks

→ Reply

ankeet

9 years ago, # ^ |

Hello, Div 1 is more difficult and is generally for contestants with a rating >=1900. On the other hand, Div 2 is easier and for less experienced competitors.

→ Reply

yashar_sb_sb

9 years ago, # ^ |

When the contesters take part in Codeforces contest, they raise or lower their rating that reflects their ability to solve the tasks. The rating is a modification of Elo rating, several details can be read in a fuller form. According to the rating, the contestants are split into two divisions: the second one (the weaker one, amateurs) and the first one (the stronger one, pros). The contestants who don't take part in contests and those whose rating is below 1900 belong to the second division. The 1900+ rating means that you're part of the first division. Usually two types of contests are held on Codeforces: for the second division contestants (the first division contestants can take part there out of competition) and for both divisions. The first contest type contains simpler and learning-oriented tasks.

→ Reply

AClover

9 years ago, # ^ |

+12

What is your div1 account?

→ Reply

9 years ago, # ^ |

Difference between Div. 1 and Div. 2

→ Reply

9 years ago, # |

← Rev. 2 →

To be honest I don't think the English is poor...quite clear for me...

→ Reply

Reyna

9 years ago, # ^ |

+14

they edited it, the last version was a bit funny but if you tried your best you could understand what it meant

→ Reply

Arpa

9 years ago, # ^ |

-16

yes!

Initial revision is really funny!

Look, like this one : << I invite all of you write this round >>.!!

→ Reply

9 years ago, # |

← Rev. 2 →

BTW,you're good-looking:D[user:Tigutor]

→ Reply

Infused

9 years ago, # ^ |

+10

Aren't you male?

→ Reply

9 years ago, # ^ |

+11

Yes...But it doesn't matter to praise him...

→ Reply

9 years ago, # ^ |

-8

He is a she. No guy praises another guy for looks bro, unless gay.

Otherwise, chinese names gender neutral. I know a girl who has same name as her.

→ Reply

9 years ago, # ^ |

it's quite normal for us to praise other's looking no matter what the gender you are,if you like.

→ Reply

9 years ago, # ^ |

← Rev. 3 →

Alright, I accept that. But YOU are a girl, unless, your name is gender neutral and you are gay(which is cool, btw) :)

→ Reply

9 years ago, # ^ |

but you're wrong.maybe there's something different between our culture.anyway,stop talking about this.

→ Reply

9 years ago, # ^ |

Eeek!!!

No offence to you sir, our cultures are probably different.

→ Reply

9 years ago, # ^ |

Okay.good luck for the coming contest

→ Reply

9 years ago, # ^ |

+110

→ Reply

azui

9 years ago, # |

-49

哇塞高中生出题好厉害也！

→ Reply

axp

9 years ago, # |

+37

I hope tourist takes part in this round and talk about the difficulty

→ Reply

smahdavi4

9 years ago, # |

Does the scoring mean that the difficulty of div2 D & div2 E is the same?!

→ Reply

404Error

9 years ago, # ^ |

It's difficult to say. For decent div1 coders it may be same. For good div2 coders it may not.

→ Reply

Ahmed_Mostafa

9 years ago, # |

-69

The comment is hidden because of too negative feedback, click here to view it

→ Reply

Xellos

9 years ago, # ^ |

+49

Look, a self-predicting comment!

→ Reply

9 years ago, # ^ |

+12

Make here as a link to your comment, then it'll be perfect :)

→ Reply

AshishYadav

9 years ago, # |

Can someone plz explain the second testcase in DIV-2 1000 points....

→ Reply

logickaiser

9 years ago, # ^ |

What is 'product'? I don't get it....

→ Reply

logickaiser

9 years ago, # ^ |

Now I got it.. Product means multiply... My english is terrible....

→ Reply

dush1729

9 years ago, # |

If i get WA in pretest then also 50 points will be deducted?

→ Reply

Far

9 years ago, # ^ |

yes, but if you don't AC that problem , there will be no decrease on your total score.

→ Reply

Far

9 years ago, # ^ |

this is what Codeforces says : "there is 50 points penalty for submission which fails the pretests or resubmission (except failure on the first test, denial of judgement or similar verdicts). "

→ Reply

newts

9 years ago, # |

+17

I'm becoming newbie today n:). So happy to achieve this feat. Feeling gratefull. after being hacked 3 times. :)

→ Reply

9 years ago, # ^ |

→ Reply

Xellos

9 years ago, # |

← Rev. 2 →

+15

Well. That could've gone better.

But dat number of pretests... I really hope not to fail systests now :D

→ Reply

bicsi

9 years ago, # |

+41

Let the hate begin!

→ Reply

9 years ago, # ^ |

+23

He did hint at problems being hard, but people laughed him off because of his weak english.

→ Reply

bicsi

9 years ago, # ^ |

I cried at your comment XD

→ Reply

ManikantanV

9 years ago, # |

Will the tests which lead to successful hacks be used for system testing?

→ Reply

9 years ago, # ^ |

Yes.

→ Reply

egor.okhterov

9 years ago, # |

Do we need convex hull in div2C or we can find the smallest radius without it?

→ Reply

mingaleg

9 years ago, # ^ |

Min from distances to all edges.

→ Reply

9 years ago, # ^ |

No, because points are given clockwise or anticlockwise direction.

→ Reply

AndrewB330

9 years ago, # ^ |

Look at the second test

→ Reply

9 years ago, # ^ |

You just need to find the point on the polygon closest to P and the one farthest away, the one closest to it is going to be on one of the edges ( so check each edge), the one farthest away is going to be one of the vertices ( so check each vertex )

Let MAX be the largest distance to P and MIN be the shortest distance to p. Then the aswer is (MAX*MAX-MIN*MIN)*PI.

No convex hull required.

→ Reply

9 years ago, # ^ |

-7

the one closest to it is going to be on one of the edges

wrong.

Consider the segment with end points -1,2 and 1,2. The minimumis at point 0,1.

→ Reply

tau0

9 years ago, # ^ |

← Rev. 3 →

read more careful, 0,1 is on the edge

→ Reply

inactive06

9 years ago, # ^ |

I tried something similar , but I was checking for min distance on vertex too. Can you clarify a bit more why the one closest is going to be on one of the edges?

→ Reply

__builtin__wolfy

9 years ago, # ^ |

It could be that the point which is closest to p is an endpoint of some line segment. In general, for a given line segment if the projection of p lies on that line segment then that's the closest point to p on that segment. If not, then the point which is closest to p is going to end up being one of the endpoints of that segment.

→ Reply

9 years ago, # ^ |

I think we just need to find the point of intersection of each side with normal from origin to that side. If it lies within that segment, then that point is to be used to find minimum radius, otherwise, the smaller distance to origin from the 2 end points of the segment are to be taken as candidates for minimum.

Waiting for editorial.

→ Reply

9 years ago, # ^ |

edge is not the same thing as vertex. The one farthest away is a vertex, the one closest is ON an edge.

→ Reply

9 years ago, # ^ |

Oh, read it wrong. My bad :)

→ Reply

mukulchandel

9 years ago, # ^ |

we can do it without convex hull also. to find shortest distance of each line segment from center first find distance of both points from center and then check if the line having slope equal to the perpendicular of this lines egment and passing through center intersects the line segment or not. if yes, calculate intersection point as well as its distance from centre. take minimum of all calculated distances.this is the smallest radius.

→ Reply

HandIeNeeded

9 years ago, # |

I don't think Div1 B and C worth the same score. T^T

→ Reply

Kareem

9 years ago, # |

+19

What's the idea behind Div2 Problem C pretest 3?

→ Reply

ManikantanV

9 years ago, # ^ |

I tried a naive solution by finding nearest and farthest radial points of the polygon. Guess there is more to it. This approach works for the illustrations

→ Reply

savinov

9 years ago, # ^ |

I suppose something like:

→ Reply

BronfenBova

9 years ago, # ^ |

+60

I think this

→ Reply

9 years ago, # ^ |

How did you make that colorful and cool drawing?

→ Reply

9 years ago, # ^ |

Umm, microsoft paint? Then post a picture comment here.

→ Reply

ch_egor

9 years ago, # ^ |

You are right. Something like this :)

→ Reply

9 years ago, # |

-6

Div2 B time limit was a bit too strict I thought

→ Reply

9 years ago, # ^ |

Dont use python or biginteger.

→ Reply

gfonn

9 years ago, # ^ |

No! You must check if the given number is beautiful (reading it as a string). If it isn't beautiful, save it for the final step. For each beautiful number, you have (lenght-1) zeros. So, if the number is only composed by one "1", and this one must be at the first position (because the restrictions), you don't need to do estrictly a "product", because most of them are one "1" and a bunch of "0". You need to save the sum of total zeros of beautiful numbers called "zSum". So, if the non-beautiful number is zero, the answer is zero. Else, the answer is a string composed by the non-beautiful number (remember to read it as a string, because the lenght can be 100000 as maximum) and then "zSum" zeros. I took me a few submissions before figure it out.

→ Reply

9 years ago, # ^ |

Yes, my java submission counts number of zeros and appends a 1 or the non-beautiful number at the front. In java, it TL-ed on test 8, but in c++ it did not. Minor optimizations could drastically change the verdict for this problem. That is why I think this TL was too strict(I wonder how hard it was to pass for python users...)

→ Reply

eboy2914

9 years ago, # ^ |

15351819

→ Reply

gfonn

9 years ago, # ^ |

Oh, sorry then. Yes, I submitted it in C++.

→ Reply

likecs

9 years ago, # |

+16

The test case 1 900000000000000000 12345678, helped me earn 1800 points in the contest by hacking the first problem of almost every user in my room. My best ranking ever, thanks to hacks.

Actually python rocks for this question.

→ Reply

9 years ago, # ^ |

Whats the correct answer?

→ Reply

likecs

9 years ago, # ^ |

1 12345678 152415765279684, is the correct answer

→ Reply

alex_bucevschi

9 years ago, # ^ |

-6

I think 1 12345678 152415765279684 108064748184340920 is the correct answer

→ Reply

9 years ago, # ^ |

I think with C++, something like taking logs should have been used. Damn so much overflow :\

→ Reply

9 years ago, # ^ |

The only you need is to check whether if LONG_LONG_MAX/n<k you need to brake a cycle, where n is current power of k.

→ Reply

9 years ago, # ^ |

My solution with unsigned long long int fails :\ Another -1 so

→ Reply

urbanist

9 years ago, # ^ |

FFFFFFFFFUUUUUUUUUUUUUUUUU----------------

Arithmetic overflow is such a bitch....

It gets me every time...

→ Reply

urbanist

9 years ago, # ^ |

← Rev. 2 →

deleted

→ Reply

intptr

9 years ago, # |

Div2B pretest 9? how?

→ Reply

9 years ago, # ^ |

This one checked if your program could answer correctly the case where all numbers were beautiful

→ Reply

intptr

9 years ago, # ^ |

← Rev. 2 →

What?? There's always 1 non beautiful number..

→ Reply

AndrewB330

9 years ago, # ^ |

← Rev. 2 →

at least n - 1 beautiful numbers

→ Reply

9 years ago, # ^ |

some number of tanks of one country was removed from the game, hence the number of tanks of this country may not remain beautiful.

may may may may

it just guarantees for atleast n-1 beautiful numbers. never for atleast 1 non beautiful no

→ Reply

9 years ago, # ^ |

There is always one number subtracted from, but it might remain a beautiful number. Confusing, I know :P

→ Reply

dush1729

9 years ago, # ^ |

And here i was thinking i can hack some submissions because of this. -_-

→ Reply

savinov

9 years ago, # |

← Rev. 2 →

+12

There could be a lot of hacks on problem A if not third pretest(

→ Reply

I_love_Tanya_Romanova

9 years ago, # ^ |

+23

There could be a lot of hacks on every problem if not these good pretests :)

I think it was a bit cruel — to give samples which can be solved with "point-point" distance, without "point-segment". And at the same time there was no crazy hack fun...

→ Reply

urbanist

9 years ago, # ^ |

I figured out the point-segment thing with concave polygons after failing the 3rd pretest, but didn't have time to code it all...

Effing geometry.

→ Reply

P_Nyagolov

9 years ago, # |

I remember some people were joking about the difficulty of the problems before the contest... Anything to say? :P

→ Reply

jAckAL_1586

9 years ago, # |

Can anyone explain Div 2 C? My idea was to find the minimum distance from P to the polygon and the maximum distance and then pi*(max*max-min*min)

→ Reply

balalaika

9 years ago, # ^ |

I don't know correct solution, but yours fails at this test:

4 0 0
-1 -1
0 2
1 -1
0 1

→ Reply

jAckAL_1586

9 years ago, # ^ |

My idea was exactly similar to this comment Now I'm confused

→ Reply

Hacliker

9 years ago, # ^ |

You're wrong. The minimum distance doesn't have to be the distance from P to one of the point in the polygon.For example, for the test: 3 0 0 0 2 -1 1 1 1 The minimum distance is 1 while not sqrt(2).

→ Reply

shubham1694

9 years ago, # ^ |

Minimum distance doesn't always lie on vertices.

eg 3 2 -1

1 0

2 1

3 0

ans = pi*(4-1) = 3*pi.

→ Reply

jAckAL_1586

9 years ago, # ^ |

I handled that issue

→ Reply

shubham1694

9 years ago, # ^ |

Then maybe you didn't handle the finite line issue.

The min point must lie on the finite line segment.

If you just considered perpendicular distance from point p to line then you might fail some cases.

→ Reply

Bleuj

9 years ago, # ^ |

I also handled the issue and failed test 3 : maybe you forgot the edge between the first and last vertex.

→ Reply

Hacliker

9 years ago, # ^ |

Maybe your solution to find the minimum distance from a point to a segment has some bugs.

→ Reply

Bleuj

9 years ago, # ^ |

No I just added the last edge and it passed all tests :)

→ Reply

Hyperbolic

9 years ago, # |

I think this round is too difficult ....

→ Reply

akulsareen

9 years ago, # |

← Rev. 2 →

What is the intended approach for div 1 D?

The same question for a single query can be solved using dp on trees in linear time which led to me to come up with an approach which involved using HLD to compute dp at the bare minimum required nodes (klogk for each query I think) but the implementation was turning out to be too long so I went off to sleep instead.

→ Reply

Baba

9 years ago, # ^ |

You can first build the auxillary tree, which is a compressed tree of the marked nodes in O(klogN) time consisting of O(k) nodes and then apply the same dp on this tree in O(k). For implementation details on how to build the auxillary tree, refer my soln here

→ Reply

grv95

9 years ago, # |

+17

Div2 A should've been named Hack those overflows.

→ Reply

9 years ago, # |

My WA solution for div2 C was to compute minimum and maximum radius, find difference between circles and output. I specially handled the case in which all radii were the same(answer =0)

I claim that any radius between [minradius,maxradius] can be attained by some point in the polygon. Is this false?

→ Reply

Hyperbolic

9 years ago, # ^ |

3 0 0 -2 1 2 1 0 2

submit it

→ Reply

mingaleg

9 years ago, # |

Thanks for great div2A! 22 successful hacks are non penis canina. My hacks:

1 1000000000000000000 1000000000
1 1000000000000000000 536870912
1 1000000000000000000 536870913

536870912 = 2 ^ 29

→ Reply

9 years ago, # ^ |

Very good!

→ Reply

kobe24

9 years ago, # ^ |

second test case can be used to hack unsigned right , awesome

→ Reply

mingaleg

9 years ago, # ^ |

Yep, and the third one is the test, which generates overflowed long long less than 10^18 and greater than previous one.

→ Reply

ch_egor

9 years ago, # ^ |

← Rev. 2 →

In first redaction 1 ≤ k ≤ 10⁹ but we thought that it is big trap for Div2A.

→ Reply

tau0

9 years ago, # ^ |

Can you describe how do you find second and third tests?

→ Reply

DEGwer

9 years ago, # |

+13

Thank you for strong pretest for B!

→ Reply

9 years ago, # |

← Rev. 2 →

-32

I hate Div. 1 A. No interesting idea, just applying mathematical formulas and crying when wrong answer on pretest #3 shows up and then finding a typo in one of these formulas :'(

→ Reply

geniucos

9 years ago, # ^ |

← Rev. 2 →

+23

I agree div1A doesn't find its place in any contest it's a stupid problem.

→ Reply

9 years ago, # ^ |

But we struggled with it. It was for us.

→ Reply

I_love_Tanya_Romanova

9 years ago, # ^ |

I think this problem fits well in some ICPC-style contest. However, CF round is not ICPC :)

→ Reply

-XraY-

9 years ago, # ^ |

+14

I don't understand what you all are talking about. I see the only problem with it: some guys could use prewritten geometry and get accepted a little faster (several minutes). I haven't used it.

→ Reply

savinov

9 years ago, # ^ |

← Rev. 2 →

It is the great problem to have a lot of hacks/challenges :)

→ Reply

9 years ago, # ^ |

+13

I don't think it is a good idea to have an ugly problem for the sole purpose of allowing people to hack more

→ Reply

Stetsyk

9 years ago, # ^ |

+30

I just used the ternary search for each side of polygon

→ Reply

baal-hammon

9 years ago, # ^ |

same here but got TLE on test 37 :(

→ Reply

anveshi

9 years ago, # ^ |

Same here, but could not get AC during contest. Missed the line segment between 1st and last point :(. Code Link

→ Reply

9 years ago, # ^ |

I don't get it. Why your comment gets +28 while mine gets -32? Is there something wrong with my comment which doesn't meet Codeforces standards?

→ Reply

aid

9 years ago, # ^ |

By mathematical formulas you mean distance between points and distance between point and line? They are well known and quite easy. Actually, geometry problems are quite rare on codeforces, so it's good to have them sometimes.

→ Reply

9 years ago, # ^ |

'Well known' — yes. Quite easy? Well... (between points ok, that's easy, but I didn't remember the formula for the distance between a point and a line and I had to deduce it by myself)

Also there surely are many much better geometry problems than that.

→ Reply

9 years ago, # ^ |

We have this formula on the lesson in 8 form: abs(a*x0+b*y0+c)/sqrt(a^2+b^2) x0, y0 — point's coordinates

→ Reply

Xellos

9 years ago, # ^ |

There is an interesting, simple idea. However, there's also annoying geometry. If P was inside the polygon, though, it could've made an easy div1A without the annoying stuff.

→ Reply

abhishek007

9 years ago, # |

Any One Please tell me that is What is "Hacked".

After my submission I received a message that solution is hacked...

→ Reply

alibaba

9 years ago, # ^ |

← Rev. 2 →

This means another contestant has found a case when your program produce wrong output. In short, your solution is wrong.

→ Reply

balalaika

9 years ago, # ^ |

← Rev. 2 →

It means someone found bug in your solution and found test in which your code fails. So, your solution incorrect and you should find bug and resend solution.

→ Reply

Lvat2000

9 years ago, # |

← Rev. 2 →

Thank you for preparing such a contest like this!Although I don't pass Div.2 C,this contest is well! Thanks everyone!

→ Reply

9 years ago, # |

At this time tourist

→ Reply

codolove

9 years ago, # |

What is test case 9 in div2B?

→ Reply

9 years ago, # ^ |

Do this

10 10

→ Reply

codolove

9 years ago, # ^ |

My code gives correct answer for these test cases. still wa on test case 9. http://pastebin.com/rz7D6CKm

→ Reply

9 years ago, # ^ |

← Rev. 2 →

Your code doesn't give true answer. It gives 010. Answer 100

→ Reply

codolove

9 years ago, # ^ |

It gives 100 for me on my system.

→ Reply

Hacliker

9 years ago, # ^ |

Maybe you used 'cout' and 'printf' together,aren't you? When you use this ,please don't use 'ios::sync_with_stdio(false)'.

→ Reply

9 years ago, # ^ |

something like

10 10 10 10

→ Reply

Mid0

9 years ago, # ^ |

the number of the removed country is also beautiful .

try this : 10 10 10

→ Reply

Al.Cash

9 years ago, # |

← Rev. 2 →

+24

The only problem I liked from this set was Div1 D :(

→ Reply

-XraY-

9 years ago, # ^ |

Seriously? My code started working after the contest (on pretests) and it's 300 lines. I don't like it. Idea is simple: there is a stupid algorithm with time O(n+k). How to fit the queries? Just compress the graph to make it O(k) vertices. Or do you have another solution?

→ Reply

KAN

9 years ago, # ^ |

+33

I liked the problem D too.

My solution is slightly above 100 lines; the idea is to compute the answer in offline and to use maps with small-to-big optimization.

→ Reply

Petr

9 years ago, # ^ |

+71

And I just processed 64 queries at once using bitmasks :)

→ Reply

Al.Cash

9 years ago, # ^ |

← Rev. 2 →

+18

My solution is heavily based on LCA. We sort vertices from the query in the Euler order (it's computed in one of LCA implementations anyway). Then it's optimal to take consecutive vertices whose LCA has the largest depth and disconnect them by deleting their LCA. If LCA is also a selected vertex, we need to delete some of its children, also -1 case is handled here. The only difficulty is how to implement this idea in the best way, but anyhow it should be O((N + K)logN).

→ Reply

adamant

9 years ago, # ^ |

+25

What about div. 1 C? I know you enjoy palindromes :)

→ Reply

DmitriyH

9 years ago, # |

+19

Any idea in DIV2E/DIV1C?
There are no DP, right? Just only some tricky but easy-to-implement construction? :)

→ Reply

Edvard

9 years ago, # ^ |

← Rev. 2 →

+15

If we have two letters with odd a_i then the answer is 0. Otherwise the answer is g = gcd(a_i).

Let's build such string:

1) If all a_i is even then we can build a block of length $\text{[math]}$ with $\text{[math]}$ occurrences of the i-th letter (in any order). And then copy that block g - 1 times, each time reversing it. Easy to see that we will have exactly g palindromes (because g is even).

2) If we have some odd a_i then g is odd. So for each even a_i the value $\text{[math]}$ is also even. So we can build g identical palindrome blocks of the length $\text{[math]}$ , where the letter with odd a_i will be in the middle and all the letters will occur $\text{[math]}$ times.

It's not hard to prove that the answer can't be greater than g.

→ Reply

9 years ago, # |

+10

I don't like Div2B statement — take too much time to figure out that numbers could be very long etc etc. One of these tasks where statement reading takes the same (or more) time as solution finding and coding.

→ Reply

Khina

9 years ago, # |

+23

Authors at this moment...
system testing

→ Reply

9 years ago, # ^ |

We're sorry, because The Great Admin now in taxi and hurry to start system testing)

→ Reply

isurugieri

9 years ago, # |

← Rev. 3 →

When I read the problem statement of Div2.B at first, I could not understand.
By repeating to read the statement many times, I noticed that "find the product" stands for calculating $\text{[math]}$ , and then I could solve immediately.
By and large, the accounts for sample case are too short for me.

→ Reply

danilka.pro

9 years ago, # |

+27

Div1A is really great for Educational Round. Authors would do better by PM'ing Edvard with this task. I know that it's wrong, but I was badly confused about this right from the start of the contest.

→ Reply

9 years ago, # ^ |

Did you participate in Education Rounds with geometry problems? In the first one, half of solutions were hacked due to precision problems. In the second one, even the author solution had precision problems and they had to increase the error tolerance 1000 times. I think it is not a coincidence that there are no geometry problems in the last 3 Education Rounds. Too much work to get them right when your adversaries have 24 hours to find challenging cases. Unless you want to restrict coordinates to be less than 100 and set required precision to 1e-2.

→ Reply

9 years ago, # |

+22

Its very funny that participants who have 26 successful hacks on A failed A on system testing :)

→ Reply

gfonn

9 years ago, # ^ |

+10

Anyway, they earned a lot of hacking score (besides they didn't solve the A)

→ Reply

9 years ago, # |

+164

→ Reply

9 years ago, # ^ |

Is that Endagorion in the background?

Tourist fanboys everywhere -__-

→ Reply

ilya151098

9 years ago, # |

Super Contest, I got a lot of fun!!!!!!

→ Reply

9 years ago, # ^ |

And KPACUBO got a lot of fun!!!

→ Reply

Yura_Sultonov

9 years ago, # |

Look there, running code: here

→ Reply

9 years ago, # |

Why system testing stuck at 100% ?

→ Reply

9 years ago, # |

← Rev. 2 →

-25

Thanks to authors! : )

→ Reply

9 years ago, # |

Endagorion tomorrow published editorial, please wait...

→ Reply

9 years ago, # ^ |

and you will publish the announce 3 days ago

→ Reply

Mr.Awesome

9 years ago, # ^ |

← Rev. 2 →

Well it's tomorrow , still no editorial published

→ Reply

12121005

9 years ago, # |

div2 D. Skills what's the answer of 3 5 1 0 4 0 4 1

→ Reply

20171231

9 years ago, # |

← Rev. 4 →

Another test case for Div. 2 A:

9007199515875289 9007199515875289 94906267

→ Reply

the_art_of_war

9 years ago, # ^ |

K <= 10^9 but in your test is more

→ Reply

20171231

9 years ago, # ^ |

Sorry, I have replaced the big K with 94906267 (<= 10^9).

→ Reply

9 years ago, # |

← Rev. 2 →

My code working fine on my machine but failed system test for the same code. Working fine on custom invocation also.

→ Reply

9 years ago, # ^ |

I'm sorry to say there's no way that code's "working fine". You're getting an overflow error, checking that it doesn't become smaller isn't enough, as it can overflow into a bigger number.

For instance, consider numbers modulo 40, k = 4. The powers are 4, 16, 24. 24 is clearly wrong, but it's still higher than 16. Your code won't detect this kind of error.

What you could do is checking whether the division is sane: check that the next number divides the previous into k. That is, if pow[i] / pow[i-1] = k, then you know it's right.

→ Reply

9 years ago, # ^ |

Sorry I misread the Jury's output as mine and vice-versa, Thanks btw :)

→ Reply

9 years ago, # |

Don't know why it failed system test ? code

→ Reply

9 years ago, # ^ |

Looks almost perfect to me, maybe a bit overcomplicated. The problem seems to be you're forgetting the last return value on you function

bool check(string s);

which should be returning true at the end, if it doesn't catch one of the false conditions. It seems you got lucky and the undefined return value is usually true, but it's bound to be false sometime.

Here's a hint: this kind of mistake is something that can be detected by your compiler. Make sure you compile with warnings enabled! With g++ this is done with the flags:

g++ -Wall -Wextra -Werror

(Of course there's more warning flags, but these should do for most things)

→ Reply

9 years ago, # ^ |

Thanks got it :) Why I did this mistake

→ Reply

9 years ago, # ^ |

Do you know how to set these conditions in Sublime Text?

→ Reply

http://stackoverflow.com/questions/23789410/how-to-edit-sublime-text-build-settings http://stackoverflow.com/questions/22516094/sublime-text-compiler-build-options

9 years ago, # ^ |

→ Reply

dush1729

9 years ago, # |

Ratings Updated!

→ Reply

9 years ago, # ^ |

We have exactly similar ratings, fine)

→ Reply

pazoki

9 years ago, # |

-22

the worst contest I see in codeforces problem B was unclear

→ Reply

9 years ago, # ^ |

Can't agree with "worst", was quite well overall.

But Div2B is bad, I agree with that. Statement is over-complicated a lot.

→ Reply

9 years ago, # ^ |

As for me it was one of the best problems during last several rounds because it is the one i have just solved and only thanks to it i have become a "specialist") And it is the one you haven't solved (from what you have tried to solve), i know(

→ Reply

9 years ago, # ^ |

← Rev. 4 →

Congrats :)

Yea I've failed on that one — algo was correct, but I didn't checked all branches correctness. My failing case was where non-beautiful number comes before 0 in sequence, so I printed "nonbeautifulnumber0" instead of "0". After self-analysis I blame my bad emotions about problem statement — because of them I wasn't very concentrated when checking.

Besides that, its very easy problem. ProblemStatementComplexity > ProblemComplexity. I really hate these ones (and my hate is what caused these bad emotions) :)

→ Reply

Bleuj

9 years ago, # |

That moment when you realize you failed test 3 on Div2 C because you forgot the edge between the first vertex and the last one...

→ Reply

Elise

9 years ago, # |

+22

Div. 2 D is interesting except for asking the final value of the numbers, that adds nothing but boring and time consuming implementation.

→ Reply

9 years ago, # ^ |

I was thinking about and decided that it doesn't add a lot of code, and has some advantages.

Firstly, you can check participant's answer more precisely.

Secondly, you could detect [potential] situation when participant's solution is better than jury's one and report.

→ Reply

Elise

9 years ago, # ^ |

It's true a lot of lines of code aren't added but the logic behind them takes a lot of time to think and debug properly. It costed me 15 minutes to code it on top of the 30 minutes used to find the best value.

1º Indeed, but I still think the problem is already good without them, maybe just asking the minimun value and the number of maximum values used is enough.

2º That's not a job for contestants.

→ Reply

9 years ago, # ^ |

2) Yes, but first reason still applies =)

What about your idea to output a number of full skills and the minimum level I think it is too spoilerish, because allows to guess that the maximums can be taken greedily.

→ Reply

iamscrew

9 years ago, # |

Can anybody please help me where my div2 A problem is getting wrong. ?

Code link — http://ideone.com/EzXlNf

Input case : 1 999999999999999999 1000000000

My output : 1 1000000000 1000000000000000000

Correct output : 1 1000000000

→ Reply

Elise

9 years ago, # ^ |

← Rev. 2 →

You are using doubles for l and r, doubles have precision problems. It's probably representing 1000000000000000000 and 999999999999999999 as the same number.

You should store l and r in long long and use doubles to check possible overflow.

→ Reply

iamscrew

9 years ago, # ^ |

Ok thanks :)

→ Reply

bholagabbar

9 years ago, # |

Was long intended to fail the tests (Test 24) in Div 2 A in JAVA ? I changed my code to BigInteger and it passed.

I'm sure a lot of people used the method I did. All I did was preprocess the powers, store them in a TreeSet and print subSet(l, r+1) (which is an inbuilt method in JAVA TreeSet (similar to C++ std::set)) which prints all the elements in the range [l,r]. You can do this by adding it to a vector, then sorting etc, same thing.

I don't think these solutions should have failed. This is just my opinion. Here is the WA code and AC code.
Only changed Long to BigInteger, nothing else

→ Reply

9 years ago, # ^ |

You need to be clever if you use 64 bit ints (java long) in order to avoid overflow errors. Echoing a similar answer I already gave:

Checking that the numbers are in the correct range isn't enough, as they can overflow and land in the range again. For instance, consider numbers modulo 40, k = 4, and [l,r] = [3,25]. The powers are 4, 16, 24, etc. Since the third number should be 64, 24 is clearly wrong, but it's still in the [l,r] range so your program will print it out.

What you could do is checking whether the division is sane: check that the next number divides the previous into k. That is, if pow[i] / pow[i-1] = k, then you know it's right and you don't have overflow errors.

→ Reply

suhendry

9 years ago, # ^ |

This problem basically asks you to properly handle the overflow. If there exists an input which make your code fail, then your code should fail (no excuse).

You can deal with overflow problem without having to rely on BigInteger.

From your code, you only need to add one line before start *= k;

if ( start * k > LIMIT ) break;  // check overflow (LIMIT can be 10^18, or you can use 'r')
start *= k;

But wait, start * k can be overflow, can't it? Yes, so change it to this:

if ( start  > LIMIT / k ) break;
start *= k;

You don't need BigInteger at all.

→ Reply

eboy2914

9 years ago, # |

← Rev. 2 →

(http://imgur.com/JckabmD) Why is my output wrong?

→ Reply

9 years ago, # ^ |

That number is clearly not a power of k, and it's appearing due to overflow errors.

See http://mirror.codeforces.com/blog/entry/22726?#comment-272811 or http://mirror.codeforces.com/blog/entry/22726?#comment-272774 for a better explanation.

→ Reply

9 years ago, # |

Got WA in problem a, initially I was using long double, and I lost a lot of time because apparently codeforces wont work correctly with %Lf. So I switched to double, then I got WA because I needed long double precision. What was the point of div2 a? To get me not to use c++?

→ Reply

Grevozin

9 years ago, # |

Oh, I didn't know that Decimal in Python is so slow. TL56 on Div2 C :( And the same solution with the usual Float is correct.

→ Reply

9 years ago, # ^ |

Its not "decimal in python", its "python" itself who is slow :)

→ Reply

Grevozin

9 years ago, # ^ |

It is ok for the problems like Div2 A-C. I just mustn't be too greedy for precision in 2C=1A.

→ Reply

9 years ago, # ^ |

Well yea, I was using it before. But then I've failed to implement some solutions because it was 40 times slower than C#. So I've decided to switch.

And I believe two active languages is a bad idea for competitive — it is better to master one (there is a lot of cases to study, like overflows, reading 1e9 test inputs, etc etc).

→ Reply

merolish

9 years ago, # ^ |

On the bright side you got to hack my botched handling of vertical lines.

→ Reply

khrak

9 years ago, # |

Div2 problem A, good example how useful Biginteger can be.

→ Reply

9 years ago, # ^ |

BigInteger Will get TL, Muhaha.

→ Reply

-AKram-

9 years ago, # ^ |

it won't BigInteger submission

→ Reply

ChrisWu

9 years ago, # ^ |

log_k r BigInteger multiplications. That definitely wouldn't time out.

→ Reply

9 years ago, # ^ |

← Rev. 2 →

Not sure about C++, but in C# we have "decimal" type which can store up to 28-29 digits (basically it is int128 with "floating point position").

I also have another somewhere interesting solution for C#:

Do all the math on regular long type (int64) inside the "checked { }" block which force compiler to check all math operations for overflow. If got an exception -> break cycle.

→ Reply

toraoh

9 years ago, # ^ |

Cool solution!

Also, there's BigInteger in C# (in System.Numerics), which is also fast (in such small case).

To Java Users : ...... and easier to write. 15385528

→ Reply

leonidvasilyev

9 years ago, # ^ |

I think It's fair to say that decimal can be used more like int97 or unsigned int96 rather than int128. Because mantissa is only 96 bits plus 1 sign bit.

→ Reply

Edvard

9 years ago, # |

+39

Typical GNU C++:

pair<int, int> s = pair<long double, long double> (13.3, 14.4);
cerr << s.first << ' ' << s.second << endl;

No warnings.

if (rand() % 10 < a.size()) puts("0");

naive.cpp: In function ‘int main()’: naive.cpp:92:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (rand() % 10 < a.size()) puts("0");

→ Reply

Gassa

9 years ago, # ^ |

Sad but logical.

With floating point types being silently and implicitly converted to integers all the way in the history of C/C++, it is only logical to extend this property to simple aggregate types as well. So, no warning, as in int x = 4.59;.

Regarding rand() % 10, there is no way to tell that the result of int rand() is actually non-negative, except if we go and analyze the source of function rand(). In the general case, it would be impossible for a compiler to do (with halting problem as a subproblem). Why rand() returns int and not unsigned is however a good question — why, indeed?

And the problem the compiler warns about gets quite real with if (rand() % 10 - 10 < a.size()) when the part rand() % 10 - 10 is converted to unsigned (~4 billion) before comparison takes place.

→ Reply

Edvard

9 years ago, # ^ |

I don't understand why this get warning:

int ans2 = (long double) (10 + rand());
cerr << ans << endl;

naive.cpp: In function ‘int main()’: naive.cpp:85:38: warning: conversion to ‘int’ from ‘long double’ may alter its value [-Wconversion] int ans = (long double) (10 + rand());

but conversion for pair<long double, long double> don't. My solution for A fails today because of that.

And about comparing of signed and unsigned values. Why it can't compare them in the following way: if signed value is negative then we know answer, otherwise compare them in unsigned type?

→ Reply

Gassa

9 years ago, # ^ |

Oh, there's -Wconversion which is not covered by -Wall or -Wextra. Didn't remember that, sorry!

Now that's actually strange. In my hand-rolled implementation of pair <T1, T2> (version 1, version 2), such usage does trigger a warning with -Wconversion right where it should. Perhaps the library authors do something more clever, or, theoretically, not detecting the warning in the library code might be a compiler bug.

→ Reply

Gassa

9 years ago, # ^ |

Regarding comparison of signed to unsigned, that would be a really clever move if there was a processor instruction to do exactly that. Looks like that's not the case, and the alternative is to issue a branch instruction, which may be an expensive operation on a modern PC. And C/C++ compilers usually produce efficient (while not necessarily intended) code by default.

Also, legacy software may depend on the current documented behavior.

→ Reply

binary_eagle

9 years ago, # |

Not knowing how to know when overflow will occur in power costed me getting to expert. Oh well, atleast I learnt something today. :)

→ Reply

BadSector

9 years ago, # |

Can someone tell me which edge case did I miss for DIV2B ? http://mirror.codeforces.com/contest/614/submission/15367847

→ Reply

9 years ago, # ^ |

← Rev. 3 →

It seems your code fails for such a non-beautiful number:

100005

Its start from '1' AND have zeroes. So you count these zeroes towards the final answer, but also printing the number as it is. So 4 more zeroes than necessary.

→ Reply

habib_rahman

9 years ago, # |

← Rev. 2 →

-18

Picture removed.

→ Reply

9 years ago, # ^ |

Please don't take it personally but honestly speaking I don't like this picture. A national flag is the symbol of independence and sovereignty of a country. Inappropriate uses of a national flag is not appreciable. May be you didn't do it purposely. But you should know that we can't disrespect our country by using our national flag inappropriately. As a Bangladeshi, my request is please remove this picture. It hurts my feelings. I don't want to see a big hole and some stripes on our flag.

→ Reply

suhendry

9 years ago, # ^ |

I'm not sure with the question, but I guess, the answer is yes.

I also fell for the notorious test case #3. My solution was: find the furthest and closest point among the N given points to P. Apparently the "among the N given points" part is wrong. The closest point is not necessarily one of the N points.

consider this case: 3 0 0 -1 1 1 1 0 2

The closest point is (0, 1) which is not among the 3 points in input.

→ Reply

CodeTamer

9 years ago, # |

So where is the tutorial ?

→ Reply

9 years ago, # ^ |

They said it will be posted tomorrow.

→ Reply

shuboy2014

9 years ago, # |

can anyone tell me what is the logic behind div2 B ?

→ Reply

suhendry

9 years ago, # ^ |

The beautiful number are in the form of 1, 10, 100, 1000, 10000, ..., and there is at most one non beautiful number. So you only need to print the non-beautiful number, followed by as many zeroes as there can be. However, you should be careful with the case where there is zero or no non-beautiful number.

→ Reply

Your text to link here...

9 years ago, # |

+10

WOW!!! We have 9 Legendary grandmaster now!!! :D

→ Reply

tsiki

9 years ago, # ^ |

There were only 5 after the rating changes if I remember correctly. I wonder what happened, wasn't the new system supposed to counter rank inflation?

→ Reply

matthew99

9 years ago, # |

← Rev. 2 →

+31

I passed the pretest of problem D with a little issue, and I skipped my old solution and lost 145 points when I found the issue. But when I submitted my old solution today I just surprisingly found it pass the system test.

This is the correct one. Just press "compare" to view the old code and the obvious issue.

→ Reply

checkMate09

9 years ago, # |

-6

It seems that the contest will be with no Editorial :(

→ Reply

9 years ago, # ^ |

→ Reply

F202130100

9 years ago, # |

NICE

→ Reply

Al.Cash

9 years ago, # |

That moment when you realise that E is solvable faster than all other problems (except A). :(

Just because there's no different cases and the most complex operation is modular plus.

→ Reply

inactive06

9 years ago, # |

+90

→ Reply

ironp

9 years ago, # |

hello, have a question: is double on the system a single-precision float? because i believe my solution of the problem C of DIV-2 was correct and on my computer i had correct outputs and apparently on the system it has output different answers.

→ Reply

9 years ago, # ^ |

No. I don't know any system where double has a single precision.

→ Reply

9 years ago, # ^ |

Use %lld to read numbers.

→ Reply

Ahmad1

9 years ago, # |

← Rev. 2 →

I think problem A is one of the most Hacked problems on Codeforces.

I hacked 11 and an other 15 solutions failed system test .

every one will know how to handle overflow after this contest :D .

→ Reply

mistiri

9 years ago, # |

+31

just another way to describe div-2 A

→ Reply

sazerterus25

9 years ago, # ^ |

how did you do in the contest? I am surprised that you found time. Syllabus finished?

→ Reply

saurabhgoyal

9 years ago, # |

I am getting wrong answer on Case 56 for Div2 C . i used ternary search.. Can someone please help ???

→ Reply