Всем привет!
Мы дэт-метал группа Skyglow, недавно у нас вышел первый альбом. И поскольку мы по совместительству являмся спортивными программистами, мы решили провести в честь этого раунд на Codeforces!
Раунд состоится в 13.07.2018 17:35 (Московское время). В каждом дивизионе будет по пять задач, три из них будут совпадать. Задачи составлены мной и rembocoder, также контест помогали подготовить TeaPot, slavik, mingaleg и niyaznigmatul. Благодарим demon1999 и winger за прорешивание, нашего координатора arsijo и, конечно, MikeMirzayanov за предоставление площадок Codeforces и Polygon.
Послушать альбом можно по ссылке:
Вы очень поможете нам, если репостните нас, даже если сами вы такую музыку не слушаете.
- https://vk.com/skyglowband?w=wall-134984483_323
- https://www.facebook.com/skyglowband/posts/2100310513570956
Всем участникам контеста, изъявившим желание, мы подарим альбом на CD диске. (Если таких окажется много, то мы выберем из них нескольких лучших по результату раунда). Обращайтесь ко мне в личные сообщения.
Удачи на контесте!
UPD1. мы подарим наш альбом на CD диске лучшим 10 участникам, которые хотели бы его получить. Чтобы поучаствовать в розыгрыше, напишите мне личное сообщение до контеста с вашим адресом, индексом и полным именем.
UPD2. Разбаловка выглядит следующим образом:
Div2: 500-1000-1500-2000-2500
Div1: 500-1000-1500-2250-2500
UPD3. Мы всё ещё думаем, нужно ли делать раунд рейтинговым или нет. Вы можете поделиться своим мнением в блоге Майка.
UPD4. Мы решили отсортировать пользователей по изменению рейтинга, так что следующие участники получат диск:
riela, +332
DongwonShin, +278
Erdenebayar, +176
DOlaBMOon, +148
Muhimin_Osim, +121
ciphereck, +117
Dotiros, +104
luismo, +94
MaxZubec, +72
whybee, +70
UPD5. Поздравляем победителей!
Div1:
Div2:
- riela
- Kato_Megumi
- luis.trivelatto
- yukuai26
- _D41_
- gls1196
- TaoSama
- chenyuqi0215
- DearMargaret
- Rena_Takeda
UPD6. Опубликован разбор!
Из музыки слушаю только гимн СССР
cool name!!! SKYGLOW
i think it will going to be good contest
And so hard!
It's going to rock
I'm sorry, but I think our music is better.
BTW, we released a new album yesterday, here's an MV: https://www.youtube.com/watch?v=Fm5iP0S1z9w
— My music is hit! — No, your is shit!
I know, it's so shit that it hit 20M views in 1 day :D
So you came to PR on our contest? Sorry, I don't rate the quality of a song by the number of views, or else I end up listening to Justin Bieber.
UPD: OK, now I see it is not even you, I am slowpoke. It's becuase you did not give the link in the beginning, so I thought you are really from a band.
You don't have to agree with me on how you rate songs or which song is better. I'm just saying that if there is a huge difference in the number of views, it suggests that one is more popular than the other :/ (aka more people think one is better)
First, if many people think it is better it doesn't mean it is better. Second, how can you know what they think, did you ask them? They didn't even hear my songs, lol, how would they compare?
You're right, our music might not be better than yours.
I'll just leave my comment as my personal opinion.
Good luck gaining popularity then, I'm sure you guys will get millions of album purchases, considering how "[your] music is hit"!!!
In this thread: two musicians that are better than me at programming and at music arguing with each other... Coming from drastically different genres: death metal vs. K-pop. There is only one way to settle this...
You guys should start a rap battle!
SirRembocodina, if I were you, I would have simply ignored her comment :-) The more replies she gets, the more people will pay attention to her comment (and the more views she will get).
It is your contest. You have worked hard to prepare it. You deserve more attention than anyone else.
"I'm sorry, but I think our music is better."
And by apologizing, you're not changing the fact that you just decided to boost your self-esteem by humiliating others. It's like saying sorry before you hit me. Sorry for my poor English.
What's wrong with comparing apples and oranges?
I'm just stating my personal opinion, is there something wrong with that?
If you want to state your personal opinion you should say like that, i think:
I like our music more than your's.
But you doing this another way:
I'm sorry, but I think our music is better.
So it ended up with confrontation, because you say that somebody have bad tastes in music if he listens to Skyglow's album.
And to be honest you've done this just to PR. Another way you could act is to say and not make any cconflict:
we too released new album yesterday, listen to it [link]
But you can't say anything without negativity or sarcasm.
Did I ever say that people have bad tastes in music if they listen to Skyglow?
Yes, it seems like my comments sound a bit too sarcastic. I will definitely learn from you.
for a country with population estimated to be 50m, and 20m hits for a music video?
The reason would be heat but (supposedly) not the beat (no offense).
Edit: OP's profile mentioned Taiwan and was confusing. But still its hard to believe on an average every 2 out of 5 saw video out of musical interest.
Our group is actually from South Korea. And the audience isn't limited to one country.
You can get the best from both worlds by watching your video on mute while having SkyGlow playing in a separate tab!
Author is red, so his music is better.
Since correlation is that high, I'll try to convince Petr and tourist to start a new band:)
If you are able to convince them then the above comment would read as :
"Author is LGM ,so his music is AC"
Oh how the tables have turned.
tzuyu_chou is LGM so her music is better
You guys are all wrong, AMERICAN music is the BEST IN THE WORLD
Let me give you a taste of what TRUE music is like in the land of the free and the home of the brave: youtube.com/watch?v=dQw4w9WgXcQ
when u already memorized the last 3 characters of the rick roll
Twice is best
Sorry to disturb，are you Ziyu Zhou herself？
Oh, you so naive darling, that is cf =)
Sorry to disturb，are you rorshach himself？=) PS: that Rorshach in Watchmen right?
I admit I'm just a naive pupil...Please go easy on me=）
I am kidding. I am just glad to find a person who has read Watchmen. I don't mean anything else. By the way I like Rorshach too.
Well, fine. I like Rorshach, and Watchmen is one of my favorite movie. Anyway, nice to meet you.（>_<）
I'm so shocked to see that 4 of the girls from Twice have CF accounts!
LMAO 0))0)), they're just fans of "TWICE"). Don't be shocked ))
BTW https://www.youtube.com/watch?v=i0p1bmr0EmE is TOP! I and my sister are your huge fans now =)
It's good to see that our advertising plan, to a small extent, somehow worked!!!
If your purpose is to lower your contribution, Congratulations! Your plan worked out remarkably!
Thanks! I only planned to help advertise but I also got the benefit of having a low contribution. Perhaps I can beat I_LOVE_METSUKA :P
Lol it gets harder as your contribution gets lower.
Also I just stopped trolling and actually trying to get better at CP instead.
Hit me up when you have lower contribution than me tho. I will be CM at that moment.
Hey where did the downvoters go? I never said your jobs were done.
each your comment should have 1000 upvotes
Your comment gets upvotes )). It makes me laugh xD. If you would be green, I'm sure that your comment would get -100 ))
I don't know why I get the feeling this contest will be nice! :)
Well, think again!!
why there is no verdict called Contest Overflow ?
That sounds so cool!
Lol, sorry, I downvoted your comment accidentally, and now everyone is downvoting it. This is how CF community works.
Nevermind,we are not the creature live on "up-vote" XD.
it's because master votes are worth many multiple points (more than 5 at least), not because others have also downvoted
Wow! This is cool, a death metal band is organizing a contest. I think this round is going to be great.
I think it will be a musical contest....
Is it rated???
Yes
Буду писать ваш контест и параллельно слушать альбом)
It happens that I'm a big Fan Of Death Metal !!!!! I'll listen your release, and I'll try not to miss the contest. I have to say that for the first time my two passions in life meet !!!
it feels good to downvote every comment :)
Surely does doing yours!!
Oh so good contest about music :D
The problems won't be about music, actually. It will be a regular contest without particular theme, just with good problems :)
Programmers, programmers everywhere...
I don't know if it's a joke or not, but you guys might be the coolest people here on cf.
A death metal band? Damn
У вас Ангела Госсов на вокале?
Хм, написано Александр Мокин. А довольно похоже.
I'm confused, is the music promoting the contest or the contest promoting the music? xD
okay , I am really hyped now <3 , a contest by death metal guys, and by the way , I liked Sacred Self-Deceit , especially the start , will listen to others soon :) ,
However , please dont put any music related legend / stories , once I had a really bad experience with a topcoder problem with music analogies , it does not makes sense to people who never made music , or dont know any instrument..
Крутой альбом.
I don't usually listen to this kind, but I got to say I really LOVED the music you are using, wish you all the best :D
Скоро на КФ — раунд от <букмекерская контора name>. С крикливым роликом, который будет автовоспроизводиться
Скоро на кф — раунд от Единой России , на подготовку которого было выделено овер9000 миллионов рублей
Пацаны, ну-ка поясните примечания к тексту песни Losing Humanity.
Сахарная dalex?
Че?
По твоему комментарию я предположил что наши политические взгляды сильно отличаются, и мой комментарий -- это завуалированное оскорбление связанное с этими различиями.
Ну насчет Крыма я допускаю, есть люди, которые считают иначе, пускай так, но тут челики обвиняют нашу страну еще и во второй мировой, теперь подумай, насколько это нормально.
Кажется, что они не обвинают, они там приводят достаточно сырые факты по этому поводу, нет?
Я бы скорее был бы удивлен тому, что они утверждают, что Крым был захвачен forcibly. Это тонкая граница -- если ко мне пацаны во дворе подошли и отжали телефон, не угрожая прямым текстом и не причиняя вреда, был ли мой телефон отжат forcibly?
То, что ты только что описал, называется "украли".
О, а вот и сам автор пожаловал.
Теперь объясни, почему Россия любит воевать и почему ты прицепил к этому утверждению (ложному, кстати) миллионы жертв во второй мировой.
Просто обвинять Россию во всех бедах человечества сейчас модно, а парни хотят быть в тренде.
Я не буду объяснять тебе то, что ты сам выдумал.
А я не буду писать раунд, составленный столь наивными людьми
Мне в телевизоре сказали, что нормально всё с крымом
Другие дет-метал группы вообще читают про кишки и другие гадости. А тут загнули реальную тему.
Really nice album art !!! Good taste in music too. Best of luck for your band :) Hope this round will be an interesting one .
Wow! How do you manage being a programming grandmaster and being in a band at the same time ?
You fool. He just doesn't need to participate in contests to maintain his rating.
Oh my god, really? What a pathetic fool he was for not realising that!
Friday 13th looks like a perfect day for a contest from a metal band.
My love for the album is based on my rating in this contest :'D
Me too, If i will became candidat master. I will love this album.))
my love for the album is based on my rating in this contest :"D
I wish to not be sent a CD :)
Are u a musician or a programmer O.o
The album is just in my favorite style. :) Hope it will be very famous soon! :D And I think I can have a fun time during this contest!
Authors music is as sharp as his coding skills.....
?detaR tI sI
.si ti seY
.unrated s'ti rO
А можна будет получить диск формата CD-RW??
I hope it is not a mathforces.
nor a hackforces...
This round sure did feel like hackforces after all...
but it's mathforces(div1b),interactiveforces(div1c) and datastructureforces(div1d)
I hope we don't have to code lyrics
Congratulations on your first album, Skyglow!
a Chinese word "New Be" is able to describe this
lol
MusicForces Round?
if I bought your album, could I be expert?
You will be losing money
Wow, I personally prefer clean singing, but this songs are really good. The riffs in "Thousand Years of terror", "...And the circle closed" and "The limitless Fog" are just awesome. Hope the problems be as nice.
Losing Humanity is definitely Div1E.
By the way, both 500th Codeforces round and 50th educational round will be held quite soon. Sounds like a big anniversary for Codeforces. I wonder, whether it will be something special. Personally, i hope that there will be 500 T-shirts for top 500 participants xdxd. Or at least 100)
Codeforces did not give prizes for (Div. 2 only) contests. At least from the day I joined (1 year ago). But I hope they do.
Are there programming contest related songs in the album?
Yes, of course, in fact every song from the album is a subtle metaphor about a programming contest
Are there any hints in your album?)
That's a preeeettty lucky day for a contest
What about a competitive programming group.
Competitive programming interview questions? Are you applying for codeforces or something?
Lol what did you just say? read up about algorithms, and data structure, then you can call stuff by their name, and have an actual chance of passing these interviews.
What's wrong with competitive programming :( But yeah that first post is advertising, it doesn't belong on this blog...
i found my twin with down votes .. tzuyu_chou
You are far more ahead of her in disturbing people.
Too pretty to be your twin
I was always interested in how do you choose amont all authors of the contest the one who will post the announcement. The one with lower contribution? Or simply by tossing the coin? How it is done generally and how it was done in this round?)
We chose the red one, of course, people love reds. But really, SirShokoladina worked on the contest the most.
Can you guys please do a Despacito cover?
I wish to have a CD. How can I get one ?
Just send me a private message
Auto comment: topic has been updated by SirShokoladina (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем SirShokoladina (предыдущая версия, новая версия, сравнить).
tzuyu_chou Honestly, it was really a smart way to advertise. I couldn't resist me from watching it. And it's good.
Wow, I might get a salary boost because of this! Thanks for letting me know.
P.S. I learned this advertising trick from JYP. Go on forums and make sure your comments get either a lot of upvotes or a lot downvotes, as that will attract a lot of attention!
Is it necessary, if you have millions of views?
20 millions of views is not a limit
How many views that trick on codeforces add(briefly)? I think it much less than 20M
You can't be lazy (maybe that's why you're not in div 1). Every view counts.
Probably all Red coders will get the CD '_^
Here is a challenge:
Compete in this contest, while listening to some death metal music :P
That actually improves your performance, Prog metal is much harder to listen to but it has the same effect (even better) if you get used to it (at least for me). So here's a harder challenge : try listening to some Dream Theater during the contest, see how much can you take. (start with Dance of Eternity)
I am also a prog fan, but never thought about it....
it looks like you are a real PROGrammer :P
Does it work with Fates Warning as well?? You know I love Dream Theater too, but I prefer Fates Warning, Skyglow here has a lot of progressive too. For me Death-Metal works better, or in a more general sense Extreme-Metal. Is nice to find Metal Fanse here. By the way your nickname is a Masterpiece if you know what I mean.
It works with whatever you like. and sure, Powerslave is one of the best metal albums ever. Iron Maidens is a God to me.
Seventh Son Of The Seventh Son is my favorite Maiden album, I wish I could watch them play it alive someday
Actually I did, but not just Skyglow, there was som Emperor, Annihilator, Amorphis and some more stuff on the playlist. Although I have to add, the I only listen Metal while I'm not focusing on hard problems, you might guess that my playlist stopped at minute 27 when I AC problem C :P
So cool, you guys!!!
Wow, I didn't see this review. Thanks!
That actually quite nice. Didn't expect to actually enjoy it because I usually hate the screaming. The musical accompaniment kinda reminded me of the whole Touhou metal variation culture that I'm very fond of :)
Losing Humanity has some clean voices, for me is the best song of the album.
Wow, if it comes to music, there are many well talented people on CF. budro, fast, it's your time to shine!
What you'd say about sending CDs to people who solve only problems C and D, apart from the top10 criterion? SirShokoladina
Not many people would want to receive a CD. I don't want to waste CDs on people who don't want them. Besides we can only send 10 CDs. Also I want every contestant to be able to win a CD, not only reds and yellows.
What's wrong with tourist's contribution ?
hidden +18
Probably the first blog after Tourist's "Hello 2018" with this much appreciation.Hope the participation would see similar levels.
This is the most use of odd time signatures I've seen since Meshuggah and perhaps Tool. Definitely feels like the songs are written by a red coder.
Ha-ha, thank you! Yellow, actually. I am glad someone marked this feature.
Really liked the song "Losing Humanity".
OMG! 1000 upvotes! Congratulations!!
Why did I not get "Congratulations" for 250 downvotes?
hahahahah .. i reached -100
OMG! -100 contribution! Congratulations!!
After this comment it's -99.
Auto comment: topic has been updated by SirShokoladina (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем SirShokoladina (предыдущая версия, новая версия, сравнить).
Your album is an amazing for people who love listening metal! You helped me to update my playlist)
I think this announcement has greatest Upvotes :)
Well, not really.
That's great you're gathering success as music band! I'd like to appreciate your work but I kind of hate music, so maybe you can record few minutes of complete silence, so I can actually enjoy one of your tracks?
A CF on Friday the 13th, May the Gods be on our sides...
I will try to become expert in this contest. :)
Typing contest because of Div2-D
C is like 1250 while D is like at least 2750.
A,B,C,D all had some typing/explanation problems. what about D?
unbalanced problemset
yes abc<DE
problem A is simple but hard to read it Wrong Description (10 20 30 40 -> 20 30 40 10) ans = 3 not 2 Somebody submit solution late because of it and have low rank in problem A problem B is very difficult Why not call it CodeSpeed round ?
Yeah you r right i was confused too at first sight
I think it's very frustrating to get a lower rating because of unbalanced problems and wrong descriptions
Wrong description is truly embarrassing but unbalanced problems, is not the case always, so for someone really trying to work hard on problem solving will surely have a good time.
A side note, I also see my rating going down in today's contest, but hell, loved the fifth question. Really enjoyed the contest.
Problem statements are not clear and difficulty difference between C and D is huge.Lots of announcements.
With 1 hour into the contest and no AC solution to D and E (Div.2), one thing can be said for sure that this round was just about fast solving A, B and C. Surely, this contest was way below my expectation, specially after the cool music theme and 1000+ upvotes on announcement :(
"All that glitters is not gold."
This is why I never vote on a contest announcement until I've seen the problems.
Wake me up when someone solves D in div2 :P
Bump. Someone did. :P
Sorry this contest put me on team K-Pop
Looking at how people are reacting to this contest, it is obvious that their main purpose of preparing this contest was to promote their music. Not that I could actually write any problems (much less prepare a contest), but they should've just not wasted 2 hours for many people.
My advertising, on the other hand, only wastes a few seconds, as it just requires people to look at my comments and downvote them.
Really bad problem set...
Problem statements very unclear.
A, B, C — very easy, thus typing speed checking contest.
D, E are way out of league for Div2 users.
Solve problem D in Div2 and you'll be a CM.
Also I usually save my vote for the announcement and give my vote only after seeing the problem set. I give you a downvote SirShokoladina.
Or, Solve problem B in div1 and become Master.
At least i tried
I solved A B C in 17 minutes and read statements of problem D. Now I can't still understand what D is saying.
Lucky you, I'm still at the first sentence in D
You may be good at singing but you're definitely not good at preparing a contest.
Too bad I already have up-voted your blog and I can't down-vote it now!
thats why i never upvote before contest.
Is it the first contest in history of CF which has had an announcement for an (wrong) announcement?
Yes, my bad this time. Sorry about it.
See, arsijo only learns to be a coordinator. Sorry for unclearness in some statements and disbalance in difficulties, we will work on it!
oh I'm sorry. Didn't wanna bother you. As long as so many rounds are coming one after the other, I'm grateful to you and CF. Mistakes are totally okay.(I guess).
I think the contest should be rated because mistakes happens in any contest and it was just a problem has mistake but all other problems were fine
It is not normal when nearly 3000 people solve ABC so fast and so few people solve D or E. I believe that next time problemsetters will be more careful with tasks.
Why would the round be extended for 10 minutes?
So we can finish with reading last two problems
maybe we have more time to hack!
maybe to decrease the difference between the number of submissions of C and D!
Maybe we have more time to get Unsuccessful hacking attempt back :(
They focussed more on promoting their music instead of preparing problems for this round.
Kind of the worst Codeforces Round, but, hey, at least you tried!
The extension will only extend my suffering
For Div. 2:
Much difference between expectation and reality..
Solve [D]
Runtime error
What's intended complexity for Div1B?
I had log(#divisors)*(#divisors) per query but with huge constant so didn't pass
still 5 mins remaining for the contest to end!
I have O(1) per query (more honest — O((2k)k * 2k) where k is number of dimensions, k = 3 for this problem).
Can you please explain your approach for the problem!
I would like if someone explain my approach to me, actually...
My solution is O(1) per query.
Calculate A[i] = number of divisors in mask i for the venn diagram (https://en.wikipedia.org/wiki/Venn_diagram) of the divisors and do a bruteforce on the possible combinations of areas from it. Turns out there are 51 possible combinations of areas for it so you can just precalculate them and pass through them doing simple combinatory.
A contest with announcement on every problem. Announcementforces round
The div2 round is completely a garbage. The problem DE in nearly unsolvable, while ABC are div4 problems. The pretest contains only examples. I cannot complain more.
Exactly like last div2 round...
This is the longest Announcement list I've seen so far!
I think K-9 is cheating
Can anybody explain how to solve E.
There will be a tutorial soon. The idea is that you maintain three rectangles, where you think the answer might be and decrease their sum square exponentially.
Disappointed.
Almost O(N^2) solution passes for problem C! 40274533 Tried to hack it with this test and it still passed in 1.5s
That really doesn't make sense to give 2s for such a problem!
Passed the pretests doesnt mean it passes the system tests
I meant for this hack test it still passed in 1.5s that's why I'm saying 2s is too much for this problem cuz such solutions will pass
generally, pretests include small test cases and for these tests maybe 1.5s is expected for that hack.
Maybe pretest doesn't include this test case.
I have heard song after solving A,B and C. xD
Semi-rated?
KKKKKKKKKKKKKKKKKKKKKKK so real
you should see problems B,C,D,E in div_1 :))
How to solve Div.1 C?
how to solve div1 B,C,D,E ?
A very tough contest indeed !!
That was pure shit!
Very Hard C, D, E!
The most difficult problemset of div1 I've ever seen!
My logic in Div2 D.
Sort the 3 numbers A,B,C. Get all factors of A, B and C in a sorted order. For each factor of B[i] find number of factors of A less than or equal to B[i] and number of factors of C greater than or equal to B[i] using binary search.
Then multiply these two numbers and add to ans.
But got WA in test case 3. How can I modify this to get AC or this is a wrong logic (I am probably not counting all triplets) ?
this is rather wrong logic
For paving we have to make sure the corresponding dimension of the smaller parallelepiped divides the corresponding dimension of the bigger parallelepiped right? This is why I used factors and then to make sure
a<=b<=cI used the binary search."the corresponding dimension of the smaller parallelepiped divides the corresponding dimension of the bigger parallelepiped"
I think the problem is in this assumption. Since you can rotate the smaller parallelepiped, the numbers a <= b <= c don't necessarily divide A, B and C in that order, for example you could have: 'a' divides C, 'b' divides A and 'c' divides B. The statement in fact contains one example of this, saying that a 1x5x6 block can be divided into 1x3x5 parallelepipeds (1 divides 1, 3 divides 6, 5 divides 5).
Two clearest things to point out: your answer might consists of duplicate pairs, also not only divisors of B can be at the middle regarding numbers' absolute values.
Not "the first" in everything turns out good, actually.
I appreciate your work (both music and CP, though I'm not a huge fan of Death Metal anyway xD); however this contest has some issues. Most known are D1B/D2D incomprehensibility and its spike over easier tasks (haven't read D1C and above, so I can't comment further xD).
Also, having a lot of additional announcements is something not so nice. You might consider simulating yourself in more varied perspectives so that you can have a wider overview of what being clear and what being vague ;)
Thanks for the kind words. We are sorry.
for div1B, what is the correct output for 6 10 15
it is 50, right? edit nvm I'm wrong its 51
My AC code gives 51. Now I'm scared.
Same here xD
correct answer is 51
it's 51, my bruteforce says
This gives 51:
51 obviously
Ok, something weird happened to me on C.
I had Idleness Limit Exceeded with one program. Then I added an assert to two places and got RTE, so the assert is obviously the reason for RTE. That's all well possible, but then I took the code with asserts, hardwired "choose random a and b initially" and a checker oracle "choose a random true answer" instead of I/O. And stresstested with tens of thousands of tests, various random and non-random N. The assert is never triggered.
Is there a bug in the checker? In my hardwired checker? Does my code fail on a strange corner case (specifically: on pretest 1)? Something else?
(commented out parts are from the original RTE submission)
i saw your solution. it runs into an infinite loop on the sample
I know where I made a mistake after going though the sequence of expected answers now... It has nothing to do with any of my thoughts during the contest, I mentally reversed the inequalities in answers (answer 1: the correct number is smaller than the queried number).
What a shitty mistake. The worst thing is that there was no way for me not to make that mistake — when I read x < a, my mind automatically goes to "meaning of random letters: the true number is on the left and the queried number is on the right" because it's the natural notation for me and that's precisely why I can't realise that's wrong too... if it wasn't a, b and x, y but something like qa, qb, I'd probably notice.
Yeah, I agree, I also made this mistake but luckily caught it when trying to run the samples by hand.
I think it would have been better if x and a were replaced by words, for example "the x-value Vitya guessed", "the x-value Vasya is thinking of".
(okay that doesn't sound that good, but I'm sure there is a better alternative.)
EDIT: better alternative in comment by Xellos
+1
I had to stop ~15 times for a second and think again what the condition means (which side/way it is).
v1, v2 and q1, q2 would be fine. Variable names being self-explanatory also means there's no need for a tl;dr explanation.
I agree. The notation was confusing :(
the interactor is determinate, so it gave you the same answer each time.
How to solve div-2 D or E?
ecnerwala are you guys streaming today?
No, we're busy after the contests on weekdays. We'll try to stream most of the weekend contests though!
Let's start a really long discussion now. I was able to solve div 2 B using simple O(n) implementation here but looking at the round I am still not sure if it'll pass the system tests or not. I solved div 2 A after somehow understanding the problem but my solution got hacked. I still don't know why test case of "nz" should print "NO". My submission is here
Because there is no vowel after z
Good news for D2B — your greedy O(n) solution is correct! :D
P/s: I solved B that way as well ;)
yay! finally something good happened in last 2 hours for me!
Почему ML в задаче может быть 768 мегабайт, а в запуске только 524288 КБ? Это сильно усложняет тестирование на TL и ML в запуске.
Hello K-9 can you explain this?
We can wait for K-9 's response
I think that K-9 has two (or more) codeforces accounts, and he just register with all of them in the contest, and by chance he's in the same room with one of this accounts, so he hack himself 9 times :) you can observe that the solution of K-9 and the the solution of Eagle-EYe have the same header ;)
If this is the case then :3 he should be skipped from today's round.
Cheaters should be burn at the stake.
the round was rated for him...
Funny，he's in the same room as mine. And I see how he hacked Eagle-EYe's. At first, I sympathize with Eagle-EYe's very much, until I view his code..= =
Очень жаль, что о продлении раунда решили не предупреждать
Было же оповещение (в 19:15:23)
UPD. Оказалось, что только для div2, упс.
I don't care if I get downvoted. This was one of the worst Div-2 contests I have participated in.
Contest is hard and very bad.
Is the title and the description of div2 D incorrect? I still didn't understand the problem.
Pave: cover (a piece of ground) with concrete, asphalt, stones, or bricks; lay paving over.
What does it mean to pave a parallelepiped?
The problem asked you to count the numbers of (a, b, c) (a <= b <= c), such that (a, b, c) are divisors of (A, B, C) or (A, C, B) or (B, A, C) or (B, C, A) or (C, A, B) or (C, B, A), respectively.
So parallelepipeds (A, B, C) is the same as (A, C, B) but rotated? [I think rotating (A, B, C), where (A != B; B != C; A != C) won't produce (A, C, B)] (1×5×6 can be divided into parallelepipeds 1×3×5) but this tells me I'm wrong.
Or maybe its even more complicated than that?
I was thinking about it a bit, but probably am just wrong or misunderstood sth.
just think of it as a 3d rectangle, a box. Then "to pave" means "to fill it" so it's full. You can fill a 3x3x3 box with 27 1x1x1 boxes, or with 3 1x3x3 boxes, or 3 3x1x3 boxes, etc. Note that, in the task, you can only use boxes AxBxC that are A <= B <= C, but rotation is allowed, so a 9x1x1 box can be filled with boxes of 1x1x3.
Please make the round unrated for those who got "Idleness limit exceeded" in Problem C because of sending too many requests.
It was explicitly stated in the statement that sending too many requests leads to "Wrong Answer" and printing nothing or forgetting to flush the output leads to "Idleness limit exceeded".
It wasn't until almost the end of the contest that the correction was made.
Some contestants may have spent huge amount of time looking for errors in their code that matched the verdict("Idleness limit exceeded")and couldn't find any mistake related to I/O and therefore couldn't compete in the contest normally.
Please look into the issue.
Im afraid that you div1 public commenting by fake account. afraid of downvote :p ?
I don't see how downvotes matter? (other than it makes the comment hidden — which will also happen from the the fake account)
I think many share the same trouble during the contest so I don't want to make this only about myself.
It happened to me, but then again I could not have solved D anyway and A,B and C were done. So I can't complain. But I do consider that it would have been the case with Div 1 users.
Hoping for a contest with less math soon
Agreed. But CF is famous for its math tasks, and many people like that?
one should enjoy maths problems .
If only your target is to learn math deeply. I enjoy programming and involvement of mathematic observation but pure hard math annoy me because I dont know much.
then when will you learn new and hard things ?
hope you know many red coders are either imo medalists or won some medals in prestigious maths competition !
But point is we newbie public are not medalist :p we want to learn data structure, graph, string and various algorithm. Many of us not willing to compete in IMO.
Although div1B was way harder than ussual, I really liked it, actually, thanks.
Why does this solution doesn't work for E? I first guessed the value for x, once I get that, I guess for value of y. I don't think this will exceed 600 requests. What am I missing here? anyone?
You should probably put your code in a spoiler tag before the downvotes come (also it's neater)
I tried to do that, the dropdown just doesn't appear. It's like the drop-down to select spoiler is hidden behind the text box.
"this suggest we got x right" — but it doesn't mean that.
I mean, if the response is random for the case when more than one condition satisfies, then it fails with probability —
1/1024. What if I increase the threshold forcnt2?Where does it say it's random?
Thanks, I got it now.
The interactor can just keep printing out '2', indicating that your y value is less than the target, and you'll never find the correct x value. When you input '2' while searching for x value, you don't change your outputted query at all, and the interactor is free to keep outputting '2' regardless of the correctness of your x value.
Thanks, my mistake. I assumed that in case of multiple conditions is true, the interactor's output is random.
Very unbalanced contest. C solved by 3000, D by 21? Was it difficult to predict when making problem set...
Wait for the system test and you will find out that the number of solutions for C is far smaller
How do you predict this "far"? Not much hacks on it, I predict only less than 10% to fail systests.
I don't get people that just write "stupid contest" without any extra explanation ("I did poorly" isn't a good explanation). Maybe you think problems were way too hard, or e.g. 3 of 5 problems were on a similar topic, or the statement was bad — but then write it and maybe the next contest will be better.
My complain: remember guys that "either ... or ..." means "xor", not "or".
How to solve E? It seems to be extremely hard.
where is "either ... or ..."
EDIT: ok, makes sense
It was in the initial statement of C in the description of the response 3. I was confused about it, asked a question and they removed the word "either".
It was in the statement in the beginning. We are deeply sorry... Someone changed it that way and we did not check.
Keep "deeply sorry" for bigger issues :D that one was a detail. Cheers.
Yes, this is just a quote from South Park :)
Also, I recommend reading emails from Polygon about every commit in your problems. I always do that and then I can't miss a bad change in the statement.
Well, I saw it, but I did not pay much attention. Someone just clarified a statement a bit, but made this mistake.
Also, I enjoyed the first 35 seconds of the first song in your album. Then the actual song begins :D
35 seconds < : A,B,C
35 seconds > : D,E
My complaint would be that a, b and x, y are very random names for "correct numbers" and "queried numbers", which led to me misreading the problem statement of C (on every re-reading too). There's nothing I can do to avoid making that mistake again, either.
What is not good in this round:
Unbalanced difficulty (B is much harder than it should)
Issue with problem statement in A (the phrase "the number that Vasya wants to maximize equals 2" confused some contestants, and the fact that ranks of contestants depend mostly on speed of solving A worsen the issue)
Issue with problem statement and annoucement on B.
i don't understand , why some complain of hard contest , rather than thinking whether it is hard / easy one should think on problem and how to solve it . if not solved wait for the editorials and learn the things where you are missing .
hard and unique problems will only teach you something.
MikeMirzayanov
It won't be an issue if the points were not based on time. The real problem is that a difference of few points causes a huge difference in ranks.
In that case, what's the point of having problems Div2.A~C? Why don't we host a contest full of Div1.E problems and make the contestants learn much more and much faster?
How do we solve Div 2 C in O(n)?
You need to sort it which is O(n log n0. Then there is a greedy solution, you can take the largest number from its place and put on the largest possible smaller number's place and then consider the next number.
Let's get all sizes of groups of equal numbers (using unordered_map). All sizes <= 1e5, so we can sort (O(n)). Answer is the cyclic shift (in sorted array of number). For all values of cyclic shifts we can calculate answer using sorted array of sizes.
You can't , sort is needed .
hashmap :)
EDIT: Ignore it, it's the solution for div2 B, the thread is meant for div2 C.
< ignore >Yeah you can, check out my solution here</ ignore > :)
You are talking about B! But they are talking about C.
Thanks!. I edited my comment
40264790 like this
That's a n log(n) solution btw . the access to an element in a map is done in log(number of elements int this map) , now consider all the elements are distinct.
he could used unordered_map instead .
can someone provide an explanation for this solution?
EDIT: thanks, understood
I thought it was n — (the largest amount of numbers that are all the same). So 1 2 2 2 5 is 5 — 3 = 2 because there are 3 2's. However, I kept getting WA on test 3. Can anyone tell me what a counterexample to this approach is? I spent so long, I even wrote down a detailed proof on why it was true, and the code was very clean, so I have no idea what my mistake was
That is indeed correct solution, so you have some bugs in implementation
Yep, after seeing the test case, I found out why...
Apparently in java Integers can't be compared with ==. (auto unboxing apparently doesn't work as great as it sounds)
This is good to know, I don't feel so bad about being stuck on it any more, what a subtle bug! (Especially since, they are apparently stored slightly differently for small integers, so when I tried like 3 1 3 it works but if you add some zeros it breaks) (And I was only using Integers so I wouldn't get TLE because of java using the slower sort algorithm... turns out it backfired D:)
Well, unboxing works exactly as advertised, there is just no reason to unbox 2 Integer instances compared with ==
That's absolutely correct. I didn't think of this, but as I read this now, I realize how the logic i used will be reduced to this. Nice!
This is probably the coolest round in Codeforces. :D :D
Ha-ha, thank you! I'm glad at least someone liked it.
Actually, He is being sarcastic.
Anyway, the contest was not that bad as many people think. The first 3 problems were kinda easy, the fourth one was not of my taste and a bit boring but is acceptable. The binary search tweak in the last problem was very nice.
Что с системным тестированием?
no one solved 5/5 of problems in both divisions !! rare to happen :|
becoz those who have the capability of doing this were not competing today ..
hope you know , whom i am talking about !
i see you did not participate in this round ..
i know .. i know
HaHa, I know the answer now.
Am I in hackforces round? -_-
i did 2 unsuccessfull hacks .. moved from 600 -> 1200 :(
It is unbelievable to see that there are 3 problems more the 3000 one had solved it and another 2 ,one of them 20 but the other is 8 (just passed the pretest)
all of we agree that was unbalanced problemset
also I think rounds like this is very very unfair for the participates and don't show their skills
Why system testing not start ? ://
rembocoder
SirShokoladina
You can't run systest if you don't have any systests. Just saw the pretests
there is some participants solved problem D and E. so it's ok for the contest to be rated just my opinion
Solved A B C in less than 15 minutes after thinking a lot about D try to hack locked my A problem and it got hacked :( .Atleast D must be of somewhat less difficulty so that we can save our rating.
Its not all about ratings bro. If you deserve them your points will come to you. So just enjoy learning new things.
I am not complaining about the contest but atleast test cases must be strong if they want to check the speed.
i think this contest deserves to be evaluated as "a bad contest" not only because of the difficulty, but also because of too many corrections made during the contest. idk if the writers know (because they are kinda red or yellow or purple coders), but people like me, who are not as good as the purple or above guys, need to read the problem and given examples 'very' carefully because we are not able to come up with the solution as soon as we read it. then what would happen if there is a clear fault in the example or hint? this really matters.. at least for me. i always want to thank for guys who write problems for people, but i hope in the future they try their best not to make these kinds of typo made today.
Apart from mistakes in the statement it was not that bad.It was a good contest i think.We should agree that we could not solve D and that's all.
when does system test starts? I want to sleep...
My grammar bad... Sorry :)
SirShokoladina && rembocoder why you have same prefix -Sir- !!
get a life -_-
.. and suffix -dina XD
When will system testing begin?
only 18 solved D and 0 solved E?
When will system testing begin?
Автокомментарий: текст был обновлен пользователем SirShokoladina (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by SirShokoladina (previous revision, new revision, compare).
The contest was just bad on the term was div2C had 3000+ submissions passing pre-tests while div2D had mere 21 and div2E didn't even enter 2 digits. Otherwise, it was an awesome contest, D made me brainstorm and even though I could not solve D(wasn't passing examples on my system), I got a list of items to learn by the next contest. So a real tough contest, not always though, is actually fun.
*Waits for System Tests to start
*Dies.
They are still thinking about making this round unrated or not.
I am confused about one thing. If a contest is tough, how would your ranking differ? Because if someone is solving it faster than you, then he/she would have solved easier question faster than you as well. I think the question as good. Though couldn't solve D and E, but it was a fun hour crying, thinking and again crying about the questions. Well, really looking forward to learning something really cool from the editorial this time, again. Sorry if offended anyone.
Well, since most people can't do problems D&E, there are only 3 questions and it comes down to speed. So there is a lot more deviation in the score and people who are usually 100th place plus or minus 50 and now 100th place plus or minus 300 (though obviously they can't get minus, so it's just worse for them). I think in general your expected position may not change too much, but it's much more luck-based.
Also it puts emphasis on solving fast rather than being smart, and if you get hacked on 1 problem you go down like 2000 places.
Imagine if you are taking a test in school with 3 easy questions and your grade is based on how fast you answer them
tzuyu_chou == TWICE_OVER_SKYGLOW ?
Of course!!!
Does anyone know what is the worst-case behaviour for the following two solutions for Div1 C?
At all times, the set of the possible answer pairs is an L-like shape. (Or a rectangle, which can be seen as a degenerate L-like shape.)
First solution: ask for the midpoint of the segment connecting the big right angle and the concave angle of the L-like figure. Update the figure according to the answer.
Second solution: if the figure is a rectangle, ask for the center of the rectangle. If not, divide the L-like figure into three obvious rectangles, and ask for the midpoint of the larger side of the middle rectangle.
I feel that the second solution should be much better, but I keep miscalculating and cannot obtain the maximal number of steps for any solution.
In my opinion problem D1B was horrible. The coding part (finding number of divisors for A, B, C, gcd(A,B), gcd(A,C), gcd(B,C), gcd(A,B,C)) is trivial and after that you have hard extremely annoying inclusion-exclusion case-handling. For comparison, look at this recent combinatorics problem that involves no case handling, and has a very elegant solution.
Even though I did very badly I wasn't affected by the issues in the round, so I don't think it should be unrated.
C looks like a cool problem, too bad I didn't have much time to spend on it.
I really liked that recent problem.
For B, I have a solution using Burnside Lemma and inclusion-exclusion principle, no case handling at all (hope that it will pass systest).
My submission
If it's not too much trouble, would you mind explaining your solution a bit more?
I'm really not seeing what sort of action is bringing Burnside into play here.
In this problem, the Burnside lemma turn the problem of counting the number of triple (x, y, z) that x ≤ y ≤ z (unordered triple) satisfy some condition P to the following three problem:
Count the number of triple (x, y, z) that satisfy the condition P.
Count the number of triple (x, y, z) that x = y and satisfy the condition P.
Count the number of triple (x, y, z) that x = y = z and satisfy the condition P.
Condition P in this problem is "it is possible to pave the given parallelepiped with the parallelepipeds x * y * z
Then I use the inclusion-exclusion principle to solve the first two problems (the third one is trivial).
Hi, would you like to tell me why you multiply the thrid count with two?
Because for a configuration (x, y, z), there is two permutations where x remain equal to y: (x, y, z) and (y, x, z)
I don't understand why the third count is related to x = y. Would you like to hear my understanding of your idea?
In Burnside lemma, we want to find the fixed point of the 6 permutations 123, 132, 213, 231, 312, 321. For 123, it is exactly what your type 1 mean. Your type 2 is 213 which has the same value as 132 and 321, and that's why you multiply it by three.
For your type 3, there are two remaining permutations 231 and 312, and that's why you multiply the gcd of all three numbers by two.
Then the answer is the sum of them divided by 6.
Would you like to see whether I have a correct understanding of your code? Thank you very much.
Your understanding is correct.
Thanks.
Could you explain the masks you have used please?
editorial?
http://codeforces.com/blog/entry/60572
Is it rated? No jokes btw/
Yep. Systests are going on.
For Div1 problem D (1007D - Ants), why was M so large at 10^4? What is the intended complexity vs. the intended-to-TLE complexity?
From what I can tell, an M^2 log N solution will definitely TLE, whereas an M^2 solution will pass or TLE depending on constant factor. However I really don't think constant factor should be an important part of these contests.
It's so disappointing in problem C to get "Time limit exceeded" on test 31...
Make Rated ! Codeforces again turned to Hackforces !
Hey, I haven't slept yet and it's 4:00 AM in my country now.
The only reason being that I am waiting for seeing if the round will be rated or not. I think you have had enough opinions from the community to be able to come to a decision.
ohhh you did not participate why you still wating>?
Was waiting for you to reply to my comment. And since now I have that, I have achieved everything I had dreamt of achieving in my whole life. Now I can rest in peace. :P
@SirShokoladina rembocoder arsijo
During the contest, I tried to hack this solution for div2 A with input as "ae".
http://codeforces.com/contest/1008/submission/40270051
I got the verdict as YES but actually, the output should be NO which can be verified from main tests as the same solution fails for the main test 23.
Am I correct or not? If yes, should I get the hacking points for the same? [submission:40270051][contest:1008][problem:1008A]
"ae" gets "Yes", it is correct.
What's the problem? Test 23 is also "Yes'.
But according to code, it should output NO like Test 23.
Please see this line in the code:
if (!flag['a' - *(s.end()-1)] && ... )Here program is accessing flag['a' — 'e'] which should return false and hence making if condition true. So, it should output NO.Same thing has been mentioned by me in "Ask the question", but as the round has ended, I am unable to reply.
I think u'r right.The code u mentioned should be
if(!flag[*(s.end()-1)-'a'] && ...).The hack should be successful.My mistake today:
a. I started 3-4 minutes late.
b. While coding the second problem, one of my laptop keys fell off. Coded it after getting external keyboard and wasn't comfortable typing in it. :(
Will, you post the names of the Winners of the CD. I would like to be on the list. :P
how to solve div2a?
You didn't check the last litter. Your solution gives WA on test 10 — "b".
thanks
When will the editorial be published?
https://codeforces.com/blog/entry/60572
Auto comment: topic has been updated by SirShokoladina (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем SirShokoladina (предыдущая версия, новая версия, сравнить).
?detaR tI sI
Why did my code of div1C which used "exit(0);" get "Idleness Limit Exceeded" in pretest 12?
Кто может предложить более короткий(чем 22-й) контр-тест для моего решения задачи Div2B? http://codeforces.com/contest/1008/submission/40273084
Понял, спасибо.
Когда разбор?
уже есть
В материалах соревнования его нет, в этом посте тоже....
Все, увидел в материалах див1. Спасибо.
ooh, I also wanted your CDs I liked it very much, but I thought that you would send your CDs participants with high scores. I have +116 at this contest and I won't get any CD :( . Anyway thanks for the good contest :) .
Well, we may send it to you if we have one left. Tell me your address in private messages.
Auto comment: topic has been updated by SirShokoladina (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем SirShokoladina (предыдущая версия, новая версия, сравнить).
Hackforces
This looks like cheating!
Upd. Missed that in comments above. Sorry
?detaR tI sI