Codeforces Round #337 (Div. 2)

9 years ago, # |

← Rev. 2 →

-27

It is unusal time. Thanks everyone who participate in this contest.

→ Reply

9 years ago, # ^ |

-50

negative to positive.

→ Reply

9 years ago, # |

-48

The scoring distribution will be announced after the contest.

→ Reply

9 years ago, # |

-33

Total: 4206 Contestants: 3959 Out of competition: 247

→ Reply

chaho

9 years ago, # |

wtf!!!! the sitre went down!!! i didnt had time to register

→ Reply

wineColoredDays

9 years ago, # |

+11

The site was down for the last 5 min, i couldn't reg :(

→ Reply

Killever

9 years ago, # ^ |

you can register now

→ Reply

nazaninnnnn

9 years ago, # |

-13

I love delay :(( :|

→ Reply

thezodiac1994

9 years ago, # |

Scoring distribution will be announced after the contest?

→ Reply

maximaxi

9 years ago, # |

+12

Been seeing a lot of this recently... ;_;

awef

→ Reply

Xephy

9 years ago, # ^ |

-6

when CF so laggy, you accidentally send the same comment twice.

→ Reply

alex_bucevschi

9 years ago, # |

+34

" UPD The start time of the Round is moved on 10 minutes.". Should be: The start time of the Round is moved on 15 minutes, right?

→ Reply

ejq

9 years ago, # |

+45

For most people at UTC+8, it will be the best time forever XD

They will enjoy a real "usual" time contest.

Anyway, gl & hf, thanks to fcspartakm & Edvard.

→ Reply

yyyyyyffffff

9 years ago, # ^ |

I think just like the football ,we should have some round at different time to make people over the world enjoy the happiness that cf brings to us.

→ Reply

urbanist

9 years ago, # |

Wow, the server is so buggy today. Takes minutes to load pages... Really impacts contest performance and productivity negatively...

→ Reply

travelers

9 years ago, # |

hacked after locking is this possible

→ Reply

9 years ago, # ^ |

Yes.

Locking just gives you access to others code. If other person has locked his/her solution then he/she can hack others solution even when other participant hasn't locked his/her solution. So submit only when you are sure.

I too realised this during a contest.

→ Reply

9 years ago, # |

WA on test 7 >_<

→ Reply

nikitosoleil

9 years ago, # ^ |

If you are about problem B, try this test on your solution: 5 1 1 1 2 1 Correct answer is 6. I also have a lot of problems with test #7, but i have already passed all system tests with completely different from first implementation.

→ Reply

9 years ago, # ^ |

Hm, my only problem with test 7 was using int32 instead of int64. When changed — AC.

→ Reply

nikitosoleil

9 years ago, # ^ |

В случае sarvagya3943 ошибка как раз таки в неправильной реализации, а не переполнении переменной.

→ Reply

9 years ago, # ^ |

problem is with my logic i guess !

→ Reply

_Ramtin_

9 years ago, # |

+32

A is mad ! O(n) solution would get ac really ? i tried to hack an O(n) solution with 2000000000 but i got UHA :(

→ Reply

manetsus

9 years ago, # ^ |

← Rev. 2 →

I think not. May be he did some constant optimization like this one: 15044253. The complexity of this solution is

$\text{[math]}$

As far I know, CF allows 4 * 10⁸ operations in one second roughly.

And always think twice before hacking any solution for TLE like me!

This solution was in my room, but I am not that fool. :)

→ Reply

9 years ago, # ^ |

I've seen a lot of times when bad complexities pass, because of marginal optimizations.

→ Reply

gepardo

9 years ago, # ^ |

← Rev. 2 →

+12

You are wrong. CF can make 10^9 operations per 0.6 seconds: 14032294

→ Reply

manetsus

9 years ago, # ^ |

Mainly I told about C++.

However, it varies on the computation you did in every iteration. But our consideration is only the worst cases.

Or may be CF increasing their speed day by day! :)

→ Reply

http://codeforces.me/contest/610/submission/15052683

9 years ago, # ^ |

← Rev. 2 →

Check this submission I tried to hack. It gave me UHA. It actually failed on systest when codeforces gave the test 2000000000. However when we hack it it gives UHA. Some bug.

→ Reply

9 years ago, # |

Fluctuating pupil / specialist . ;(

→ Reply

9 years ago, # ^ |

Fluctuating pupil :( :P

→ Reply

9 years ago, # ^ |

Look for garbage value in B. I was getting WA in pretest 3 then i realized that when there is only one minimum then some values will be garbage.

→ Reply

9 years ago, # ^ |

I get WA 7 :(

→ Reply

9 years ago, # ^ |

WA 7 is about int overflow, use long (64-bit) data type for calculating a sum.

→ Reply

9 years ago, # |

Don't you just love it when you get hacked in a solution, but your hacker is so nice, he gives you ample time to rectify your mistakes ^_^ .

→ Reply

9 years ago, # ^ |

Yea that happened with my A. I was first thinking they should have written print -1 when not possible so that it will cover odd case. But i submitted my code without thinking over it. Pretest passed -> Hacked -> AC. :)

→ Reply

smahdavi4

9 years ago, # |

does pretests of C include all K s?

→ Reply

I_love_Tanya_Romanova

9 years ago, # ^ |

+15

There are people with successful hacks on C.

→ Reply

9 years ago, # ^ |

Lol,no. Why would they do that

→ Reply

_Ramtin_

9 years ago, # ^ |

nope because the person that commented just before u had his C hacked :)

→ Reply

ben13

9 years ago, # ^ |

Nope ... My friend got hacked in problem c for k=0

→ Reply

ben13

9 years ago, # |

Isn't the k=0 case in problem c a controversial one ?? Because some consider that there is no solution for it .. while others printed + for it .. U cannot have an orthogonal set over there r8 ??

→ Reply

9 years ago, # ^ |

Let's just accept the fact that if you got hacked in C, it was because of k=0, and then rectify it.

→ Reply

-is-this-fft-

9 years ago, # ^ |

The condition was that any two vectors are orthogonal. Since there is only one vector, the condition remains true.

→ Reply

colin_ni

9 years ago, # |

+39

Problem C is very unoriginal: https://en.wikipedia.org/wiki/Walsh_matrix#Formula

→ Reply

9 years ago, # ^ |

And D is the most original problem ever :P

→ Reply

Edvard

9 years ago, # ^ |

Sorry for that. I didn't know about that. Actually the legend is true story about me.

→ Reply

Joeization

9 years ago, # |

How to solve pC ?
is it gray code or something?

→ Reply

drd93

9 years ago, # ^ |

+12

i solved it next:

start from K = 0, then lets say the vector is + Now for all numbers from 1 to K do next:

copy existing vectors
for the first half of vectors, duplicate them (i.e. ++ -> ++++, +* -> +*+*)
for the second half of vectors, add their reverse (i.e. ++ -> ++**, +* -> +**+)

→ Reply

Joeization

9 years ago, # ^ |

and how to output 2^k answers?

→ Reply

drd93

9 years ago, # ^ |

Each time you iterate the cycle I described your number of answers gets doubled. So for K = 0 you have 1 vector '+', for K = 1 you will have 2 vectors, for K = 2 you have 4 vectors and so on.

Technically, I solved it using char arrays. And then just pring every char array on its own line

→ Reply

bholagabbar

9 years ago, # ^ |

What was the intuition behind this?

→ Reply

pew-pew

9 years ago, # ^ |

My solution was:

answer for k = 0: (1) (or "+")

answer for k:

all vectors from (k-1) answer doubled and all vectors from (k — 1) answer doubled, but second half is inverted

→ Reply

9 years ago, # |

← Rev. 3 →

+22

Hello,can anyone look into my hack #192799? I think there is a problem with the checker maybe?

Solution verdict:
OK

Checker:
ok OK. Be happy!

Input:
1

Output:
+
*

Answer:
++
+*

How can this be correct?

→ Reply

Zharaskhan

9 years ago, # ^ |

Print 2^k lines consisting of 2^k characters each.

→ Reply

9 years ago, # ^ |

Yes,he printed 2 lines of 1 character but he should have printed 2 lines of 2 character.

→ Reply

krock21

9 years ago, # ^ |

really this print + * on test 1

→ Reply

GlebsHP

9 years ago, # ^ |

+30

We are working on this issue.

→ Reply

GlebsHP

9 years ago, # ^ |

+23

Issue is now resolved, everyone should be happy I suppose)

→ Reply

9 years ago, # ^ |

← Rev. 2 →

Can you please open problemset now? It says temporarily blocked

→ Reply

9 years ago, # ^ |

It seems that his submission 15050289 was still accepted and he still got 1200 points for that problem?

→ Reply

GlebsHP

9 years ago, # ^ |

Yes. He has a correct solution that works incorrect only in this case, so we decided to keep it accepted.

→ Reply

9 years ago, # ^ |

← Rev. 4 →

+10

I accept your decision but I think it is a bit unfair,since it goes against the spirit of competitive programming.It is wrong even if only on one case.What if there is no bug in the checker in the first place,will it still be accepted?Let alone I should get +100 points for a successful hacking.

→ Reply

9 years ago, # ^ |

If there was no bug in the checker in the first place, it would have given me "Wrong answer on pretest 2", then I'd read my code again, find the bug and resubmit. But since it passed pretests, I assumed it was correct and moved on to problem D.

I think that what would actually be unfair is get -1200 points on a contest because the checker failed on pretest 2.

→ Reply

krock21

9 years ago, # ^ |

контест будет нерейтинговым? таблицы изменятся? у tenshi_kanade всё ещё Accepted за C

→ Reply

krock21

9 years ago, # ^ |

THIS

→ Reply

9 years ago, # |

← Rev. 2 →

@fcspartakm ; There has been solutions to problem A with an O(n) solution, which is getting passed. I tried to hack one with input as 2*(10^9) and it still passed. How is this possible?

→ Reply

9 years ago, # ^ |

Compiler Optimization most probably.

→ Reply

9 years ago, # ^ |

I don't think that should be allowed. And it's a pretty straightforward O(n). Where the loop runs n/2 times.

→ Reply

9 years ago, # ^ |

I read about this here: http://codeforces.me/blog/entry/21585?#comment-263052

→ Reply

http://codeforces.me/contest/610/submission/15052683

9 years ago, # ^ |

← Rev. 2 →

This is the link to the submission. It got a WA in systests, and it is giving WA on my system as well for the input for which I hacked. In sys-tests this guy has TLE's on the same code. How come the hack passed?

Can you please check this fcspartakm, Edvard, [user:GlebsHP)]?

