CodeCraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined)

7 years ago, # ^ |

You are right, it has been fixed. Thanks.

→ Reply

soohotiam

7 years ago, # |

← Rev. 2 →

-53

Only 20 T-Shirts. Please added High School Programmer Quote :'(. For Prizes

→ Reply

Mr_Emrul

7 years ago, # |

Please update the duration in contest tab! I am seeing 2 hours there!

→ Reply

RohanRTiwari

7 years ago, # ^ |

Yes, it will be updated soon. Thanks for pointing out!

→ Reply

7 years ago, # |

Auto comment: topic has been updated by Superty (previous revision, new revision, compare).

→ Reply

7 years ago, # |

Why is it not on the home tab yet?

→ Reply

RohanRTiwari

7 years ago, # ^ |

It will attached to the home page soon after today's contest is over.

→ Reply

shubhiks1032

7 years ago, # |

← Rev. 2 →

-55

Hope for even amount of geometry and math problems.

→ Reply

7 years ago, # ^ |

-28

(additional info) Last year there was only 1 math problem and no geometry problem.

→ Reply

ContestDestroyer

7 years ago, # ^ |

why not odd amount?

→ Reply

below_6

7 years ago, # |

r_ _ _ _???

→ Reply

ContestDestroyer

7 years ago, # ^ |

+25

Round 458, sir!

→ Reply

7 years ago, # |

Auto comment: topic has been updated by Superty (previous revision, new revision, compare).

→ Reply

Alireza

7 years ago, # |

+45

I know it is very hard to prepare a contest and we are so thankful about that, but dear authors please double check your solutions. We all prefer not to have 2 consecutive unrated rounds!

→ Reply

aloo123

7 years ago, # |

Are there any prizes for school students in India

→ Reply

ista2000

7 years ago, # ^ |

Dont think so.

→ Reply

ghoshsai5000

7 years ago, # |

Will the Project-Euler style contest be conducted on CodeForces ?

→ Reply

phpduke

7 years ago, # ^ |

← Rev. 3 →

+38

No. Gordian Knot will be hosted on Felicity's site on 25th for 24 hours.
You can see other technical events here.

→ Reply

akumar1503

7 years ago, # |

Expecting 10,000 registrations.

→ Reply

KAMA3

7 years ago, # ^ |

-26

Expecting al of them will be worse then me

→ Reply

I_LOVE_METSUKA

7 years ago, # ^ |

-16

HAHAHAHAHA

→ Reply

MiNus239

7 years ago, # |

Good luck! Have fun! xD

→ Reply

Oblivi0n

7 years ago, # |

Clashes with COCI

→ Reply

shahidul_brur

7 years ago, # |

← Rev. 2 →

+39

Here are some past codecraft contests:

2017: Contest, and Editorial

2016: GYM, and Editorial

2015: Contest: GYM, Replay on codechef and Editorial

2014: Replay on codechef

→ Reply

noelnadal

7 years ago, # |

+13

I wonder, is there any reason why you are not giving T-Shirts to random participants like last year's contest?

→ Reply

KAMA3

7 years ago, # |

Its time tu up my reting. Good luk to me

→ Reply

kunalsojatia

7 years ago, # |

-38

→ Reply

HOMIARA_RUBY

7 years ago, # ^ |

+19

It works.. why? probably to be hacked.

→ Reply

21August

7 years ago, # |

-37

So many indians, its their chance to prove that they can be good problem setters.

→ Reply

DoomzGay

7 years ago, # ^ |

-29

(nope)

→ Reply

_HossamYehia_

7 years ago, # |

+21

I hope one day i will get a T-shirt from Codeforces. that will be the best recognition of my hard work.

→ Reply

ista2000

7 years ago, # ^ |

Yeah, they are rare af! :O

→ Reply

_HossamYehia_

7 years ago, # ^ |

Yeah , but i will get it one day

→ Reply

Swistakk

7 years ago, # |

+68

Will the drain be adjusted, please?

→ Reply

MikeMirzayanov

7 years ago, # ^ |

+44

Yes!

→ Reply

Sigyn

7 years ago, # |

+11

"The scoring distribution will be announced later" ... ?

→ Reply

BaaaaaaaaaaaaaaarkingDog

7 years ago, # |

← Rev. 2 →

-59

In Problem B, Is there any problem in range of a[i]? check my submission please.

