Hello, Codeforces!
I'd like to invite you to Codeforces Round #337 (Div. 2). It'll be held on Sunday, December 27 at 14:05 MSK (Moscow time) and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time!!!
Me and Edvard Davtyan (Edvard) prepared the tasks for this Round.
Great thanks to Gleb Evstropov (GlebsHP) for helping us preparing the contest, to Maria Belova (Delinur) for translating the statements into English and to Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform.
The scoring distribution will be announced later. Good luck everyone!
UPD The start time of the Round is moved on 10 minutes. Score distribution 500-1000-1500-2500-2500
UPD2 Competition completed! Thank you all! Editorial
Yee this contests digits are prime :-D
What a nerd ...
Recently Edvard prepared so many round, like a Problem_HULK ! Sorry to say , but description of problems prepared by fcspartakm are really hard to understand. Hope this time , it will be okay !
Really appreciate the effort Edvard is doing here.
As usual, the round starts in the unusual time :)
Worst unusual time ever :(
I agree... contest begins when I am at school
So me.. like you.
But it is very suitable for us students in China. :)
Also suitable for students in India (4:50 pm) :D
I think so too。
GL & HF
Hope to be an expert after #337 div2!Come on,Parco!
My brain after reading this comment:
M-x replace-string "expert" "candidate master"; M-x replace-string "Parco" "KostikBigOne"
rank 300,i think i could be an expert :D
btw,what's wrong with the rating now?
It is unusal time. Thanks everyone who participate in this contest.
negative to positive.
The scoring distribution will be announced after the contest.
Total: 4206 Contestants: 3959 Out of competition: 247
wtf!!!! the sitre went down!!! i didnt had time to register
The site was down for the last 5 min, i couldn't reg :(
you can register now
I love delay :(( :|
Scoring distribution will be announced after the contest?
Been seeing a lot of this recently... ;_;
when CF so laggy, you accidentally send the same comment twice.
" 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?
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.
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.
Wow, the server is so buggy today. Takes minutes to load pages... Really impacts contest performance and productivity negatively...
hacked after locking is this possible
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.
WA on test 7 >_<
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.
Hm, my only problem with test 7 was using int32 instead of int64. When changed — AC.
В случае sarvagya3943 ошибка как раз таки в неправильной реализации, а не переполнении переменной.
problem is with my logic i guess !
A is mad ! O(n) solution would get ac really ? i tried to hack an O(n) solution with 2000000000 but i got UHA :(
I think not. May be he did some constant optimization like this one: 15044253. The complexity of this solution is
As far I know, CF allows 4 * 108 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. :)
I've seen a lot of times when bad complexities pass, because of marginal optimizations.
You are wrong. CF can make 10^9 operations per 0.6 seconds: 14032294
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! :)
http://codeforces.me/contest/610/submission/15052683
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.
Fluctuating pupil / specialist . ;(
Fluctuating pupil :( :P
:(
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.
I get WA 7 :(
WA 7 is about int overflow, use long (64-bit) data type for calculating a sum.
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 ^_^ .
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. :)
does pretests of C include all K s?
There are people with successful hacks on C.
Lol,no. Why would they do that
nope because the person that commented just before u had his C hacked :)
Nope ... My friend got hacked in problem c for k=0
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 ??
Let's just accept the fact that if you got hacked in C, it was because of k=0, and then rectify it.
The condition was that any two vectors are orthogonal. Since there is only one vector, the condition remains true.
Problem C is very unoriginal: https://en.wikipedia.org/wiki/Walsh_matrix#Formula
And D is the most original problem ever :P
Sorry for that. I didn't know about that. Actually the legend is true story about me.
How to solve pC ?
is it gray code or something?
i solved it next:
start from K = 0, then lets say the vector is + Now for all numbers from 1 to K do next:
and how to output 2^k answers?
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
What was the intuition behind this?
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
Hello,can anyone look into my hack #192799? I think there is a problem with the checker maybe?
How can this be correct?
Print 2^k lines consisting of 2^k characters each.
Yes,he printed 2 lines of 1 character but he should have printed 2 lines of 2 character.
really this print + * on test 1
We are working on this issue.
Issue is now resolved, everyone should be happy I suppose)
Can you please open problemset now? It says temporarily blocked
It seems that his submission 15050289 was still accepted and he still got 1200 points for that problem?
Yes. He has a correct solution that works incorrect only in this case, so we decided to keep it accepted.
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.
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.
контест будет нерейтинговым? таблицы изменятся? у tenshi_kanade всё ещё Accepted за C
THIS
@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?
Compiler Optimization most probably.
I don't think that should be allowed. And it's a pretty straightforward O(n). Where the loop runs n/2 times.
I read about this here: http://codeforces.me/blog/entry/21585?#comment-263052
http://codeforces.me/contest/610/submission/15052683
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)]?
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?
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 :(
In problem B, 3 WA on pretest 7 with int, even in JAVA! :( Finally passed it
Hahaha, the same to me! But TLE instead, and something like 4 times :p. Finally AC
I got 2 WA with long long :(
During contest my friendlist was behaving weirdly. Did this happen with others?
when will the system tests start
Way too much China :P
I worked so hard to get over my addiction to chineese food, and now you remind me of it ;_;
in problem b the wa was due to the constraints 10^9 not anything else
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.
I was able to register only coz of the delay, and luckily, I'm getting a notable jump in ratings this time!
Wake me up, when the ratings change
I should have solved B faster :( one hour for an easy problem is not good...
So after 3-4 WA on problem B: Wrong answer on test 53 :\ :(
You also have to consider the distance between first minimum value and last minimum value.
Yeah added that now and got ac now :)
Nice fast editorial! Thanks fcspartakm!
Good Contest and give me good luck.
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
Maybe, but it is Div2 and only 123 ppl solved it. So seems very fine :)
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 :)
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...
The same with you...
And C is just weird someway... I don't think the solution can be called 'algorithm' anyway.
yes, it's "guess the pattern" problem
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
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
Thanks.
Haha, yes. Guessed the pattern, then copied and pasted k times :)
ho-jo-bo-ro-lo, the perfect complexity analyzer: 15049767 :)
how about this one 2563497 not even a single millisecond margin
Its been an hour, still no rating change. They probably caught one cheater at least, because my standings improved by 1.
My standings improved by like 15 positions since system testing finished :)
Nothing to see here.
Well, my position improved by 2 so that must be the case :)
If yours improved by 2, then mine should too, you stood better than me.
where is the rating changes ? :(
Its coming, just like winters . FYI winters hasn't reached my country yet.
why unoffical Participants still rated ?
I think any participant who hack in contest will be rated
Div 1 users got rating changes. For example, Alex_2oo8 went from 2590 down to 2315. Please, you have to correct that...
kingofnumbers got -176 rating change although he's unofficial participant.
I got -169 and I'am unofficial participant too
all participan hacked still rated
mb cheats?
Seems ratings are difficult to calculate →_→.
Will this round be unrated ?
Why do I have less rating increase than I had an hour ago?
Because the ratings calculated earlier included Div 1 unofficial participants who hacked during the contest, and that's not supposed to happen.
Ok, thanks! :) And congrats for getting back to div1 :)
Thanks!
I solved problem A without any wrong ans. But my rating decrease 8. Why?
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.
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 ?
This round has given me more anxiety than I know what to do with.
OK, back to final standings :-)
They may take our lives, but they will never take our rating changes :D
Seems indicative of a zombie apocalypse...
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...
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!
Mike just found a submission that was judged as "cheating", but in the end it was not. Give it some time to recalculate again.
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... ?!?!?!
I know it is a strategy to kill us with anxiety :-|
English is not my native language
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.
Has anybody any information about our ratings? I'm very excited)
You shouldnt worry that much , sir. Rating is not the most important thing in your life.
Actually, it is))0)
Rating change seems to be John Cena. I can't see it.
^ We have a winner over here
I just can't sleep. I want to be candidate master today ^_^. Give me my rating :D
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." :)
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
Huh, then congrats!
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 :)
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
You are a pupil again.
Yea it is switching itself after sometime. When contest goes rated i am pupil when it is unrated i am specialist! :D
Did you re-rate the contest? My rating change seems to be different than it was several hours ago...
Also some features on the website don't seem to be present (search). Is it just on my phone or is there some problem on the server?