Hello, everyone! Codeforces Round #292 will be held at Feb/17/2015 19:30 MSK. We're looking forward to your participation!
The problems are from dreamoon_love_AA, and thanks Shik for some discussion. Also we want to thank Zlobober for helping me prepare the round, AlexFetisov and winger for testing this round , Delinur for translating the statement into Russian, and MikeMirzayanov for Codeforces and Polygon.
This is first time I provide all problems for a Codeforces round. I hope you'll find it interesting! Please read all problem statements and discover what the main character drazil do in those problems for he's really cute =)
Finally, I would like to ask sorry_dreamoon to participate this round. I believe everyone have the same curiosity as me about your behavior in Dreamoon's round =) May I have the honor of inviting you?
Update1 : Because problems of this round are hard to determine their difficulty, We will use Dynamic score for this round. Then the order of problems is from easy to hard by sense of me and testers.
Update2 : Due to technical reasons we have to move round on five minutes.
Update3 : Congratulation to our winners:
Div 1:
Also, special congrats on rng_58, who solved problem E in Div.1, which anyone else could not solve.
Div 2:
Between them, EarthQuito is the only person who solve all problems!
Update4 : link to editorial
I think it will be great, I agree with sorry_dreamoon :) Best regards.. Ibahadir Altun ..
I have a little doubt, dreamoon_love_AA is man or woman? :)
Is it matter?
No, but it is a question that I have for some time
Ok, I don't know :)
RIP english
he's a man :D
I know of course :)
i'm you :D
Me too! Me too :D
We are all mokhlesane jenabe Haghani
I'm man, definitely >_<
Don't take it personal please.. I'm sorry, I definitely know that you are a man.
ok , definitely resolved
Yeah, definitely :)
So sorry_dreamoon definitely woman :P
Or definitely gay :P
a cute man,definitely! ↖(^ω^)↗
"[user:???] for translating the statement..." , I think you mean Delinur
and please pin this post in CodeForces home page so everyone can see it :)
[edit] fixed, thanks :)
Please allow tourist to change his handle to sorry_sorry_dreamoon for this round .
Am I the only one who thinks tourist is sorry-dreamoon himself??
Plot twist: sorry_dreamoon is already tourist
EDIT: Damn, I was not first :(
But sorry_dreamoon's solutions were written in Java .
Pretty sure that since tourist is rated 3200+ with C++ he would easily still be 2700+ with Java, even if he does not know the language quite as well.
I don't think it's very difficult for toursit to write solutions in different languages. For example in результаты, he wrote code in delphi, and won 3rd place in Div 1. I don't know delphi, but it looks like Java is much closer to c++ than delphi.
Trust me, when shifting from C++ to Java, you'll encounter many (from a competitive point of view) stupidities and need to find out how to skip them.
For example, suppose you want to debug and throw
return 0;somewhere in the middle of your code. C++ has no complaints; in Java, it won't even compile! Because you can't have leftover code after returns.Pair? There's none, write your own. Map? Which map? There are about 3 types. Vector? Possible, but ArrayList is a new version of Vector. Forget about using
[]in vectors (or arraylists), you need to use access/modify functions. Which arguments are passed to functions by reference? Not to mention having to throw some exceptions.A lot of these things make sense from a development point of view (the absence of a Pair class does not), but are unnecessary in contests and definitely take some time to learn. Nobody would chug out a working code in Java on the first attempt.
Also, implying nobody but tourist can beat dreamoon_love_AA.
Hm it is interesting. Currently I use Java and am trying to switch to c++, and am having a lot of difficulty. Writing working code in c++ for me is very difficult. Just goes to show I guess that it depends on which language you learn first, since for me Java is far more intuitive.
I think Xellos is sorry_dreamoon ;)
I think you're throwing random guesses.
May be. Anyways, best of luck for this Div 1 contest. I hope u will participate ;) :)
He has aready said that he thinks that dreamoon_love_AA is better that him...
That would be incredibly hilarious given that thread: http://codeforces.me/blog/entry/15336#comment-202627 :D
Just say "I don't know Java"
so sorry_dreamoon is already petr :P
tourist can program in Java. you can see it in this link: http://codeforces.me/contest/482/submission/8394627
Do you think: 1-what does tourist do during the contest? 2-why does he register but don't Participate? 3-why is he online now,if he don't want to Participate in this contest. understanding it is easy: if he copy his code that submited with sorry_dreamoon's profile and submited it in onother profile (tourist) everybody understand that tourist is already sorry_dreamoon so he have to program in Java and C++ and it is a hard work!
of course sorry_dreamoon can program in C++ because he hack Mohamed.Bassem and randan's solution and both of them program in C++ but sorry_dreamoon program in Java! Who is sorry_dreamoon? it can Specified in the future for next contests... . ;)
you don't need to know other programming languages to hack solutions of different participants
you're right but for certain you must know other programming languages(of course if you have many time.)
Petr possibly be sorry_dreamoon , the program in java .
You possibly be sorry_dreamoon , the program in java .
very good joke , I have not the level to beat the dreamoon_love_AA , I hope someday JOINING to their level.
I wonder how sorry_dreamoon feels when reading all those comments considering whether he is tourist or Petr :P. My contribution to that investigation is that we can clearly exclude all participants from here: http://codeforces.me/contest/498/standings :D.
You aren't there!
Hah, yes I'm not. I said that we can exclude guys participating in #284, but if you will read comments, especially that one: http://codeforces.me/blog/entry/15336#comment-202611 you will learn that I can be excluded as well :). And all polish guys in generality :P.
I think we can narrow down the list of suspects to 5 after today's contest!!
It's definitely not Petr. I don't think he has the time to play games like this because of work + He never considers pure Div.2 rounds. I'm almost 100% sure that it's either tourist or YuukaKazami because though the code is in Java, their style is so damn similar (one letter variable names etc.)
Yea.. True. Not only that, both of them keep braces for single line if/else statements. Both of them have a single space after ; in loops. Both have same spacing for braces in general, single space then a brace. The only difference one could spot is the newline spacing between different modules in the programs, tourist does not use spaces/newlines at all, whereas WJMZBMR uses a single line to separate out different sections of the program(similar to what sorry_dreamoon did).... :D
Why not Egor ?
what about niyaznigmatul or Egor ? They are in a group of five people ( Petr, Egor, niyaznigmatul, Illyakor, mmaxio) from top 30 who use java . Illyakor and maxio participated in div1 284.
If it is a group of five users from top 30, I think the score of Codeforces Round 284 (Div. 2) may be higher. I think two or three users will be possible.
Because 3 minutes(147 seconds) for div2B and 3 minutes(183 seconds) for div2C(div1A) is an amazing speed for reading statements and coding if it is single!
Let's ask Mike about him and his IP address. And then ban him for using second account!
nice today!!!!
Would love to see dreamoon_love_AA and sorry_dreamoon compete in the next Div 1 contest. Lets see if he manages to beat him in a Div 1 round.
I'm dreamoon' for math!!
how it would have looked when dreamoon was blue,hosting a div1 contest!
Like this.
sorry_dreamoon reading comments:
How about dreamoon_fan? He (She) is 3rd place in the CF Round #284 (Div.2) :D
maybe dreamoon_fan is I_love_Tanya_Romanova :D
I don't think so. I_love_Tanya_Romanova participated in 284 div 1.
I guess everybody can distinguish my ugly style of code:)
Oh, come on, I think whoever he is, he is smart enough to adopt different style of coding for his fake account.
Something like
I'll just put a song at the top of my solution, and they will think that they know who I am...
Am I the only one who thinks YuukaKazami is sorry_dreamoon? :P
They use different languages.
Yes, but I recall YuukaKazami has made a few submissions in Java too. Anyway, it was just a guess :P
How about ivan.metelsky. Seems he also uses Java 7 constantly :)
/feeling like a real stalker
I don't think ivan.metelsky is that jobless :D
Same goes for Petr and personally, I think tourist doesn't really care.
Please rethink about your comment it might hurt YuukaKazami.
It is impossible. He has no time for this...
I see. Previously, this link used to exist. And YuukaKazami seemed to be a fun loving guy from the comments there. So, I won't find it surprising if YuukaKazami turned out to be sorry_dreamoon. But again, that is just a hunch because I am unable to think of any other top rated guy who would do this :D
imho cgy4ever
You are right, even that is probable :)
Oh well, sorry_dreamoon will not reveal himself unless MikeMirzayanov agrees to not block him for multi-accounting, which he won't. So, we are supposed to just keep guessing :P
Tonight YuukaKazami cgy4ever tourist I_love_Tanya_Romanova all registered div1.
I think sorry_dreamoon is a team
Only 1 participated :P
Writing solutions in Java and then rewriting them in C++ was really hard...
Jokes apart, it is an honor for me to see my nickname in this list along with such skilled competitors as YuukaKazami, cgy4ever, and tourist :)
You are a skilled competitors too! You solved 3700+ problems in Codeforces and participate in 122 contests so that you are an experienced competitor. Your rating can show that you are one of top competitors.
Therefore, you are a skilled competitor.
I'm pretty sure that sorry_dreamoon is Xellos. Or someone really close to him.
But Xellos doesn't write neat code!
I should prepare to get bashed by Xellos :D
Yeah, it seems I am wrong, but still who khows :D
Don't worry, he'll just post some image.
I don't have an on-topic one, so here's something random:
What, it's just a few cases. What's so hard about copy-pasting and manually editing stuff? :D (Although I had to admit I took a huge gamble with that code.)
UPD: Hmm, it's a 1000 point problem... so maybe it's not the one I thought it was when seeing the casework.
So you don't deny that sorry_dreamoon is your account? :D
I never did before. Well, not that I don't like to mislead, but no, it's not my account.
I can't beat dreamoon_love_AA in Java, anyway.
I don't think so. Based on rating, dreamoon_love_AA is better than Xellos. And sorry_dreamoon was very confident that he can beat dreamoon_love_AA (based on account name + comment on CF).
Not me >_>, I have already been banned once as I create multi-account to win a Div 1 Contest...
Hi!
I can't solve this зproblem. My code:
include
using namespace std;
int main() { int a, b; cin >> a >> b; int ans = 0; for (int i = 0; i < a; i++) ans++; for (int i = 0; i < b; i++) ans++; cout << ans << endl; return 0; } Please help
holy mother of formatting.
This type of code (and God bless that styling) is one of the reasons robots + computers are going to declare war against human being someday.
P.S: If it was a joke, please accept my haha.
Tomorrow night is Chinese Spring Festival's Eve, which is the most important festival to Chinese people, just like Christmas Day to western people. The Chinese year of the Sheep (or goat || ram || lamb?..) is coming, I want to say "Happy Spring Festival" to every friend on Codeforces!
Wish you a happy Spring Festival :D
Thanks ;-)
Happy Spring Festival...I think many Chinese students are busy preparing for tomorrow's big dinner and visiting their relatives, so the number of contestants decrease a lot.
Wish everyone a happy Lunar New Year!
It is my first Spring Festival's Eve with coding~~~ Amazing night!
Happy Spring Festival!
Happy Spring Festival
My first DIV1 contest, look like it would be a severe fight for me tonight.
Wish score distribution won't be DYNAMIC...
...and the scoring is dynamic, just as we all had not hoped D:
Because problems of this round are hard to determine their difficulty, We will use Dynamic score for this round. Then the order of problems is from easy to hard by sense of me and testers.
GL & HF to everybody!
its dreamoon_love_AA VS sorry_dreamoon Again :p
You should change the names on the back of the clothes~
3 hours before contest, good luck everybody, I'm definintely gonna be green after contest ends
Does peter50216 have any CF account?
Update: Oops, he is peter50216 on CF, I didn't know that.
deleted
too soon. No I seriously mean it, it's too soon.
It will be amazing to see if dreamoon_fan participates or not :D
hoping to get good rank in my 100th contest :)
Thank everyone this round was very interesting!!!
Can you tell me what is the difference between dynamic scoring and the usual scoring, please? I'm sorry if you find my question stupid :)
you can check this out :
Dynamic Score
Got it, thanks!
I guess it means the score of problems is determined by the amount of participants who solved this problem
Yep, you are right!
do you know what's the meaning of Dynamic score for me ??? yep you are right Div_2 again :D
There's only one way to find out who sorry_dreamoon is and this will work only if he is not very careful. Someone who works at Codeforces can determine the IP address from where he is logging in and compare it with the IP addresses of all other users. By this comparison, we will either get one particular user who always logs in from the same IP address or we might get a few users who log in from the same IP address (maybe behind a university proxy?). Hopefully, there won't be many International Grandmasters in the list.
This will work only if sorry_dreamoon is not very careful and doesn't use proxy servers (or Tor) to be anonymous on the internet (at least while logging into Codeforces with that handle).
may be MikeMirzayanov is sorry_dreamoon :)
Why does Div. 1 start 5 minutes later?
UPD: Oh! Div. 2 also moved by 5 minutes.
Thank you very much!
P.S. I just want +331 too =)
Первый раз пишу под Ubuntu, может кто-нибудь подсказать, как копировать/вставлять в консоль CodeBlocks?
нужно заменить терминал на обычный. ссылка.
спасибо
I hope the 5 minute extend will be the only technical problem today, dreamoon_love_AA is an awesome coder and I hope we will be able to enjoy his problems without any difficulties :)
I think sorry_dreamoon is one of the ITMO guy (by looking at his style of code) and my wild guesses are mmaxio or qwerty787788
Yeah even I guess that it could be more of a chance being qwerty787788 looking into the style of his code, even now he didn't attend today's srm and was just active 4 hours ago and the style of his coding looks way similar and yeah he didn't attend srm 284 and was regular for all other srms other than 284 , so chance of sorry_dreamoon being qwerty787788 is high :D :D :D
It would have been fun to the characters of the problems were dreamoon_love_AA and sorry_dreamoon
Guys, ABHISHEK004 and pranjuldb are cheaters. They are from my room. I want you to take a look at their submissions for A after the contest!
Почему в A div1 N <= 15? Есть решения, которые будут за линейное время работать, ну или, в крайнем случае, за квадрат, то есть N можно было спокойно ограничивать 10^3 или 10^5, но никак не 15.
Чтобы натолкнуть на неверные решения.
Можно, например, вместо строчки считывать long long. Зачем делать большие ограничения, если идейно задача от этого не изменится?
Да ладно, пускай задача А будет лояльной по ограничениям, она же А. Хорошие ограничения, чтобы желающие могли написать переборчик — 9886986, или же так — 9891585, или даже увидеть в ней несложную динамику — 9888532:)
It's time to back to the old color.
I think Haghani should change his handle to sorry_(sorry_dreamoon) :)
What is wrong with pretest #1 on problem B div2? I can't believe my solution didn't pass it.
Pretest #1 is the sample, the one which is in the task description
That's why I'm asking. My solution passed all sample tests on my computer. It's very strange...
Maybe you used freopen or ifstream or you read from some files(most of coders use input and output files and than, when they submit, erase that part of program)Anyway, it could be also something like you used dome variables which weren't defined.I can't view your source yet.
http://pastebin.com/SrNrsUaP
Use "Custom invocation".
I don't know what to say.The only strange thing is taht you used reserve with n and m.I think it would be better to use sample vectors or to reserve something like n + 10
The problem was that reserve() leaves the vector uninitialized. I should have used resize() which sets all values to 0. D'oh :-(.
what was the hacking test case for C(div2)/A(div1) ?
1
9
Answer is 7332
I've hacked 2 solutions with 1 9, but my solution is wrong too((((
I just missed your code. Was looking for this mistake, don't know how I overlooked it.
I missed your A also. Hacked Thandkou's code for the same mistake. Shit.
What is the mistake? I mean, what did those people miss so their solutions can't pass this test?
Maybe my last post as a purple coder this week :D
In DIV 2 A they were checking (a + b) % 2 = s % 2 where a and b can be less than 0.
In C they missed 9 case.
I don't know what I missed in B. WA on test 41 :(
ashish1610 u hacked two div1A problem just 2-3 seconds before I could hack it.
what's the answer ?
7332
Mostly just
4,6,8, and9, in case people aren't careful enough with which digits should replace them. (4is replaced by322;6is replaced by53;8is replaced by7222;9is replaced by7332. I think most people missed the9case.)and you're right, sir! ;-(
most people missed the '9' case because it was hard to calculate out :(
anyway problem set was great
Good bye Div-1!
You're not alone
Guys, can I join you, please? :D
No, you couldn't :P
Hahahahah, what a luck!!! :D
However, I think it is better for me to be Div2 until I become able to solve almost every Div2 D problem...
1700.... it's your fate not to join us... Deal with it!)
sorry_dreamoon is no.1 in Div1!
I think he/she can pass system test safely!
UPD: although he/she pass system test... It is surprising that so many FST on B, therefore, the score of B level up from 500 to 1000~~~ rank change!
Maybe he really is the Petr...
My life is ruined. I took less number of days in problem B of div2. Was hoping to become candidate master. But now my rating will fall. :(
Same here. Worst performance ever!
Me too, I only calculate n*m days
Was D div 2 a bipartite matching problem?
The constraint leads to topological sort, I guess.
I don't think so.That's why they want to know if the solution is unique.If you used bipartite matching, it would took too much, and also, you are unable to see the uniqueness.
No! It could (hopefully, of course) be done greedily.
and then you can flip all these dominoes "one forward":
giving another good configuration).
This greedy in my implementation was hacked.
UPD: I've got TLE with using set of free cells. Maybe there is way to know whether exists cell with single free cell nearby itself without set
UPD: Using set of pairs was so lame idea. I've got AC using queue. Thanks to mnbvmar
Your code is wrong then. I implemented the same algo and passed system test.
My code got Accepted. Maybe it was too slow (now I see some people getting TLE) or didn't consider some cases?
// Edit: balalaika: you can use a queue/stack/whatever. When you take an element from such structure, we just check whether we haven't processed it before. It is conceptually similar to a priority queue-based implementation of Dijkstra's algorithm.
I used the same idea, I had luck , because my code passed in 1.996 seconds I use a priority_queue<> how implement with a queue or similar structure for avoid insert and delete operation in o(logn) my solution is O(n^2 * logn) I want implement O(n^2)
Use queue of coords. Firstly push into queue all cells adjacent to exactly one free cell. Then while queue non-empty, you update table and if after that you've got another cell adjacent to exactly one free cell then you push this cell into queue.
If queue is empty and you still have free cells then output "Not unique"
Since queue::push() and queue::pop() perfomance for O(1) and each cell can be pushed no more than once you've got implement O(nm)
thank you !! that was overkill
Огромное спасибо за интересные задачи и такие возможности для взломов :D
Лучше контеста у меня еще не было!)
Has anybody solved D faster than O(N * Q * log(n))?
dreamoon_love_AA and me =)
It is possible to solve this task in O(qnα(n) + nlogn).
+1.
It seems that sorry_dreamoon's identification will remain a mystery
Problems were so so nice, that I was very upset then contest ended :(
sorry_dreamoon became 1st again!!!
He is so confident that... Is he a tourist ?
i'm so sorry man....
2nd again= =... because of so many FST for B... the score of B change from 500 to 1000...
минуты не хватило до submit C.
там ведь слоеные списки по min (x- 2h), и max (x + 2h), с хранением индексов, которые дают эти максимумы. Как обработать ситуацию когда одно и то же дерево дает и max и min? у меня была какая-то странность с этим.
Не очень понял, что за списки, но это задача почти в чистом виде задача поиска подотрезка с максимальной суммой.
Списки для ответа min/max на отрезке за O(1).
Рассматриваем значения 2h+х и 2h-х. Для выбранной пары деревьев ответ является суммой первого значения для правого дерева и второго для левого.
Дальше дерево отрезков с максимумами всех трех значений (2h+х, 2h-х, ответ). Тогда ответ для вершины при построении — это либо ответ левого сына, либо ответ правого сына, либо (если выбранные деревья в разных сыновьях) — сумма 2h+x справа и 2h-x слева. Аналогично с merge нескольких вершин при поиске ответа.
спасибо.
Only champions league can make me happy after such a lose :(
In time zone of GMT +8, the game start at 3:45 am :( sleepless night again
Same here, but still not so bad as yours. GMT +5
Очень красивая задача С (див.2) про факториалы! Спасибо:) Истинное удовольствие от анализа условия!
I solved 3 problems in div2.. My best record :>
of course, if I pass system test..
For Div2 participants, this round was a super hack round!!! Problem C was easy to hack!!
sorry_dreamoon : Petr or mmaxio or ilyakor or qwerty787788 or eatmore who in top 100 and didnt participant #292 and coding java
Yeah even I guess that it could be more of a chance being qwerty787788 looking into the style of his code, even now he didn't attend today's srm and was just active 4 hours ago and the style of his coding looks way similar and yeah he didn't attend srm 284 and was regular for all other srms other than 284 , so chance of sorry_dreamoon being qwerty787788 is high :D :D :D
and I think we can rule out Petr and eatmore the rest were active today :D
i think mmaxio
mmaxio and ilyakor participated in #284.
so then my guess is almost getting right it could be qwerty787788 :D :D
wow nice
You forgot Egor.
or he is tourist
He can code in java too
and He is good enough to beat dreamoon_love_AA
The problem C (div.2) is excellent! Very interesting and pleasure:) Thank you very much!
Div1 B must have been quite tricky...I think over a third of people submitted and failed system test on it.
Put the top 5 people in the announcement please :D
Now we know its not tourist. cause he is not first. :P
I failed the system test of problem B in div2... What is the approach like?
You need to traverse for some more no. of days.Traversing till n*m fails,but 2*n*m passes. It is possible that a girl becomes happy for some i~=m*n and then makes a boy happy sometime afterwards.
Does 2*n*m passes guarantee that it will have correct result?
I don't have the proof,can someone else help out?
running till (max(n,m))^2 days worked for me...
the value is (n+m-1)*n*m. the proof is pretty forward. for functions b(i)=i%n and g(i)=i%m, you have to loop n*m for all possible combinations of b(i) and g(i); as b(i+n*m)= (i+n*m)%n =i%m=b(i) and g(i+n*m)=(i+n*m)%m=i%m=g(i). Now If all combinations of b(i) and g(i) happens without a change in the state (happiness) then terminate. so worst case : 1 of n+m must change to happiness. assuming only 1 is happy at start, and is spreading to only 1 at a time of all possible combinations, so we need (n+m-1)*n*m .
I think that just n*m + max(n, m) would be enough. I don't think I have a formal proof, but I tried it here, and it can be seen passing 41st and 43rd test, which were problematic: 9907232
Only guarantee is n*m*(n+m). No less is a guarantee.
I will never use cin&cout without
ios_base::sync_with_stdio(0);I will never use cin&cout without
ios_base::sync_with_stdio(0);I will never use cin&cout without
ios_base::sync_with_stdio(0);I will never use cin&cout without
ios_base::sync_with_stdio(0);I will never use cin&cout without
ios_base::sync_with_stdio(0);You can submit with MS C++ without
ios_base::sync_with_stdio(0)Oh sorry_dreamoon is 2nd in final result..! Because of Dynamic scoring, A problem's score is changed...
Too many people failed in problem B so it changed from 500pts to 1000pts...What a sad story
dynamic score just to make sure sorry_dreamoon doesn't win the round
Why isn't that enough to check up to lcm(n,m) in the div2 problem B?
I saw a lot people solved the problem just by randomly picking large numbers like 1e6 or 1e7 etc. Why is that so?
Because it's easier to throw a big number that doesn't exceed the time limit than thinking about the exact upper limit.
should be 2*lcm(n,m)...
Can it be lcm(n,m)+max(n,m)?
Upd : It must be max, not min. Thanks for pointing it out.
tested on some cases, should be lcm(m,n) + max(m,n)...
firstly congrats to haghani secondly it will be a nice revenge if you change your handle to sorry_sorry_dreamoon :)
Ooops... Seems like our little kid (Haghani) beated sorry_dreamoon ... !!
why did one of my solutions skipped during evaluation?
Two reasons — 1- You did your coding in online ide and setting was public 2- You solve the problem as a team and somebody have same code as yours.
may be you re-submitted the solution or submitted from another account before this.
Finally,sorry_dreamoon is beated by dynamic score.....
Again I failed a problem (C) because of not declaring the array large enough, I though I was over with this kind of mistakes :(
If it weren't for bugs in my library I would have been probably 16th and IGM ;__; (didn't manage to debug it during contest in D, already got it ACed, needed sth like 15 mins more).
This is the first time I see such code.. Could you share what that is? Is it centroid decomposition? Googling for "FastrigateTree" yields no result :(
Hahaha, there is no such word as "fastrigate" :D. Few professors on UW used word "fastryga" for doing some easy searches of a tree during first semesters of our studies. That is very weird polish word, I don't even know what this means and not many people know (and it's nothing related to trees or algorithms) and since I maintain my library in English I created a verb "fastrigate" for doing all standard things on trees which came to my mind :). That includes finding a diameter and its middle-edge which was useful here (but can be done in a significantly easier way than in my code, because I do many other things there).
Can we solve problem B div2 using graphs.I tried solving it by naming nodes from 0 to n-1 and n to n+m-1, then established an undirected edge between all nodes that can possibly meet on same day.Then for all nodes that have initial happy value 1, I start a dfs and make happy values of all nodes that can be reached 1.
But my solution failed system tests.
Can somebody tell any flaw in this strategy?
Please see my code for details.
nop
Ahh..That's stupid of me.What was i thinking.
Changing j<(i+m) to j<100*(i+m) gets AC.
Anyway, thanks.
The idea is correct — I solved it using this way.
Solution link
Luckily became GrandMaster....Thanks all!!!
How to solve Div1 B ? Please help .. i thought about it a lot during the contest but not able to come up with an idea to solve this one.
If you have an empty cell that has only one empty cell near it, then you are 'forced' to put a 1x2 tile there. Do this for all force cells (And look if new forced cells appear after, and put them as well). If after doing this process there are still empty cells, then there are multiple solutions.
No, after a while of doing that process there will be no more forces cells. (You keep putting the forces cells and putting the new ones in a queue).
Problem C http://codeforces.me/contest/515/submission/9904318
My above code is generating correct answer on my system for given test case but its showing wrong here Plz help??
In the '9' case you are adding two sevens.
I have to add two sevens , in that test case one seven will come from 8 right??
9! = 72 * 7! = 6 * 6 * 2 * 7! = 3! * 3! * 2! * 7!
in the case of '9' you just need a line of
arr[index++] = 7;in problem div1 C:
am I the only one who first thought that it means trees which are special kind of graphs not the trees in our normal life? , funny how my default way in understanding the word "tree" became the trees which are special kind of graphs
Как решать D(Div 2) / B(Div 1)?
At least my rank was palindrome. -_-
2200is not palindrome!2112is.assert(rank != rating);
I can never distinguish between these two! Excuse me :D
I swear I will be in the top 5 one day QAQ.
Where Is Rating?Everyone Feel bore.Follow Topcoder.
Contest 2 hours.1 hour system test + 2 hours update rating.
Can someone please tell me what's wrong with this solution of Div 2 B.
I am getting wrong answer on 5th test.
In the for loop boy[temp]=1;
You should use temp, not i
Thanks
This is the first comment ever to break barrier of 500 upvotes and it already broke barrier of 800 http://codeforces.me/blog/entry/16446#comment-213065 :o!
You are wrong about first comment ever — this one got +500 few weeks ago.
What an irony... This is how it looks — dreamoon_love_AA gets huge number of upvotes for his round announcement, and then sorry_dreamoon is just doing that sorry, dreamoon_love_AA... stuff once again — now by getting more upvotes for his comment than dreamoon_love_AA for announcement :)
Oh, you're right. So it was first one to break (1000000000)2 barrier :D
so sad that he/she got that number of upvotes in his/her fake account not the real one :P
So, here is my story:
My solution for Div.1-B failed system testing — TLE on test 15, if I'm not mistaken.
After contest I took my java code, changed Points to pair<int, int>'s, changed queue to C++'s, submitted — and got AC.
So the question is — do I need to forget about using Java in competitions?
UPD: To compare: C++ — 9905626 and Java — 9896943.
На создание объектов в Java уходит больше времени, чем на создание записей в C++. Особенно это заметно когда создается много объектов.
You just need to adapt by using as few objects as possible. For example, instead of
Queue.add(new Point(x, y))useQueue.add(x); Queue.add(y);.PlayLikeNeverB4, As far as I know Java, the way you said to it, each time x and y will be wrapped into two Integer objects, cause you cannot make a generic queue with primitives.
Enavik, Of course it takes more time to create objects in Java, but for this purpose TL for Java is twice the TL for C++.
The thing is that I always thought that Codeforces is such a website, where I don't need to worry about small optimizations when my solution is correct...
And I think that for this problem TL was really too strict — a lot of solutions failed systests due to TLE.
Another thing is to use arrays. When you have an array (or queue) of pairs, just use int[N][2]. You can even sort them if you want.
I used to have problems in the past because of the language, but that thought me to be more careful. When it's an important competition I stick to C++ though :)
Use EZ Collections!
Sure?
When will the editorial be put up?
longer than 100 minutes and I 'm waiting for my rating updated -.-
Good luck to tourist with reading his PMs, I guess there will be a lot of questions like "Are you sorry_dreamoon, plese tell me, I won't tell anyone else :)" :D :D :D
sorry_dreamoon writes jokes in the head of each submission... 9885853 9893183 9895490 9898972
First one of the jokes is very funny :D
Immediate Persona and League of Legends flashbacks. Them puns.
Nice contest, nice problems. Hacked for the first time in my life :)
Не ищу простых путей. В Div1/B вместо того, чтобы проверять появление новой "плохой" клетки я выбирал особый порядок обхода.
Сверху-вниз, справа налево — WA10 Сверху-вниз, справа налево, повторить 20 раз — WA36 От каждого из четырех углов по диагоналям — WA19 От каждого из четырех углов по диагоналям, 20 раз — AC. (достаточно 3).
Вопрос, есть ли какой-то тест, чтобы новые "плохие" ячейки попадались хитрее, чем в наборе тестов?
I think Div2 ranks are lost :D lets repeat the contest
Thanks dreamoon_love_AA for nice contest I enjoyed the contest and most important thing that I gained +228 :D
I really enjoyed the contest today and reached Div1 again :)
Can someone explain me why in the final standings my rank is 340 but after the rating update it changed to 626? It's not even close to 340 :( Thanks!
Edit: Nevermind, the issue was solved!
In problem A, if you print "yes" in case of "Yes" will it be accepted or not?? Somebody wrote "yes" and he got it accepted??
Why ask when you already know the answer? :)
I enjoyed participating a lot. However my submissions were judged incorrectly in pre-testing phase itself.
See here: 9902412 9902094
Can anyone tell me why this unexpected behavior occurred?
How do I contact the organizers for correction?
It' my mistake :'( You should get some message like "your output may contain invalid character". But When I write checker, I will output this message when read invalid character.
you should not add '\0' to string.