Hi!
I'm honored to invite you to Codeforces Round #383, it will be held on 6nd December 14:35 UTC. There will be 5 problems for each division as usual. The contest was prepared by AmirReza Arpa PoorAkhavan and Mehrdad Batman Saberi. It's our first official contest at CodeForces.
The contest stories will be about Arpa and Mehrdad and some events happen with them in Arpa's land, in addition you will get some information about Arpa's land and girls living there (Owf (t = 1)).
I'd like to thank myself (:P) and Mehrdad at first, then Nikolay KAN Kalinin for helping me in preparing problems and Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platforms.
The scoring distribution will be announced later.
Answer for one of your common questions : -Yes, It is rated.
UPD. GL & HF. Hope you came up with Dokhtar-kosh solutions for our Dokhtar-kosh problems.
Urgent information from MikeMirzayanov: due to hardware issues, the round is moved to Tuesday 6th December, 14:35 UTC. We are very sorry this happened. More information is available in this post.
UPD. Scoring distribution: Div.1 : 500-1000-1250-2000-2500, Div.2 : 500-1000-1500-2000-2250.
UPD. Contest is over, hope you have been Joon-Joon of the round :P
Congratulations to winners:
Div.1:
1 . EvenImage
2 . mnbvmar
5 . Phronesis
Sepcial congratulations to anta who solved Div.1 E.
Div.2:
1 . gilcu3
2 . toHisDream
3 . Far
4 . shpsi
5 . orz_liuwei
Editorial is ready.
Hope for finally become orange :)
Its Arpa, not ADJA.
Well, there are some cool coincidences, like:
So, I hope increase of rating will also become coincidence :P
Mother of logic.
We need a bit more positiveness these days :)
I share a secret with you, don't tell to anyone: You can buy problems by just $100, tell me if you want them.
Lol!!! I bet you want to sell them after the contest, right? :'D :P
DP? Again DP problems? ( Oh, I see it everywhere
@bekar13 :D why he need to wait for the end of the contest? he can sell it when the contest starts ;)
Mr.Adnan don't you think that he will be busy in that time for judging and giving clarifications? ;)
if you want, you can!
2191 :|
I'm starting to think maybe my rating is asymptotic to 2200.
You havn't face the real asymptotic,bro. I'm starting to think maybe my rating is asymptotic to 1820
And my graph does not have a limit, because it's a function of type f(n) = ( - 1)n ;)
what does that (t=1) mean???
Please wait just for 48 hours. You will understand the meaning in Div1.A.
I don't know too :/
Maybe he means owtf(oh what the father) If you mean this arpa, i have to tell you that it is so funny haha :|
if you think you are very funny you can create your own contest.
dont spam in this blog
Hope the english translation is better than this blog !
I wouldn't hold out my breath though :D
Hope this time I won't fall back to div2 immediately :D
the new question should be: will the problemset contain googable problems??? is it rated became too old :D
Hope to become green again guys pray for me!!
Since, no one asked this above and there is no seriously hated down-voted to hell comment above, I would like to ask this: Is it rated?
Read post again carefully.
Here you are :P -76 just in 13 hours. GoodLuck and high contribution :P
number 383 is prime && palindrome! ：）
you meant palindromic prime ?
I've been waiting for along time to see how Batman can do in problem setting
I'm very exciting , hope you guys won't disappoint us
Thanks a lot...
We tried our best for the contest... But by the way, I don't guarantee anything at all :)...
I like the characters of Arpa and Mehrdad
who did paint them or they have copied from the Internet ?
I painted them...
And there are other paintings in the problem statements too... Hope you enjoy them :)
The Codeforces is begging me to "Register Now" and also asks me to pay attention...
Try to control your site admins... It has some devil plans...
Glad to see our Codeforces is back! Thanks to the maintainers' hard efforts.
I got a mini heart attack when it read :
Temporarily, because of hardware issues Codeforces and Polygon are not available. We hope to fix it before January, 11, 11:00 MSK. We apologize for the inconvenience.
What would I had done for 1 month :3
your graph is really inspiring Arpa ! :)
Thanks, I need to write about my story as some people wanted from me (link), but I haven't enough time, sorry :(
Your submissions are enough to tell your story :)
If you mean "number of submissions" by "submissions", I'd like to post my graph here :
If you mean "special comments on top of the code" by "submissions", Some of them can tell something to you. But last one : "Someone like you"?! Unbelievable ... refers to my love and it is totally unrelated.
How'd you get that graph?
Are there any other such graphs?
Use CF importer.
Tell me... Whose your love Arpa? :D
Why you are asking while you know him as well as I know?! In addition you will know him better in Div.1 E.
Him?! or Her?!
I check my comments before publishing, so there isn't any typo in my comments.
Then you are... ehhmm...?
@ RuinsOfCentury, Let's move to private messages, shall we?
Isn't it weird that you didn't want to thank GlebsHP?
He wasn't involved in preparation, KAN helped me instead.
That's true. Moreover, there were already some rounds recently that were prepared without my help.
i wish you will make a good contest brother Arpa .good luck for all.
it's my birthday guys.:) i get my rate up .
Happy Birthday
Happy Birth Day bro
As you gave thanks to yourself, you needed to thank us (contestants ) also :/
Users are showing their thank with minuses.
is it usual ?
God with us, brother.
fck u stupid extremist.
Please be polite. Everyone has some beliefs. "All we are brothers", is slogan of Islam.
wtf he posts a terrorist's photo
Oh ! Maybe you are right, but it isn't enough reason to misbehave.
UPD I think he wants to misrepresent Islam.
You guys are debating because of a spammer?
yes
Only Muslims(not all) are brothers according to your Islam, and others are terrible sinner who are going to be punished by Allah, isn't it what your Islam says?
You can post sources.
Listen, I'm not Muslim, so don't ask me for proof. I've talked with many Muslims and all of them has agreed with that. So they suggested me to take Islam and Allah would forgive me.
And if you want proof whether Allah has indeed said it or not, ask Mohammad (the Islam prophet). If you can't do that then just die and meet him directly.
ps: don't mind if you didn't mean to ask for a source, I can't understand whether you asked me or told me to do something.
UPD: Source added below.
I stated something that's good practice when making an argument for or against... well, anything.
You can research it yourself (Quran and some texts around it); a lot of people have. I'm intentionally being vague in order to not hint at what you'll find (and to have fun).
"As to those who reject faith, I will punish them with terrible agony in this world and in the Hereafter, nor will they have anyone to help."
source: https://goo.gl/46zNQB
"We have special responsibilities towards our brothers and sisters in Islam that we do not have towards the non-Muslim"
source: https://goo.gl/NXl7xB
And now I remember, my friend once told me that at his last speech Mohammad said that all Muslims are brothers. (though He also told not to enforce other races to take Islam). So I think you can take Mohammad as the "source".
What is this "In the name of God" thing?
"Anything which doesn't starts with "In the name of God" is incomplete"
-- Mohammad (the Islam prophet).
Allahu Ekber brother.
This is the most common phrase to utter before a Muslim die or kill "in the name of God". I hope you are still safe, dear!
This comment is incomplete
This comment is incomplete
This comment is complete shit
Still incomplete
I already gave an answer, see below.
I hope I get to feel the colour cyan. Just 6 points away from it.
Then you have to solve at least 3 problems probably.
Solving A and B fast should be enough (10 minutes for A and 20 minutes for B).
Are problems on russian?
hope for becoming blue finally
After 7 months, I am back. :)
to steal some points .. huh ???
You stole the whole round, right? !! And moved it to 6,December. :D
You're here also!? :D just because of you the contest rescheduled! @RippleOfLove
The CodeForces is not only for you, right? !!
Yeah right! you wasn't there, everything was fine! Just you came and see what's going on ! :/
who is he? why do you think like that?
He is a cheater! :D stole money from 100+ programmers to arrange a contest, but he couldn't manage the contest. Now he isn't returning money to all :D Do I need any other reason or am I behaving worst to him? :P +nandrewjh
Come back Codeforces after nearly 2 years. Wish me good luck!
And, I'd like to thank myself (:P) for reading Arpa's Blog :D
how to make codeforces in English again it became in russian ?
Click
hope the contest be cool as the painting. (but i guess mehrdad's eyes(in the painting) are saying it's gonna be hard enough! :D)
Yeah, he looks a little bit scary. On the other hand Arpa looks so innocent :P Maybe the painting has some hidden message about the problem set too(easy problem with so many corner cases) ;)
i think Arpa looks like the main character of "The Little Prince" book in this painting and Mehrdad looks like a malefic person!(sure he isn't in real) :D (or maybe i'm just over judging a painting -_-)
We've found the father of logic too.
LOL! I was just kidding :p :v
yayyy, another Persian contest. Hope to see funny problem statements like PrinceOfPersia's problem statements :D
you can not find it everywhere easily :)
I have some here... Come tonight and I'll show you...
:|
First, be polite. In addition, don't challenge Batman, he is so dangerous. Wait and see his great works in problem statements :P
Such a dreamer...
Batman sorry
Contest will moved to another date, lets take a virtual contest with our team, "Keyvan KL" tonight, then keyvankhademi will became happy ^_^.
khademi moalem helli 1 e.
It seems that I need to take another virtual contest with amsen with our team, "BK".
It seems that I have to choose my team's name carefully :/
Mage energy hanuz madresas? :/
felan ke sal pish 3 ta tala dad :/ Mahdi_Jfri
Tabrik migm shoma mitunid bad tarin nasle energy bashid (0 specialist hatta!)
go and play with your toys
sepanta Now i can see who has to go and play with his toys :)
couldn't even solve problem B? :)
guys! please respect to others
they pressed down vote, because they do not understand the iranian language. write in this website Russian or English.
:-)
I hope you guys will be the same active in comments after the contest. People usually need you so much right after contest ends...
I will decide for it after the contest by considering the situation :)...
Just make it cool and then accept compliments :)
P.S. a tip: prepare the editorial before you get annoyed by comments "where is editorial"
But it's not just about the editorial, there should be lots of things I guess... So it's preferred to don't think about all of these, just saying something like good luck and have fun before the contest should be enough :)...
The editorial is already prepared by me, don't worry ; )
Can you post it now :P
Here you are :
Nothing here dude :P
Thanks for the interesting problems. where is the editorial now ?
Just curious. In the name of which god do you write?
There is only one God.The most fundamental teaching of Islam is to believe in the Oneness of God, in the sense of His being the only Creator, Preserver, Nourisher, etc. But this belief is not enough. Many of the idolaters knew and believed that only the Supreme God could do all this and yet they associated other gods with Him. Therefore, one must acknowledge the fact that it is God alone who deserves to be worshipped, and thus abstain from worshipping any other thing or being. Likewise, Muslims believe that God has no father or mother, no son or daughter. None is equal to Him. He is God of all humankind, not of a special tribe or race.
Thank you, man. You make me so glad of having been born in the west.
good luck
EDIT: The guy I replied to edited his post...
. concentrate on contest
I assume you're an intelligent human being. You don't need dogmas, you are SMART, you have the possibility to be free, but instead choose to live imprisoned in ancient beliefs.
If you had been born in India, you would believe in something else. If you had been born in Greece 3 thousands years ago you'd believe something different.
I deeply believe every human being has the capacity to think for himself, don't waste this!
Through history, humans have invented multiple religions, and there are tons of them RIGHT NOW. There's absolutely no reason to believe one is more real than the other.
I'm very sorry you were born in such a harsh environment, with such strict views of the world, but I'm sure light will be shed on you eventually.
Have a good day!
sgioia tnx. but what you mean "dogmas"?
you mean " Religion " ?
Not at all. Not all religions enforce dogma.
this is your opinion .i don't have to consider it . and there is no need to prove that there is a god . just read more and ask some one who has a mind . ^_^
Yeah, no problem. I'm sure you're comfortable getting your beliefs shoved up your butt =)
i wonder if your mother really knows who is your father .
Whatever, man =)
Are you Sunni or Shi'i?
Thank God I live in a country where I'm not forced to believe in Him.
Thank Putin I live in a country where I'm forced to not be forced to believe in God.
Reply to above comments : Here is Codeforces, please move your discussions to another place.
These comments are relevant according to your blog. If you didn't write that irrelevant sentence at the start people would not ask for explanations. This is Codeforces, not an advertising site of spreading what you believe.
But it's fine I think...
It's cool to read about different believes from different regions :D ...At least for me...
Cool for me too! As it is a community we can expect other's views and beliefs on different subjects, that's why Codeforces get festive mode in religious occasions. But, Author himself can not take these discussions easily, also some people here are crying as their feeling is getting hurt. And some would declare war for hurting their feelings.
believe is a personal matter for everyone i think
also i don't think that it can not be a annoying issue to all and specially you :P
any way never mind :)
I believe you are dumb ass. because
No, man just kidding!
did you get hurt? see? sometimes it is not that simple. Totally irrelevant but just showed you an example how it can be more than personal.
And no, It is annoying, read above comments. Some mis-beliefs can lead you to hate others. In worst case I think there will be a war soon.
finally I didn't mind but sorry if author did.
After a long delay (4 weeks), I'm here to say : It was my mistake, I want Codeforces community to excuse me.
That sentence (In the name of God) was, and currently is, one of my beliefs, but now I know that I shouldn't write my religious beliefs in Codeforces.
Codeforces сегодня тормозит и иногда вовсе отказывается работать, надеюсь во время раунда всё будет в норме!
Надежды не оправдались и раунд был перенесён, ну что же, будем ждать вторника(
Codeforces, не надо болеть, выздоравливай!
I have a question... what does the word "dokhtar kosh" mean?!
You will know it's meaning in Div.1 D.
I'm interested in why you ask questions that are related to problem statements, You've asked three questions and all of them was related to some problem. It's so abnormal ...
It's a spoiler I guess.
No, it has meaning in persian.
"dokhtar-kosh" meaning girl-friendly in persian language :)
It will be my first contest. Hope for a good start :)
I think I have to wait
Trust in Codeforces — there are so much lags and troubles with logging in and refreshing pages today.
I just want to know the meaning of "t=1", don't care if I lose some rating xD
Raise your hand if you think the contest will be delayed, postponed or at least won't run smoothly :/
Even if the problems turn out to be very good, it's not a good day for contest given the state of the servers. I feel bad for the writers :(
You were right, it is delayed.
383 is a prime number :)
Someone has mentioned it earlier :p
Glad to see that my student is becoming the master, good luck Arpa ;)
Thanks PrinceOfPersia. I'm more glad to say you was (and currently are) my teacher. Wish the bests for you too.
I could not participate in any prince_of_persia contests, hope to taste similarly nice problem set from you :)
How to become your student? Is there any way? =)
Urgent information from MikeMirzayanov : due to hardware issues, the round will be moved. what it means by "MOVED"?
why not tomorrow? what if after 4 days same problem exists? DO IT AFTER ONLY 3-5 HOURS NOT 4 DAYS
Read the post, they are going to NEERC which is held this weekend
Because NEERC is to be held on December 3-4 — tomorrow and the day after tomorrow — so a lot of participants won't be able to write it
Should we participate in the round ? The site is so buggy .
Let me register on div2!
Delayed for 4 days. "Big drama show".
Before Contest 00: 47: 10
Refresh
Before Contest 4 days
Had to check couple of times whether I was seeing it right.
Congratulation, you have just invented a time machine. :)
То чувство когда раунд перенесли.
Issues issues and more issues. Last time with the copied problems thing, I thought of posting a comment regarding the issues that have taken place with CF in the last 3 months.(8+ issues).
However, I shall not post any disrespectful comments as anybody at Codeforces is not answerable to us, but this rising number of issues is very difficult to deal with to say the least.
NOOOOOOOOO , :'(
Urgent information from MikeMirzayanov : due to hardware issues, the round will is moved to Tuesday 6th December, 17:35 UTC. We are very sorry this happened. More information will be available later.
Better delayed than long queue/unrated. :)
LETS BOYCOTT CODEFORCES FOREVER FOR "BEING ISSUEFORCES"
WTF!!!
StayStrongCodeForces
oh mike, faz isso com nois nao, senao nois te quebra
Sad because of delay(
This is because Writers Forget to thanks MikeMirzayanov!! :)
No he didn't -_-
কেনে চলর?
:D ঘুম থেকে উঠে দেখি কন্টেস্ট শিডিউল চেঞ্জড !! এমন রাগ উঠছে :@
IT SEEMS CODEFORCES SERVER HAS GOT IMPROVED AFTER THE UPDATE OF DELAY
At least site is working and we are not seeing "...due to some hardware issue, CF will be unavailable until 10 January 2017"
Deleted
This needs an edit for Mike as Wojak. There are already real life memes, after all.
GET WELL SOON CF!!!
Actually, computer scientists from codeforces developed some way to time-travel. But due to hardware issues, they could not go back to now. :)
I prepared a bottle of caffine drink and luckily I just took a little sip of it. I think I can sleep tonight.
Its time to change your handle bro :P Congrats btw.
But he's only violet :|
Make Codeforces great again. ._.
Hardware Issues :P
:S :S
:/ I waited and waited whole day for the contest!! now I change the sentence- I wasted and wasted whole day for the contest :'(
you should try another platform like Hacker rank, Hackerearth, lightoj, uva, code chef etc if you are eagerly interested in contest :)
Codeforces contest is another thing bro :'( I can't feel any other contest like cf :(
Till now the most frequent comment was "Is it rated ?"
Now it'll be "Will it be delayed?" or "I hope it won't be delayed" or "Is the hardware ok?"
since the contest is 4 days delayed, I think there'll be higher number of registrations and thus more participation!
ooohhh...nice :)
just 'ooohhh...nice :)' and you got more upvotes than me? Not I want any upvotes.....but seriously!!
I'm so sorry for that :/
And again Batman got more upvotes than u mitsuki ;)
hahaha, then go ahead and become purple or up and prepare for a round. :)
Where is Chinese?
If you are talking about Chinese people, they are everywhere man. Even you are Chinese! LOL :P
http://prntscr.com/derzh8 OWF(t=1) ? What.
I don't feel good about this contest.
first it was postponed and second JESUS CHRIST did anybody read the comments on this blog ??? someone should delete them this is codeforces for god's sake...unless god is participating in the contest do not bring up religious talks here there are a ton of sites for that.
Arpa you are going to make record for highest registration may be participation also
More participants mean more load on servers. Praying for smooth contest.
Trust on Codeforces strong servers.
I believe in Codeforces.
I hope today it won't be delayed again..
The entire human race survives on hope.
I was on a trip when the Contest was held but then I got home and it had been moved... so happy ^^!
Good Luck
And Have Fun.
Is this going to be the largest CF Div 2 in terms of registrations? Any Pinch on statistics?
For now the largest Div 2 contest had 8497 registrants, but only 7965 of them were really Div. 2 contestants. So, this was already beaten earlier today.
It better be the largest in terms of participation :)
What if there are 8500 participants :O
it's almost 10.000 for both divisions
Don't raise expectations so much — not all of them will participate.
Scoring Distribution ?
Here you are.
What's up with the long queues -_-
The queue is killing me T_T
In Queue :(
For > 5 minutes my submission is in the queue...
I've locked a problem but it won't allow me to see other people's submissions, why?
Merhdad's girlfriend's reaction (if he has) to problem D (and the word "Hos" that he calls girls with) must be interesting!!!
Which girlfriend you mean? he has many ...
anyone that he cares about(if he does)!! i hope his GF(s) & crush(es) won't be programmers or CF users :D did you two guys even think about anything else except girls when you were preparing this problems?! :D :/
They are CF coders as well, like bogjse316.
No, but note that I was writer of all of problems ; )
and one more reason(*) to wish that she hasn't a CF account!!
* -> he(Merdad) has a handle with such a name! -_-
is there any easy way to be an Arpa's land citizen?! :D
bogjse316 is his girlfriend.
It's too hard to become an Arpa's land citizen, your DNA must have same pattern as mine, in fact you must be a ... (more information here : 741E - Arpa’s abnormal DNA and Mehrdad’s deep interest).
so it seems like they are in a relationship since at least one year ago :))) (Hos) huuum, so it means that i must be gay?
As I said, Mehrdad has many girlfriends, some of them are new (less than one year in a relationship) and some of them are old (more than one year in a relationship). And you are right, that Hos (bogjse316) is his loyal and official girlfriend.
I can't find the relation between Mehrdad girlfriends and you being gay :/
Being the "sogoli" of your own "haramsara" is such a fun thing! :))
Being gay was not about Mehrdad's girlfriends it was about the citizenship.
Ohom.
Excuse me, but why you think I am a homosexual ?!
I just guess :)
Don't publish your guesses publicly. Let's move to private messages, shall we?
Too many girls in problem statements :D Arpa ?
I am the god of lock problems...
Awesome problems, guys!
Thanks. Wait for unique editorial as well :P
I wish I had hacked myself. T__T
I wish the same. Was hacking someone then realized that I myself missed a case.
To be honest the contest isn't interesting, speed contest, first 2 are easy the rest hard ((.
It was fun for my level.
Hack case for Div 1A :
Make simple cycles of odd lengths, i.e each node belongs to exactly one cycle of an odd length.
Using 99 nodes, you can make simple cycles of lengths 3, 5, 7, 9....17.
The answer for such a case would 14549535.
I hacked 6 and got hacked...maybe next time I should try to solve E...
Same case here bro :(
Is O(nk2) dp the intended solution for Div1-B?
And how to solve C?
C: First, all men — 1, all woman — 2. After random.
Solution
I think its possible in O(n*w + E)? (no of distinct component*w + n*w with amortized complexity)
I did something similar.
Is div1 C 2-SAT?
I don't think so, at least not my solution...
Solution : Draw an edge between each pair of couples and also draw an edge from vertex 2i + 1 to 2i + 2 for all i. This graph is bipartite since it has no odd cycles. Thus, we can 2-color it and it is easy to see that this satisfies all problem conditions. GG
Note : I didn't solve it during contest T_T
"This graph is bipartite" ?
The graph is sum of two maychings so it is biparitie!
So we add edges between 1-2, 3-4 and so on. But isn't this forcing the condition that the type of foods by the people at 1st and 2nd position should necessarily be different? Can't there be a solution when both eat the same type of food (unless every case of that type can be converted to one in which they eat different foods)? I am unable to understand this.
Worst feeling known to humanity: the realization that your solution is wrong after locking the problem
Oh, same here! For some reason, I forgot that I couldn't submit anymore and thought I had found some pretty cool cheat. My idea was to open the source of the one who hacked me, then rewrite it myself and submit it. It sounded brilliant to me until I tried to submit it :D :D :D My biggest facepalm ever, something strange happens with me these days :D
Hello sorry but for further contests i believe you need to be more specific about what you want in the problems for example in problem B div2 when you say pairs, you don't say distinct pairs or plain pairs, example input does not help to clarify this and this could lead to unnecessary wrong answers. (not in my case since i had it all wrong but you get the idea)
in the statement 1 <= i < j <= n
this is the same as saying that they are distinct pairs
I think there were some mathematical thing that says what it want after the word pair. It's quite clear to me tho.
Any hack for problem C.
I'm new here. Pardon me if I say something irrelevant. Will the explanations of the problems be given after the contest? :/
Yes, the editorial will be posted within few days :)
Thank you very much mister ^_^ can you help me with another thing? What is "hack" that everyone keeps talking about?
There are a set of tests called pretests which your submission is tested on during the contest. These tests aren't entirely comprehensive so your solution could still be wrong even if it passes the pretests. After passing pretests, you can "lock" your problem (meaning you can no longer resubmit it) and then you're allowed to look at the code of other people in your room (everyone is assigned a room in the beginning of the contest). If you think someone's code is wrong, you can give it a counter test case and if it is wrong, then you get an extra 100 points but if your test case is wrong, you lose 50 points.
I saw someone in my room successfully hacked 10 times.(div 2)....
And now I'm thinking about my life.
Does Div2C/Div1A has anything to do with floydWarshall ?
No, just find all the cycle lengths and calculate the LCM. Beware cycles with even length.
I'm confused about how you came up with that. Did you just notice a pattern or is there some kind of reasoning for why that's the solution?
First, notice that all nodes must be within cycles (a node outside a cycle can't be reached by any of the nodes he reaches, by cycle definition, so we'll never satisfy the property of the problem).
Then, considering a and b in the same cycle, the only way to satisfy a --(t steps)--> b and b --(t steps)--> a is if a == b (and then t = size of cycle) or if b is halfway from a on the cycle and a is halfway from b on the cycle (and then t = half the size of cycle) — which is only possible if cycle length is even.
So cycles of even length will satisfy the mentioned property when t is multiple of length/2, cycles of odd length will satisfy the property when t is multiple of its length. And then the LCM of these will give the minimum t where the property is satisfied for them all :)
I can't even code knapsack!
Wrote
i++instead ofj++. Literally 1 character mistake. ;_;And I can't code LCM either -_-
Can not believe C was solved by a lot of people. Maybe I understood in a wrong way.
Problem A and B sooo hackable! For A problem! in
0 out 1 For B problem! in 2 0 1 1 out 1 But someones' answer 2
I'm not too sure, but I suspect that the girls in Arpa's land are attractive to look at.
While B was too easy and boring (I even spent some time re-reading the statement two times to see what I missed), problem C was very nice. And it may be argued but I would write "note the unusual constraint for the alphabet size" in problem D because it was extremely easy to miss (and it's indeed very unusual constraint). Thanks for a nice contest!
So what's your complexity about problem D?
UPD: Oops, I didn't see this constraint during the contest, and implemented a hash table.
BTW, the time complexity of my solution is
. If this solution is expected, I think the it's better to set small N.
This solution was expected. The hard version of this problem hasn't that limit : 101189D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths(Hard).
I don't see why author didn't remove that constraint and put memory limit of 512MB (or smaller N so that hashmap can be used). It would look much better.
Actually that is a very good question. Originally that was a problem C and I had the same comment in the system during presolving as you have. But when the problem became D we all agreed that having this technical difficulties should be great for D.
Arpa, why did you hide your article "DSU on trees"? Still available with google cache :) I guess Div1D can be solved with it (though I didn't manage yet).
Yes I've hided that. And the solution uses this technique.
enot110 has a very interesting solution for Div 1C...
It is just random solution. Most of the solutions have been like this.
the hacking round....
Can anyone tell me why my solution to problem B is wrong? (it got wrong answer on pretest 11):
long long int count_anwser() { long long int ans = 0; for(int i = 0; i < numer_of_elements; ++i) { int needed_number = tab[i]^x;
ans += count_of_this_numer[needed_number]; count_of_this_numer[tab[i]]++; } return ans;}
where count_of_this_numer is number of elements which are equal to index
Value of needed_number can be greater than 1e5.
Ohhh, I lost 30 min to figure out what was wrong, now Accepted :(
Interesting problems accompanied by a super fast system testing. Thanks for the nice contest guys :)
Ровно 10000 участников)
I solved problem div2 D using this technique [ DSU + 0-1 knapsack + dp ]:
make groups with DSU
With the 0-1 knapsack, take the max of:
ii) try to invite a single person of this group(try with each member)
iii) don't invite anyone at all
store the max in dp and return it
What's wrong in my algorithm or in code ?
Can problems of the type of Div1C in general have flow solutions? I know here n ≤ 105, but I'm interested to know if these problems where every k consecutive people satisfy some property can be solved with flow.
In problem D, the constraint that all letters are between 'a' and 'v' is very well hidden in the input section and not emphasized at all. I'm pretty sure it cost Swistakk an Accepted on it, and it cost me a submit and half an hour more to implement it.
I think such unusual constraints should be highlighted because it's very difficult to spot them otherwise.
I don't know why you mentioned me, but my code was just a bit too slow (and memory consuming, but that can be fixed with one line). I really dislike that problem, it is rather obvious what is the solution and whole "fun" is winning with strict TL what is dependent on details of implementation :|.
However, indeed I had an idea to create a static array of size 2|Σ|, but 226 was too much. Either way, I needed to create
such arrays, so I needed |Σ| ≤ 21, 22 was still too much :D.
And yes, I definitely agree with your point, that constraint was extremely easy to miss, it should have been emphasized.
I saw you got MLE, so I glanced through your code and saw you had 26 and 27 in your code so I thought you didn't see the constraint like me xD.
Two non-similar codes 22748780 and 22758461 from the same country.
I'm feeling sad about that. I belive they will be banned and will learn the lesson in a hard and expensive way.
i think there is a mistake in problem D on DIV2 int the statement you say " Along with that, from each friendship group he can either invite all Hoses, or no more than one" you didn't say that i can take no one from this group
"no more than one" implies that you can take <=1 people.
What is the intended time complexity of D and E? O(Nσlog N) in D and O(Nsqrt(Nlog N)) in E?
me when i see a girl from Arpa's land :3 :3 :v
What is the reasoning behind problem E?
I understand the first part. The quite obvious idea of sorting implicit strings with hashes is not brand new and (usually) not very pleasant to implement, but nevertheless, it is OK for Div1E.
I understand the second part. The quite obvious idea of splitting K-s into small and large and answering queries in
is not brand new and (usually) not very pleasant to implement, but nevertheless, it is OK for Div1E.
And now, if you think that it is really interesting to combine two completely unrelated to each other nasty idealess implementations into one Div1E problem, be the first to throw a stone at me.
Firstly, I agree that the problem isn't very imaginative. However, I think as far as difficulty goes, it deserved to be where it was, seeing as only anta solved it in contest — I found it very hard to code it in 2 hours and only solved it afterwards. I do understand your point though.
Secondly, the complexity you mentioned for queries isn't fast enough. Instead we need to use both range trees (for K<=50) and sparse table (for K>50 so that N/K <= 2000). However, this does actually prove your point about how it was nasty to implement.
So I agree that it wasn't beautiful as you would expect for a Div1E, but I would argue it isn't too trivial to 'see' the solution either.
I use overall complexity
for queries and get AC.
Ah, I didn't think of your algorithm (which has lower constant factor than what I was thinking) — it's quite beautiful. :D
It was allowed, I had a
as well. What is the problem ?
Sorry, I skipped your comment suddenly because I was busy that time.
Note that hashes are not allowed. I had banned solution with hashes, if you use mod = 2x, you'll get wrong answer, otherwise, you'll get TLE because modulo operations.
Why you want to mock my problem? Let's talk more in privet messages, shall we?
(Thanks to Errichto, I was writing a mocking comment because I was angry, he told me not to do)
I want to go to Arpa Island. ♥
Hello,
Could someone help me with a little explanation?
I tried to hack this code for problem B during the contest:
http://pastebin.com/TJHFm3s8
I was expecting it to give runtime error since there is an array out of bounds access on the test that I've provided (you can see there is truly such an access if you comment out the cout... it will try to access the array at position 131071 but the array is only 100005 long). However, even though there's an out of bounds access it doesn't give runtime error. Can someone explain why?
Thanks in advance.
I guess it depends on the compiler.
You can test cf compiler here: http://mirror.codeforces.com/problemset/customtest
Here is my conclusion after testing:
If the array is declared in global, then out of bounds will print 0. However , If the array is declared in the function, out of bounds will give run-time error.
That's not true either. I have seen codes which declared the array globally and got RE (my own code does that if I comment out the line which checks this).
It really doesn't seem fair to me that some sources got accepted with this problem while others got RE for the same issue. Applied to hacks as well (especially to hacks). Haven't seen this happening on any other online judge.
Oh well.
There is also a variable 'b' with size 100.000. Variable 'a' is a pointer and when you access a[ 131.071 ], you basically access a + 131.071. 'b' is allocated after 'a' so you will access b[ 31.071 ]. Not sure if this works only on global variables but i think this is something that depends on the compiler and language. If you would access a[ 250.000 ] ( this will be equal to b[ 150.000 ] i guess ), that will go out of every variable and that should give runtime error.
Thing is you access b[131K].. not a[131K]. And b is declared after a.
At any rate... we can speculate on this all we want but the truth is array out of bounds is classified in C (and C++) as undefined behavior. Which means we can speculate all we want but the details of this are compiler-specific.
Therefore, the CF crew is not at fault here. It's just sad that some people got accepted with a bug in their code while other people got RE on the same bug. But oh well, what can you do ¯\_(ツ)_/¯
Same code but why RE for using Array and AC for using map (STL). [problem:][problem:742B] RE: 22763251 AC: 22763425
All data set <= 100000. i am used 100005 in array size. but got RE. why?????????????????? Explain please.
100000^1323 = 101323 .
arr[i]^x >100000
99999^25655=123560
It's possible that for some (i,j), a[i] xor a[j] will exceed 100k.
Can anyone help me in Div2 B?
I first sorted the given array, then if a^b=x then b=x^a. Since it is sorted I can find out the number of occurrences of b in the array by upperbound-lowerbound. (I checked for non occurrence seperately).
Thank You.
You overkilled it. Just count xxorai. Array is enough. Keep in mind that size of array must be greater than 105 since xor can be greater.
Thank You! I got an AC with this method. But still, although I know my solution is an overkill, it should give correct answer right?
Here is the link of my solution : http://mirror.codeforces.com/contest/742/submission/22764097
Thank You once again :)
Overflow.
In
ans = ans + ub - lb;, address of ub will be added to ans which might cause overflow.So change it to
ans = ans + (ub-a.begin()) - (lb-a.begin());orans = ans + (ub-lb);Accepted
Thank You so much!
Never once thought of overflow. Will have to take care not to repeat it again. Thanks :)
In div1A and div2C pretest 4 is as follows
5
2 4 3 1 2
In this wouldn't the ans be 3 as 1 calls 2. Then 2 calls 4. 4 calls 1 giving t=3
5 calls 2, 2 calls 4, 4 calls 1, 1 calls 2, 2 calls, 4,...
The cycle keeps on going, but will never return to 5. So ans is -1
Ahh got it. I missed that 'each' x. This means that every node has to be in a cycle. Thanks.
No, the answer will be -1 because 5 will never be called. 5 calls 2 and 2 is a part of a loop 2->4->1->2. The number t should be satisfied for all x and it isn't satisfied for x=5.
Finally I'm green :)
Green upvotes for you then :)
Where's tutorial?
I think today's problemset(Div.2) was awesome. One of the best contests in Codeforces in recent times by far.Though my own performance wasn't the coolest, but really got inner peace just by thinking and formulating the solutions. :P :P. Thanks to the authors and co-ordinators. Great job guys. :D :D
Two code are same . In the problem B constraint for 1 ≤ ai ≤ 100000 . IN one code I used frq array for frequency got WA on 11 . But when i USed MAP for frequency , then got AC . That means constraint for ai is not correct . My two submissions are 1) With MAP frq 2) With frq array .
As stated above by OMG_wc
"arr[i]^x >100000 99999^25655=123560"
XOR of two numbers a,b <= 10^5 can be greater than 10^5 . That's why using an array fails . Map just stores 0 for a key which is not present .
LARGEST NO OF COMMENTS ON ANY CONTEST ANOUNCE'' PAGE EvenImage >Petr
Whats special with even cycle in Div2 C? why we need to half them ?
In an odd cycle, the only way that if the round of X ends in Y then the round of Y ends in X with a certain t, is if X=Y. Nevertheless, if the cycle length is even, it can Y can be the "midpoint" of the X cycle. Think of the following case: 2 2 1 (Sorry, I don't know how to format the test case properly)
how to do div2 E
first you must know -1 is impossible.
then you can do such thing
here is code 22763097
Really neat solution :)
Really outstanding contest!
Short problem statements, elegant pictures for every problem, interesting legend and such a extraordinary editorial. After this contest I feel a very pleasant aftertaste, because I see that every effort was made to make this contest brilliant. And it is.
I feel satisfied. Thank you a lot.
had a nice starting for the problems "arpa land has very nice girls" :D
good job anyway. best reference of learning persian:D
Plot twist: Arpa is the nicest one :P (Just joking, I have a good opinion on him :))
Could someone help me debug my solution? http://mirror.codeforces.com/contest/742/submission/22769800
thank you!
EDIT: I found the mistake, if anyone was wondering it's accessing the array with i%2, those arent the iterations of the dynamic but the index of the group.
i wanna make deeeeeeeeeeeeeeeeeeeep replays
deeper
deeeeeeep
deep
deep
after few deep they remove my replays and my comment too