→ Reply

Xerx

9 years ago, # |

+21

Em I really do wanna know what is point of retarded hacks like in this contest, a good hack should be one that needs your effort to find test case that is not working, not having no pretests and then first guy, that gets the idea of: Oh, maybe they have no pretests, get like 1500 points?

→ Reply

drd93

9 years ago, # |

So how do you check intersecting points in D without checking all lines which are in the range?

Like you have a horizontal line from -1000 to 1000 and there are 100000 vertical lines in this range — how do you avoid checking every one of them?

And if you can't, then the solution complexity is n^2 right? Because if there are 10 horizontal lines who all start from -1000 to 1000 on different Y positions then you still have to check 100000 vertical lines for each of these horizontal lines, right?

Tried to optimize my solution for 30 minutes without any luck :(

→ Reply

bholagabbar

9 years ago, # |

← Rev. 2 →

In problem B, 3 WA on pretest 7 with int, even in JAVA! :( Finally passed it

→ Reply

gfonn

9 years ago, # ^ |

Hahaha, the same to me! But TLE instead, and something like 4 times :p. Finally AC

→ Reply

9 years ago, # ^ |

I got 2 WA with long long :(

→ Reply

9 years ago, # |

During contest my friendlist was behaving weirdly. Did this happen with others?

→ Reply

sinhashubham95

9 years ago, # |

when will the system tests start

→ Reply

9 years ago, # |

Way too much China :P

→ Reply

9 years ago, # ^ |

-19

I worked so hard to get over my addiction to chineese food, and now you remind me of it ;_;

→ Reply

sinhashubham95

9 years ago, # |

in problem b the wa was due to the constraints 10^9 not anything else

→ Reply

saurabhverma

9 years ago, # |

+11

To the person who answers questions, if I am taking time to ask a question very specific to the problem, I have carefully read the statement and understood as much as I can. After that, if I am still not able to understand, the fault is not always mine.

After solving C, I had to wait for 10 minutes on clarification of case k = 0. This penalised my time for D which I could not code in time.

I am still not able to understand problem A at all. The contest had good problems. Please be a little more helpful and kind with the statements.

→ Reply

wiseboy

9 years ago, # |

I was able to register only coz of the delay, and luckily, I'm getting a notable jump in ratings this time!

→ Reply

9 years ago, # |

+14

Wake me up, when the ratings change

→ Reply

C137

9 years ago, # |

I should have solved B faster :( one hour for an easy problem is not good...

→ Reply

9 years ago, # |

So after 3-4 WA on problem B: Wrong answer on test 53 :\ :(

→ Reply

9 years ago, # ^ |

You also have to consider the distance between first minimum value and last minimum value.

→ Reply

9 years ago, # ^ |

Yeah added that now and got ac now :)

→ Reply

zscoder

9 years ago, # |

Nice fast editorial! Thanks fcspartakm!

→ Reply

Trasier

9 years ago, # |

Good Contest and give me good luck.

→ Reply

9 years ago, # |

← Rev. 2 →

+21

am I the only one who think that D is repeated and very dull problem?

maybe the right place for this problem is educational rounds not rated rounds

→ Reply

9 years ago, # ^ |

Maybe, but it is Div2 and only 123 ppl solved it. So seems very fine :)

→ Reply

allllekssssa

9 years ago, # ^ |

It was standard task, but I decided to do the third task, new and interesting for me. After nearly two hours of thinking I realized that I am very stupid guy :)

→ Reply

dogther

9 years ago, # ^ |

After thinking of C for nearly an hour, I found D an easy task but finally failed to code it out before the contest ended...

→ Reply

zhy

9 years ago, # ^ |

The same with you...

And C is just weird someway... I don't think the solution can be called 'algorithm' anyway.

→ Reply

9 years ago, # ^ |

yes, it's "guess the pattern" problem

→ Reply

Ir1d

9 years ago, # ^ |

Can you share your ideas on how you found the pattern?

I kept thinking about it but nothing found until I read the Hadamard_matrix

→ Reply

9 years ago, # ^ |

I thought I should use the answer for K-1 to compute the answer for K, since the answer for K-1 is 2^(K-1) * 2^(K-1) square and for K it's 2^K * 2^K square then I knew I have to complete the other 3 parts of the square using the first one

→ Reply

Ir1d

9 years ago, # ^ |

Thanks.

→ Reply

9 years ago, # ^ |

Haha, yes. Guessed the pattern, then copied and pasted k times :)

→ Reply

manetsus

9 years ago, # |

+39

ho-jo-bo-ro-lo, the perfect complexity analyzer: 15049767 :)