→ Reply

BaaaaaaaaaaaaaaarkingDog

7 years ago, # ^ |

-37

Sorry, my poor mistake.

→ Reply

sagarthecoder2

7 years ago, # |

-83

problem A: Sample test 2; How 576 is a perfect square????

→ Reply

7 years ago, # ^ |

+33

Please do not discuss

→ Reply

7 years ago, # ^ |

24 * 24 = 576

→ Reply

BagishovMikail

7 years ago, # ^ |

-13

"24 * 24 = 576" isn't simpler than "576 is square")

→ Reply

7 years ago, # |

+12

Can't hack solutions , it keeps on loading

→ Reply

M_H_H_7

7 years ago, # |

-9

what a hard contest!!

→ Reply

yaswanth

7 years ago, # |

-8

Getting runtime errors on pretest 1 with no error specified for problem C. Can the admin please help? It runs fine on my machine.

→ Reply

AsleepAdhyyan

7 years ago, # ^ |

same thing happened to me. you are probably using a different compiler. try using custom invocation option. In my case i was using negative indices

→ Reply

sagarthecoder2

7 years ago, # |

-95

May be another unrated contest is running..............................

→ Reply

M_H_H_7

7 years ago, # ^ |

-76

i think they have to unrated the contest because of problem H :D

→ Reply

orlon.

7 years ago, # |

+49

Even though I performed miserably in this round, I must admit this round was pretty neat as the problems were good. Good job!

→ Reply

alisfr32

7 years ago, # |

-97

this round should be unrated because of problem H like yesterday contest

→ Reply

WolfBlue

7 years ago, # ^ |

+10

I think that, because almost nobody even attempts H, the round should still be rated.

→ Reply

HOMIARA_RUBY

7 years ago, # ^ |

You are talking about 'H'; not 'A' or 'B'. As if you have stood 2nd because of this mistake.

→ Reply

Storm__Spirit

7 years ago, # |

+16

I'm mentioned in problem H!

→ Reply

7 years ago, # |

← Rev. 2 →

-32

waiting for notification, when they say , round is "UNRATED " :P

C problem,,, looks interesting :P ...

→ Reply

Amaryllis

7 years ago, # |

-7

Is $\text{[math]}$ fast enough for D ?

→ Reply

walnutwaldo20

7 years ago, # ^ |

You need $\text{[math]}$ .

$\text{[math]}$ .

→ Reply

killer_god

7 years ago, # ^ |

it might just pass if your constant is very small but unlikely.

→ Reply

7 years ago, # |

How to solve C and D?

→ Reply

Len

7 years ago, # ^ |

C digit dp.
D answer is yes if there is <= 1 numbers that isn't divisible by X.

→ Reply

7 years ago, # ^ |

How to find that for D?

→ Reply

arif.ozturk

7 years ago, # ^ |

+46

Make a segment tree where you keep the gcd in each node. A query will point to multiple nodes and you'll pick the only one not divisible by X(if there are more, there is no solution). This node has either 1 or 2 sons with a value not divisible by X. If both values are not divisible by X you have no solution, otherwise just go to the node that isn't divisible by X.

→ Reply

7 years ago, # ^ |

Can you share your code for D?

→ Reply

Phanix

7 years ago, # ^ |

Your solution to D did not timeout?

→ Reply

BaaaaaaaaaaaaaaarkingDog

7 years ago, # ^ |

C : once you apply operation to N, it must less than or equal 1000. So you just have to pre-calculate k-value for 1 to 1000

→ Reply

7 years ago, # ^ |

C is a DP. cases k = 0, 1 are easy. k = 2, 3, 4. needs a DP., rest k's are 0.

→ Reply

7 years ago, # ^ |

I think C pretests are weak. it doesn't have any test case with k = 1?

just now i noticed a problem with my k = 1. I output s.size() instead of s.size() - 1

→ Reply

dioji

7 years ago, # |

+11

Was a N * log(N) + Q * log(N) * log(N) solution supposed to pass D?

→ Reply

ajecc

7 years ago, # ^ |

+12

yes

→ Reply

dioji

7 years ago, # ^ |

mine didn't :(

→ Reply

mochii

7 years ago, # ^ |

I think so, at least pretests, i was able to pass pretests with this complexity.

→ Reply

mochii