→ Reply

9 years ago, # ^ |

+42

how about this one 2563497 not even a single millisecond margin

→ Reply

9 years ago, # |

Its been an hour, still no rating change. They probably caught one cheater at least, because my standings improved by 1.

→ Reply

9 years ago, # ^ |

My standings improved by like 15 positions since system testing finished :)

→ Reply

9 years ago, # ^ |

← Rev. 2 →

Nothing to see here.

→ Reply

9 years ago, # ^ |

← Rev. 2 →

Well, my position improved by 2 so that must be the case :)

→ Reply

9 years ago, # ^ |

If yours improved by 2, then mine should too, you stood better than me.

→ Reply

indroneal

9 years ago, # |

where is the rating changes ? :(

→ Reply

9 years ago, # ^ |

Its coming, just like winters . FYI winters hasn't reached my country yet.

→ Reply

_Rampage_

9 years ago, # |

+21

why unoffical Participants still rated ?

→ Reply

nt.hieu

9 years ago, # ^ |

← Rev. 2 →

I think any participant who hack in contest will be rated

→ Reply

9 years ago, # |

Div 1 users got rating changes. For example, Alex_2oo8 went from 2590 down to 2315. Please, you have to correct that...

→ Reply

RetiredAmrMahmoud

9 years ago, # |

kingofnumbers got -176 rating change although he's unofficial participant.

→ Reply

mkisic

9 years ago, # ^ |

I got -169 and I'am unofficial participant too

→ Reply

_Rampage_

9 years ago, # ^ |

all participan hacked still rated

→ Reply

TheConfessor

9 years ago, # ^ |

mb cheats?

→ Reply

zhy

9 years ago, # |

Seems ratings are difficult to calculate →_→.

→ Reply

Yuuki_Asuna

9 years ago, # |

Will this round be unrated ？

→ Reply

9 years ago, # |

Why do I have less rating increase than I had an hour ago?

→ Reply

9 years ago, # ^ |

Because the ratings calculated earlier included Div 1 unofficial participants who hacked during the contest, and that's not supposed to happen.

→ Reply

9 years ago, # ^ |

Ok, thanks! :) And congrats for getting back to div1 :)

→ Reply

9 years ago, # ^ |

Thanks!

→ Reply

hard-rox

9 years ago, # |

I solved problem A without any wrong ans. But my rating decrease 8. Why?

→ Reply

Velter

9 years ago, # ^ |

Rating is calculated considering time of solving and first successful attempt. And also with some special expected and real positions. To more information click in this link.

→ Reply

damien_g

9 years ago, # |

WTF is happening to the rating ?

It has been saying "System testing 100%" for quite a while now.

It seems that the last educational round was also rejudged ???

And why did rating changes disappeared ?

→ Reply

Aemon

9 years ago, # ^ |

+15

This round has given me more anxiety than I know what to do with.

→ Reply

damien_g

9 years ago, # ^ |

OK, back to final standings :-)

They may take our lives, but they will never take our rating changes :D

→ Reply

send_nodes

9 years ago, # ^ |

Seems indicative of a zombie apocalypse...

→ Reply

damien_g

9 years ago, # ^ |

+26

It reminds me what happened at the Miss Universe ceremony.

Like "You are Miss Universe", and then

Here, it's the same but for a "+162" in rating...

→ Reply

dracarys30

9 years ago, # ^ |

Is there any chance the contest is unrated? coz its should not be! What is it with these judges just give the rating and get over it!

→ Reply