7 years ago, # ^ |

Passed systest =)

→ Reply

walnutwaldo20

7 years ago, # ^ |

No. That is what I originally did. You need $\text{[math]}$ .

→ Reply

ajecc

7 years ago, # ^ |

I passed the pretests with a solution that i think is slower that Q log^2 N. Maybe i overestimated my complexity, or you implemented something slower than that.

→ Reply

zscoder

7 years ago, # |

+73

That moment when you realize your C will fail 4 mins before contest end after locking it.

→ Reply

7 years ago, # ^ |

me too, for k = 1? or something else for you?

→ Reply

zscoder

7 years ago, # ^ |

k = 1. Used it to get 3 blind successful hacks in the end but still RIP rank.

→ Reply

7 years ago, # ^ |

such a bad way to fail a problem :(

→ Reply

7 years ago, # ^ |

Exactly same thing happened to me. So, in the last 2-3 mins, I just put that hacks in other's code. Didn't read them so got 2 unsuccessful hacks as well with 4 successful ones xD

→ Reply

7 years ago, # ^ |

In my opinion, they should have had k=1 in test case. its not something at the core of this problem. .. but maybe that's my defeated soul consoling me..

→ Reply

kobortor

7 years ago, # ^ |

Haha, I used K = 1 to hack someone else before I realized my code would fail the case too.

→ Reply

_QWOiNYUIVMPFSBKLiGSMAP_

7 years ago, # ^ |

why if k==0 the answer should be 1 ?

→ Reply

7 years ago, # ^ |

because only 1 needs 0 steps to make it equal to 1

→ Reply

7 years ago, # |

Is E divide and conquer? If yes, how to merge the answer of 2 sub-trees efficiently?

→ Reply

Len

7 years ago, # ^ |

Maintaining mask of letters will work I think.

→ Reply

7 years ago, # ^ |

Thank you. Oh! I see, you just iterate through 0^mask, 0b1^mask, 0b10^mask, 0b100^mask... right? Now the complexity is some O(26n). Ahhhh...

→ Reply

7 years ago, # ^ |

Can u explain a bit more?

→ Reply

7 years ago, # ^ |

I haven't solved it yet. Here's how I want to merge sub-trees. So use a 26 bit mask to represent the odd/even of letters on the paths that ends at the current node under analysis u.

If 2 paths p1, p2 ending at u can be connected and form a palindrome path, p1 - u - p2, then, if you xor the mask of p1 and p2, either the resulting mask has only 1 bit set or all bits are 0.

→ Reply

7 years ago, # ^ |

There's only 20 letters, [a, t]. Very important.

→ Reply

7 years ago, # ^ |

Oh thanks, I didn't notice that...

→ Reply

7 years ago, # ^ |

What if there is a path p1 ending at u which has mask something like ....000011 and p2 has mask .....000010 so in that case we won't be counting p1?

→ Reply

7 years ago, # ^ |

Since 000011 ^ 000010 = 000001, there's only 1 bit... So p1-u-p2 should also be counted in this case...

→ Reply

7 years ago, # ^ |

But u r not storing the bits except for 00001,00010,00100,01000,10000 for each node right?

→ Reply

7 years ago, # ^ |

← Rev. 2 →

so...in my opinion, u will store all possible masks. since the number of these masks is at most O(n) (# of paths to u from sub-trees), it is acceptable.

→ Reply

pk842

7 years ago, # ^ |

I have a doubt. In a subtree there can be atmost N possible masks and when we are merging we have iterate on them. So, isn't the complexity is O(N^2)?

→ Reply

7 years ago, # ^ |

The solution should be a little bit different from dfs, by exploiting the information about the size of sub-trees (centroid decomposition, you may refer to the editorial).

→ Reply

pk842

7 years ago, # ^ |

thanks! i didn't know that it is out.

→ Reply

madn

7 years ago, # |

Must D be done faster than Qlog^2 or is my segtree implementation just bad?

→ Reply

oToToT

7 years ago, # ^ |

← Rev. 2 →

I do that O(Q log^2 * gcd) with some optimization, and it runs about 2s. (Hope I can pass the system test)

However, I think the ideal solution may runs in O(Q log * gcd).

→ Reply

7 years ago, # ^ |

My Qlog^2 solution ran pretests in 1092ms

→ Reply

7 years ago, # ^ |

← Rev. 2 →

It's possible to implement query() in O(log n) and update() in O(log n * gcd). I think that's the fastest.

→ Reply

oToToT

7 years ago, # ^ |

How does that work? I use a segment tree and binary search.

Also, I use the pragma to optimize my code, but it still runs in 2s.

→ Reply

7 years ago, # ^ |

← Rev. 3 →

This is my solution:

Keep a segment tree of gcd()s.

The query is basically "Is there more than 1 value in this interval, which isn't divisible by X?". You can check it by finding the leftmost and rightmost "bad" index; if they're the same, then there's only 1 bad value.

Yeah, you can binary search this, but that's not very fast. The segment tree query will produce O(log n) nodes that cover your query interval. Then, you can iterate over them from the left, and when you find one whose (already calculated) gcd is bad, you can locate the leftmost "bad" index in O(log n), by deciding to either go left or right in each layer of the tree. The same thing can be done from the right to the left side, again performing at most one O(log n) traversal.

Update: O(log n * gcd) Query: O(log n)

(During the contest, I was too lazy to code this, so my query was O(log n * gcd))

→ Reply

posij118

7 years ago, # ^ |

Simple implementation of an update actually works in O(log n + gcd).

Idea: After each two steps of the Euclid's algorithm, both numbers will be less than half of the original ones. Therefore, the number of steps is bounded by 2*max{a_i}.

(This should explain faster than expected running times.)

→ Reply

7 years ago, # ^ |

That's pretty much what I did.

For the queried range, I divided it into 2 parts and recursively went down the segment tree, until reaching a segment of size 1. If during the search, both parts had a gcd not divisible by the guess, that meant, it's wrong. Otherwise I chose the wrong part (if any) for continuation of the search,

You can check my submission if you want to see it more clearly.

→ Reply

7 years ago, # |

How could you solve C?

→ Reply

ouch__casquinha

7 years ago, # ^ |

-13

baktrak binomial newtom

→ Reply

WildUtah

7 years ago, # |

Hacking says that my version of Flash is too low to run. I am running the Flash that came with the latest version of Chrome.

→ Reply

Omar_Morsi

7 years ago, # ^ |

Same here

→ Reply

7 years ago, # |

For B : Hack Case is

5 1 1 1 2 2

→ Reply

7 years ago, # |

What was the hack Case for A ?

→ Reply

7 years ago, # ^ |

I used this one..

5 0 0 0 0 -5

→ Reply

Shayan.P

7 years ago, # |

by a mistake I resubmitted for problem A near the end of the contest and so I got two hundred instead of 490 which was my initial score is there any way for me to get my initial score?

→ Reply

kingofbugs

7 years ago, # ^ |

Nope

→ Reply

Jynx

7 years ago, # |

what are the hack cases for C ?

→ Reply

7 years ago, # ^ |

111 1

If you don't write an if() you'll print 3 instead of 2.

→ Reply

Jynx

7 years ago, # ^ |

I bruteforced for values less than 1000 Maybe mine fill fail on larger values when k == 1

→ Reply

Syloviaely

7 years ago, # |

Why the third sample input of H is 36?

I think 1 2 3 and 3 2 1 just have a single way to modify. QwQ

→ Reply

7 years ago, # ^ |

For 1 2 3, you can flip 3 or negate 2 3. For 3 2 1, you can flip 2 1 or negate 1.

→ Reply

Syloviaely

7 years ago, # ^ |

+10

Oh, that's my mistake.. thanks a lot

→ Reply

animeshf

7 years ago, # |

+394

Problem G submission by rajat1603 LOL

→ Reply

sggutier

7 years ago, # |

+14

How did you guys hack problem C?

→ Reply

7 years ago, # ^ |

k = 1, you're supposed to print len(n) — 1

→ Reply

rajat1603

7 years ago, # |

+46

I Hope F is better than $\text{[math]}$

→ Reply

radoslav11

7 years ago, # ^ |

+13

Bitset is better than everything!

→ Reply

halyavin

7 years ago, # ^ |

I see O(N²) solutions with bit masks at the top.

→ Reply

Baba

7 years ago, # ^ |

← Rev. 2 →

+12

I think it can be done in O((N + Q) * rootN) by keeping a suffix tree over each block of sqrtN. Not sure though, got confused with the implementation details.

→ Reply

ko_osaga

7 years ago, # ^ |

← Rev. 2 →

+57

Me : How to solve F?

Some red guy : Do kmp 7000 times

Me : That's obvious, but it won't run in time

Some red guy : Why not, CF is super fast

Me : (facepalm)

→ Reply

i4gotmylunchih

7 years ago, # |

I know it is O(n^3) but why does it get wrong answer on C: code

→ Reply

Amaryllis

7 years ago, # ^ |

K = 0 in test 4, if that is of any help.

→ Reply

Jynx

7 years ago, # ^ |

1111 0 ans is 1 your ouput is 4

→ Reply

i4gotmylunchih

7 years ago, # ^ |

understand now, thanks

→ Reply

Alireza

7 years ago, # |

+54

I really enjoyed the problemset especially the tricky ones. Thank you guys!

→ Reply

_Mugiwara_

7 years ago, # |

← Rev. 2 →

+67

2 — 1 in last min!!

→ Reply

7 years ago, # |

During contest I tried to hack 2 solutions with the test "1 -64". However they both gave unsuccessful verdict. So I copied their code by hand, put it into codeforces compiler and it gave WA! Images: https://imgur.com/a/NrhKb. However, now I put their original codes and it gives correct answer! Could anyone please tell me the difference between their original code and my copies that could cause this? Code1 Code2

→ Reply

7 years ago, # ^ |

Your manual copies look same to the original codes. So, only difference could be the choice of compiler but then I have no idea how would that produce different results.

→ Reply

7 years ago, # ^ |

I tried both C++11 and C++14

→ Reply

vintage_Vlad_Makeev

7 years ago, # ^ |

Could you please tell ids of hacks?

→ Reply

7 years ago, # ^ |

403017 and 403242

→ Reply

vintage_Vlad_Makeev

7 years ago, # ^ |

← Rev. 2 →

Seems like it's some kind of undefined behavior.

Reference

C++ guarantees only that domain error will occur in case of negative x and nothing about return value.

→ Reply

7 years ago, # ^ |

Damn :( I thought since it's the same compiler, the undefined behavior would be the similar. Anyways, thx for clarifying it to me.

→ Reply

7 years ago, # ^ |

I checked C++14 and 11 gives INT_MIN while c++ 5.6.1 gives -64. (at custom test)

→ Reply

Rafbill

7 years ago, # |

+47

"A path in the tree is said to be palindromic if at least one permutation of the labels in the path is a palindrome."

Is there any reason to call the special paths in problem E palindromic when the obvious notion of palindromic path is different ? I only noticed the different definition 30 minutes before the end of the contest...

→ Reply

Errichto

7 years ago, # ^ |

+40

And it didn't help that the first sample didn't distinguish that. :(

→ Reply

sansae

7 years ago, # |

Anybody knows pretest 5 in problem C? Maybe k=5?

→ Reply

Kalyan9981

7 years ago, # |

← Rev. 3 →

-84

lol

→ Reply

sansae

7 years ago, # ^ |

-8

Lul

→ Reply

this is the list of the special numbers

7 years ago, # |

← Rev. 5 →

-12

For C problem, I have doubt, pls someone help me...

question is saying that ,,

He calls a number special if the minimum number of operations to reduce it to 1 is k. ****

so , for the second test case,,,input is like

111111011

when I convert binary to integer,,, value is 507,,,

from 1, 507, there are 498 special numbers according to definition of the 'special number'...

then how come answer is 169 ... ( I know answer is 169 for EXACTLY K steps ) ...

I spent whole lot of time on C ,,, could have done D though :| ...

This is my brute force, code,,,

code is here

( this is the code to generate and check special numbers , it takes string(s) and integer(k) as input, and converts binary string to integer value(n) , and then iterates from 1 to n, and for each i check whether it's special number or not )

→ Reply

7 years ago, # ^ |

Yes, the statement did confuse me a lot, but here "exactly" is same as minimum number of operations as he any further operations is a wasteful activity on 1.

→ Reply

sdnr1

7 years ago, # ^ |

The problem statement actually means that the minimum number of operations to reduce it to 1 is "exactly" k. Minimum number was mentioned in the statement with respect to the operations needed. Although this is bad on the part of the statement writer since this creates doubt as mentioned by you because the operations needed for a number are fixed and there is no need to minimise the operations. I was also stuck at this for quite a lot of time during the contest.

→ Reply

7 years ago, # ^ |

Maybe they didn't want to tell us that the number of operations was fixed, on purpose, so that we have to figure it out ourselves.

→ Reply

7 years ago, # ^ |

← Rev. 2 →

well, next time just give input and output, and we will figure out everything ourself...

This is ridiculous, I had finished my C quesiton code in just 30-40 minutes,,, and then I was debugging that code for 1 hour,,, then decided to write bruteforce,,, and finally understood that it's "**exactly K**"

Moreover, we can't make any assumptions ,,,

in case you want to see my code for C question(considering minimum k)

code for minimum k steps

→ Reply

7 years ago, # ^ |

← Rev. 2 →

-16

He calls a number special if the minimum number of operations to reduce it to 1 is k.

The word minimum in the above statement changes entire meaning ...

Now, don't try to fool yourself, and tell me that,,, I should look at the test case and then understand by myself,,,

I know life is not fair,,, but I had my faith in codeforces, why you do this :( ???

(JK)

→ Reply

7 years ago, # ^ |

Acctually the number of operations is not fixed because you can keep aplying the operation to number 1 any number of times. So by saying minimum they mean you cannot do that I believe

→ Reply

jisan047

7 years ago, # |

Another Hacking round. It seems to be a hacking contest, not a programming contest.

→ Reply

vijju123

7 years ago, # ^ |

← Rev. 4 →

Cant be worse than me tbh. Solved B, it got hacked. I was like "Yeah, easy fix. Done. No more bugs now." Re-submitted, got accepted, immediately locked and...hacked again XD.

Lesson: Dont hurry for few points, take time and think over the problem. In the end, thats true- we get hacked because we did mistakes.

(Anyway, getting hacked> failing systest so...:p )

→ Reply

7 years ago, # ^ |

← Rev. 2 →

+17

Why don't you like hacks? maybe it is just because you can't hack?

→ Reply

jisan047

7 years ago, # ^ |

I can but I think to solve the problem is the matter.

→ Reply

7 years ago, # ^ |

I thiNk that hacking (finding mistakes) is helpful because you learn how not to make your own mistakes.

Also I solved 3 problems, but the duration of round is 3 hours, so hacking is a good way to waste your own time.

→ Reply

vintage_Grigory_Reznikov

7 years ago, # ^ |

+10

I can, still my opinion is that making three easily hackable problems is not a fine choice for a combined round.

→ Reply

7 years ago, # ^ |

← Rev. 2 →

i think it is fine.

→ Reply

7 years ago, # |

+10

please stop systests at this point! haha joke

→ Reply

DenXman111

7 years ago, # |

+73

→ Reply

neko_nyaaaaaaaaaaaaaaaaa

7 years ago, # |

→ Reply

seif__

7 years ago, # ^ |

i'm so curious for the hack case do you know it ?

→ Reply

7 years ago, # ^ |

5 0 0 1 1 1

5 0 0 0 1 1

might work.

→ Reply

neko_nyaaaaaaaaaaaaaaaaa

7 years ago, # ^ |

You can check out others' solutions to see where you got wrong. The person who hacked you maybe?

I think that's better than asking for the specific test case, because your algorithm is likely to be already incorrect anyway :p

→ Reply

7 years ago, # |

+32

So much failed system tests on C

→ Reply

7 years ago, # ^ |

pretty bad pretests if you ask me..

→ Reply

chemthan

7 years ago, # ^ |

+113

Actually, I guess that is intended. It makes contest worse not funner.

→ Reply

Z0RR0

7 years ago, # ^ |

Exactly. One can get AC after a few minutes with 1/2 additional penalty. But after system test, BOOM, you dropped down by a huge margin for some silly coding error or corner case misses which could have been easily found.

→ Reply

Denton

7 years ago, # ^ |

+12

If pretests will include every case, why have them?

→ Reply

Zeus726

7 years ago, # |

A good good good contest :) but too bad for me, solving E and not get acc from it just because of my poor coding skills ... :( feel so upset ...

→ Reply

Ali_Adelkhah

7 years ago, # |

+33

if(k == 1){ res--; } and only becaus of this i lost 850 point :(

→ Reply

Usu

7 years ago, # |

That moment when you got TLE on test 105 problem C... I should change my profile photo...

→ Reply

MazzForces

7 years ago, # |

← Rev. 2 →

-12

This k=1 case where most solutions count 1 and still get pretest pass is a full killer. I doubt I will be able to find such a corner case ever in my life by myself.

→ Reply

ZaakDov

7 years ago, # |

Is there some easy solution for problemE rather than DP on tree with bitmask?

→ Reply

ZaakDov

7 years ago, # ^ |

I type code slowly, so there seems not enough time for me. So I wish to know some simple implemented solution, thanks!

→ Reply

mochow

7 years ago, # ^ |

If you only consider the Centroid Decomposition solution easier, then yes.

→ Reply

Deathly_Hallows

7 years ago, # |

How to solve F ?

i see that most of the people who solved it used bitset so is it a known algorithm ?

→ Reply

7 years ago, # ^ |

It's brute-force. O(N^2 / 64)

→ Reply

Deathly_Hallows

7 years ago, # ^ |

← Rev. 2 →

how ? if you did it with complete brute force it will be larger than N^2

→ Reply

ngfam

7 years ago, # |

← Rev. 2 →

Am i the only one solved E with DSU on tree? I was afraid that my solution is wrong cause it run so f*cking fast.

UPD : I tried to choose a random root. And it's even faster now.

→ Reply

Zeus726

7 years ago, # ^ |

no some others use this approach like me :)

also Arpa use this too ...

→ Reply

ngfam

7 years ago, # ^ |

But still, my solution is much faster than Arpa's. I don't even know why.

→ Reply

Zeus726

7 years ago, # ^ |

lol ... you're right ... :)

→ Reply

enogseh

7 years ago, # ^ |

how did u solve it with Dsu on tree?

can u explain your approach ? :)

→ Reply

ngfam

7 years ago, # ^ |

← Rev. 2 →

Let's choose 1 as the root of the tree.

We will use Dsu on tree to get these two things :

calc[u] as the number palindromic paths such that Lowest Common Ancestor of start and end vertices is u.
start[u] as the number palindromic paths start or end at u.

So now, if we have a palindromic path (x, y), this path will pass through u only if lca(x, y) = u or lca(x, y) is not inside SubTree(u).

So the number of palindromic paths pass through u is

sum(SIGMA(start(v : subtree(u))) — 2 * SIGMA(calc(v : subtree(u)) + calc(u).

→ Reply

enogseh

7 years ago, # ^ |

...

thank's :D

→ Reply

rajat1603

7 years ago, # |

+95

So do i get 2 tshirts?

→ Reply

mitsuki

7 years ago, # ^ |

ideally you should

→ Reply

satyaki3794

7 years ago, # ^ |

+27

Yes, I think we will. AFAIK, it has happened before too.

→ Reply

7 years ago, # ^ |

+17

Yes, you will. Congrats! :)

→ Reply

Baba

7 years ago, # ^ |

+26

The way organizers had mentioned, you should be getting 2 T-shirts but wouldn't it make more sense to pass on one T-shirt to the next winner either in Top-20 World category or Top-5 Indian category? Anyways what value would the 2nd T-shirt of same contest add for you?
However, you guys are the winners, so it's up to you. Congrats btw!

→ Reply

mr_knownothing

7 years ago, # |

I submitted my solution to problem C and it results in RE at test 5. I tried running the testcase locally, it outputs correct. I am unable to reproduce the error. Can anyone help?

My submission id: 34391810

→ Reply

7 years ago, # ^ |

Try custom invocation and print some debug variables (maybe you forgot to declare some variable — locally it stars with 0 but on codeforces server it starts with something else)

→ Reply

yassin_

7 years ago, # ^ |

use diagnostics compiler

→ Reply

balalaika

7 years ago, # ^ |

Adding cout to begin of choose_again() removes RE. So I thing you've somewhere got UB.

→ Reply

balalaika

7 years ago, # ^ |

← Rev. 3 →

Yeah, you've got UB. if last cycle for i = 1 and j = 2 and number s with one 1-bit you access element at index 1, while size of bits is 1. So you've got there UB.

→ Reply

mr_knownothing

7 years ago, # ^ |

Yeah, I found that out. Was just waiting for the problem to get unlocked for practice again, just to be sure.

Thanks, anyway! :-)

→ Reply

7 years ago, # |

+91

this guy skipped Candidate Master!!

→ Reply

kriii

7 years ago, # |

Is anybody check the brute-force solution of H?

For (n,d) = (4,2) and (4,3), my submitted solution and brute-force solution both give 268 and 364 respectively. But test outputs give 168 and 264.

My two solutions agree about some small input, so I couldn't recognize what is wrong. If anybody recognizes something wrong in my solution, please gives help. Thanks.

→ Reply

Um_nik

7 years ago, # ^ |

+19

Both players should play optimally. If for some tree Storm will win then Ember won't choose this tree.

→ Reply

kriii

7 years ago, # ^ |

Oh, I misread whole problem statement...

I need to sleep... Thank you!

→ Reply

dotorya

7 years ago, # |

+61

Why did Um_nik disappeared from the scoreboard? I definitely saw him on the scoreboard..

→ Reply

Um_nik

7 years ago, # ^ |

+74

Admins decided that I was heavily affected by issue with problem H (probably because I was the first one to submit a clar about wrong sample), but I certainly wasn't, so they will restore me.

→ Reply

dotorya

7 years ago, # ^ |

+16

Oh, I got it. Thank you for your response. It was great that you solved problem H finally!

→ Reply

7 years ago, # ^ |

-13

Probably he spent some time on H and found an error in the statement. Since he spent some time there he probably asked to be out of competition

→ Reply

hell_hacker

7 years ago, # |

I am not able to figure out wrong logic in my approach for C. I precalculated the number of 1s in binary representation from 1 to 1000. Now I start from 1st digit. If it is 1 I have 2 options. Put 1 and move to the next digit or put 0 and make number of 1s equal to all precalculated values with k-1 1s. If it is 0 I move on to the next digit directly. For example k = 2 then I try to make number of 1s equal to 2, 4, 8, 16, 32... so that in next step I get 1.

→ Reply

fmota

7 years ago, # |

← Rev. 3 →

The last year magic was canceled in the scoreboard

UPD: It's fixed

→ Reply

21August

7 years ago, # |

WTF is happening with the rating changes?

→ Reply

suspicio

7 years ago, # |

What happened. The rating just disappeared

→ Reply

koadma

7 years ago, # ^ |

I guess history just repeated itself :(

→ Reply

7 years ago, # ^ |

← Rev. 3 →

They are updating some scores. Usually it is someone who was detected of cheating that acctually wasnt — so they reinsert him in the scoreboard (which requires everyone's rating to be uptaded).

So no, it does not mean that the contest is unrated

→ Reply

suspicio

7 years ago, # ^ |

I hope

→ Reply

hell_hacker

7 years ago, # ^ |

I am not sure but I guess they are checking Um_nik's submissions because first the contest was made unrated for him (see his comment above). So they have to change the rankings.

→ Reply

MikeMirzayanov

7 years ago, # ^ |

+209

Um_nik obligingly pointed on the issue in the H and spent a lot of time to argue his point of view. I've made him "out of competition", but he asked to return him despite he has negative rating change. He is my hero for today!

→ Reply

21August

7 years ago, # ^ |

It is Um_nik but not for cheating but for not bothering a legendsry grandmaster

→ Reply

suspicio

7 years ago, # |

-10

What happening

→ Reply

Vsevolod_Kaplin

7 years ago, # ^ |

They've decided to retest Um_nik's solutions?

And...He has already changed his username from KarimHussein to KarimHussein? Or it's just a bug?

→ Reply

7 years ago, # ^ |

Did you just scr...

→ Reply

7 years ago, # |

Auto comment: topic has been updated by Superty (previous revision, new revision, compare).

→ Reply

burstintotears

7 years ago, # |

← Rev. 2 →

Why there is no changes at the top rated board?

→ Reply

ZaakDov

7 years ago, # |

MikeMirzayanov Hello Mike! I'd like to ask a question. Is there any way to test someone's code with a large file data or a data generator after a contest is completed? After this contest, I've do some analyses for the problems, and found some coders' solution make me confused after calculated the time complexity myself, so I want to do a test to those solutions. Many thanks!!

→ Reply

613

7 years ago, # |

← Rev. 4 →

+14

I got Top 20 this time.How can I receive the T-shirt, thanks. I haven't receive any gifts from Codeforces before so that I do not know what to do. @Superty

→ Reply