9 years ago, # ^ |

Mike just found a submission that was judged as "cheating", but in the end it was not. Give it some time to recalculate again.

→ Reply

9 years ago, # |

Where have the rating changes gone? They were calculated, then reset because they were wrong, then recalculated, now I come back and they are gone again. What the... ?!?!?!

→ Reply

MahanZDH

9 years ago, # ^ |

I know it is a strategy to kill us with anxiety :-|

English is not my native language

→ Reply

tweety

9 years ago, # ^ |

Your English is pretty good. I think that adding that note at the end (or "sorry for poor English") is what makes it look bad.

→ Reply

Melnik

9 years ago, # |

← Rev. 2 →

Has anybody any information about our ratings? I'm very excited)

→ Reply

hloya_ygrt

9 years ago, # ^ |

You shouldnt worry that much , sir. Rating is not the most important thing in your life.

→ Reply

Melnik

9 years ago, # ^ |

Actually, it is))0)

→ Reply

9 years ago, # |

← Rev. 2 →

+28

Rating change seems to be John Cena. I can't see it.

→ Reply

tweety

9 years ago, # ^ |

^ We have a winner over here

→ Reply

saurabhverma

9 years ago, # |

I just can't sleep. I want to be candidate master today ^_^. Give me my rating :D

→ Reply

9 years ago, # ^ |

Its really not the greatest thing that can happen for you :) Back in the days before colors revolution it was like "I'm in div1 now, yay! Why is there only div2 contests? Finally, a div1 contest! Damn, I'm back in the div2 again." :)

→ Reply

saurabhverma

9 years ago, # ^ |

+32

After being rejected from MITACS, EPFL, Google, Jane Street, Microsoft and many more, this is surely the best thing happening in long time.

These are not the days before color revolution.

Let me celebrate my happiness. I am in love with it :D

→ Reply

9 years ago, # ^ |

Huh, then congrats!

→ Reply

9 years ago, # ^ |

First they reject you, then you build something so awesome, they buy it for billions of dollars(remember whatsap). Chin up, buttercup! :D And congrats. I am inspired by you :)

→ Reply

9 years ago, # |

I love this! :D I check my status it says pupil then i come back after two hours it says i am specialist! Codeforces changing colours of people like colour change on a Christmas tree! :D

→ Reply

urbanist

9 years ago, # ^ |

You are a pupil again.

→ Reply