Hi.
Codeforces round #299 is gonna take place soon(exact time) and I'm the writer. I'm lucky to be the first Iranian author in Codeforces, in your and our new year (2015 and 1394).
Now, I wanna thank: myself(PrinceOfPersia) for writing the problems(:P), MikeMirzayanov for great Codeforces and Polygon platform, Zlobober and Damon and sobhan.miryoosefi for helping me prepare this round, Haghani and SoroushE for testing this round, Delinur for translating problem statements into Russian and big thanks to my great buddy, HosseinYousefi for problem legends and the pictures.
Also, I wanna thank MinakoKojima for teaching me how to use polygon and testlib and so much other things about it (about a year ago).
This is my first official contest(after all those contests in Gym :D). I hope you enjoy it.
The main character of all problems is Tavas, well-known by eating CoffeeMix without water! Trust me, when he does that it smells awful.
Also, you'll meet his friends.
I hope you enjoy the problems. I wish you all high ratings, many Accepted solutions and Successful hacking attempts. And Hacked instead of Failed System Test.
Scoring will be posted later.
GL & HF ;)
UPD: Scoring will be standard for both divisions (500-1000-1500-2000-2500).
UPD2: Contest is over. We're waiting for system testing. Editorial is published.
UPD3: System test is done. Congratulations to all winners.
Div.1 winners:
And Div.2 winners are:
Good job everyone, see you ;)
looking forward to this contest thanks :) congrats for being the first Iranian author in CF in our new year wish u and everybody else luck :)
tavas has eaten the ratings instead of karafs??
Congratulations with your first official contest:) Looking at your contests at gym — now I am expecting interesting tasks, and I'll try to attend this round.
P.S. And I guess you'll also become a leader of contribution rankings soon, congratulations in advance:)
wow, he made it! congratulations :))
There will be another boost up after the editorials are out assuming he writes them.
Congratulations Man !! Hoping to see problems like the ones in gym :D.
I like contests with graphics :D I think it would be amazing one isA
Congratulations with your first official contest :)
I hope to see Problems a bit easier than yours in GYM :P and please do not use dynamic Scoring system :D
And also you should wish us Hacked before locking code ;)
Long time no see ... It is great to see you progress during this year ~ I am looking forward to your problems tomorrow night ~
This is my first contest as a Div.1 participant. Hope my rating will not decrease)) Thanks for Div.1+Div.2 contest!
Round #282 was my last Iranian author CodeForces round I have participated in and the problems was interesting.. I hope this one to be better :) Good Luck.
Hoping for rating increase.
Congratulations,I hope the problems will be easy enough for me to be able to increase my rating a little bit :P vali dadash farsi ham tarjome mikardi soalaro Awwwli mishod :)
Good luck to everyone !!! Hope that I'll participate in Div 1 Round next contest :)
You said you were going to write a contest and thank yourself and you did. haha thats awesome (y) http://mirror.codeforces.com/blog/entry/16996#comment-217994
Is Tavas your character ?
Firstly, when I see green color in this blog, I decided that it is some green coder, who made part of problems for the contest:D
Do you think green coder can't "make part of problems for the contest"?
Loved that "Hacked instead of Failed System Test"!
be careful with tricky cases xd, ...Does somebody know why our contest time has changed in one hour later?
It happened the same to me. I think it's just because the different Daylight Saving Time in Russia as in other places.
Congrats! :D
You're now first in top contributors list.
our new year also. it's 1st day of 1422 here in Bangladesh today!!
If you carefully read mails about rounds, you can find "The round writer is Codeforces problem coordinator PrinceOfPersia".
It is just copy-paste mistake. Zlobober, sorry me. You are not fired :)
I'm sad that there are no pretests for mails and I can't fix mail and resubmit it again.
Yeah, I noticed. (I almost never read the e-mails, it's quite strange that I now did and noticed it.)
I never read the mail, but when I saw you said that I read :D
I think if you hadn't mention that a lot of users wouldn't see :D
I'll be on a flight from the U.S. west coast to the east coast during this round...
Sounds like time for Codeforces at 39,000 feet (if the flight I'm on has wifi) :)
MISSION ACCOMPLISHED
...though my score doesn't really tell the same success story... :P
My Second Contest as a Candidate Master... This time I'll never go down to Expert
Wish you can rating-up again and become master soon~
Thanks~
Congrats to my country — Iran — for having Top contributor(PrinceOfPersia) and Bottom contributor(Fear_Is_An_Illusion)!
Two records, congratulations!
I guess +150 contribution is also a record!
Iranians are the records :D
PrinceOfPersia has registered for this contest !!!?
"Hacked instead of Failed System Test".. -> An awesome contest on the cards.. Also just 1 more to go now for 300 contests.. Thank you CF.. :)
I hope I will increase ratings in this contest !
And
I hope I will increase contributions in this comment !
I'm guessing your second wish was a fail.
I would participate in this contest and then watch the Real Madrid match. but Just Chelsea :D
It is a perfect time for programmers who are also real madrid fans!
Yeah it is a perfect time for watching Real Madrid's defeat...
If I predict your doing give me +1 else give me -1
"You will give me -1"
It is a paradox. Isn't it ???
I wasn't going to rate your comment, so your prediction failed, so I gave you -1.
It is paradox because : 1 you don't rate my comment — 2 you give me -1 how can you do that ???
We're programmers. If statements are only executed once.
I'm sure we all know what this does :)
so :
if( "none" != -1 ){
cout << "YOU DO 2 THINGS none && -1 how ?????";
}
Yes very nice, except lets refrain from using Python :D.
vote == action .
it is necessary
Early score distribution, lol. Nice!!!
Why most of the contests recently are being delayed?!
Это тот редкий случай, когда задержка порадовала — успею покушать
Wow ! Top contributor ! :D niiice ! :D Congratulations :D
This feeling when you found a mistake in your pretest AC-code, recode it, submit it again, and then realize that it wasn't mistake. Oh no( I was 125 and now I'm 825(
Imagine locking your solution DIV 2 A and hacking others with testcase 0 and later realizing even you missed that testcase..
Made two big blunders in this contest. Really need to learn to keep my cool during contest.
How to solve C?
Isn't it just a fenwick tree? My solution got WA on pretest 3 but I think that the idea is correct. I sort them in increasing order of S and then of R. Then I loop from n to 1 and find the answer. Counter-examples?
3 1 5 2 2 5 1 Answer: 1 3
Thank you, does it mean that the idea of Fenwick tree isn't correct or just my implementation is bad?
Fenwick tree isn't correct.
Thank you, now I understood why :)
The idea is not correct.
Thanks! :)
Convex hull.
Solution for problem C Div.2 ?
It should use binary search i think.
Lock Problem -> thinks about a test case that your code doesn't consider :(
For Div2 A, what about leading zeros?? please don't judge me on those :(
Thanks for the round, though there was a huge gap between B and C ( Div2 ). 2233 people solved B but only 196 ( of them ) got C !
about C task:
my solution: convex hull with two extra points: ( - 105, max(y) + 1) and (max(x) + 1, - 105)
I found my counter-exapmle :D
Can you explain ?
I did the same (post-contest), and have WA... What is my mistake?
If you're thinking you're having a bad day.. I'm going to fail in B because I wrote this to calculate power
And what's wrong with it?
i < n and n is the string length in the input :(
Ah, got it, It will fail, when m=0
This is just precalculation and then I output power[cnt] where cnt is the number of ? characters.
and seriously I don't know why I did this
I did more stupid mistake in B: I wrote
int count = m == 0 ? 0 : (y[0] - 1);instead of
int count = m == 0 ? n : (y[0] - 1);:( :( :(First time i've solved E:), I just could not make myself stop to submit E after 1 hour and 40 minutes.
Contest is now ended. I hope you enjoyed problem legends and little graphics for each problem :)
I can't wait for the system testing to complete.Will my submission for B get accepted?
My Problem A got hacked,before locking and failed system test!!
I hacked MamZi's B in the last 10 seconds and achieved a positive score :D
systest has stoppped :/
running again
Irrespective of the system testing results , this was by far my favouraite Contest among the recent codeforces contests . Hats off to problem setter .
Any tricky case for Div1 B. Many people seem to have failed case 8 in pretests.
forgetting to use MOD 1000000007, i think
Found my error . By mistake used the wrong library method for modular expo.
It was pretty fun to hack div.2 A, I made fife successful hacks. And it was more safe not to write any numbers by hand — just copy-paste from wikipedia.
Copy-paste what from wiki?
Copy-paste written numbers from the given link, and then somehow use them in the program code (10707394).
Oh, sorry. I didn't understand that you were speaking about Div2 A
Salam iran zamin ? ! How old are you ?! O_O !?
Hello)) There is a question about task C (2 div): Tavas and Karafs. Why in this answer on first test 2 1 4 1 5 3 = 4 ? 3 3 10 7 10 2 6 4 8
In this the sequence : 2 3 4 5 6 7 8... and I must have t = 7 that take 2 and 5. Or something not that?
http://mirror.codeforces.com/blog/entry/17401#comment-222339
Thank you
То самое чувство, когда хакнули двойной хэш =\\
My only mistake in C: I used doubles instead of integers. Even with an error margin, not exact comparisons, it still gave WA. When I replaced them by integers, AC. Stupid doubles.
You are dealing with cross products with points distant from each other of 1e-8 and you expect it to work ( ͡° ͜ʖ ͡°)? Moreover you possibly wanted to check if some point lies on some line and do it with some allowed precision error ( ͡° ͜ʖ ͡°)?
I thought it was 1e-4. (Not like the error caused by taking the difference of two close numbers couldn't be too small anyway, but this is the first time double comparisons have failed me so miserably.) Stupid doubles.
What's the idea of problem E-Div2/C-Div1 ?
The editorial is already available, check it out: http://mirror.codeforces.com/blog/entry/17401
Hey,
The limits for DIV2 B are (1 ≤ n ≤ 10^9). While if you look at this http://mirror.codeforces.com/contest/535/submission/10713882, the code fails on an input which is out of bound. WHY ?
it's 10^9 not 109!
Yeah... The limit is n<10^9, then why is his code test on
"444444444"? This is greater than 10^9.I really hope that you know that 10^9 has 10 digits
Yeah Got it..!! Thanks for the patience..!!
444444444 <
1000000000
10^9 has 10 digits
I think there are weak tests in Div 1 A. At the end of the contest I found long overflow in my solution (I used binary search and the sum of arithmetic progression could be too large). I quickly added additional check and got AC but lost about 150 pts. However, my first solution passed all tests too...
Maybe because when R is too large, then you fail
and can ignore overflow
Thanks!
Overflow? Where?
Can somebody explain in detail how to solve DIV-2 C as I am unable to understand the editorial.There's a lemma.Is that a standard lemma. if Yes can anyone give me the link to that lemma .If no can someone prove that it will be the optimal way to arrive at maximum r because I am unable to think how to approach solution if say t is such that more than m is the answer.
just a binary search for the required answer
Похоже, в Div 1 C слабые тесты: 10720876. Наверняка можно придумать тест, на котором это будет работать неправильно из-за точности или получит TL.
UPD: тест на TL : диагональ x + y = 104 без точки (1, 104 - 1), но с точкой (1, 104). Работает 1138 мс. Могут ли знатоки погрешностей придумать тест на точность?
Упала D на 41 тесте из-за ОДНОГО СИМВОЛА!!!1 Задача C тоже лежит из-за корявой реализации
БАБАХ
loved the contest :) and the descriptions of the problems :)
Wrong answer at 51 for problem A div-1. with message-
wrong output format Expected integer, but "1e+006" found , actual answer is 1000000
why are you matching answers as strings? match values!!
10714667
and got runtime error in problem B because of writing "n" instead of "s.length()"
BAD DAY.
I got a Runtime Error on test 55 on problem B (div 1), a case where m=0 and my code crashed trying to read a line that didn't exist.
Looking at the input specification again, shouldn't you be able to expect an empty line in that case?
Same here... Problem statement indeed states that The next line contains m space separated integers... , but there were no next line at all. Re-test wanted!
Yeah I think that would be fair. Looked through some submissions and saw that at least 8 failed because of that reason.
I'm not very familiar with Codeforces rules and regulations. What can we do in this situation? Do we need just send private message to MikeMirzayanov ?
I'm one of them. Run my code against empty line test, lost 200 positions and my red color because of that :/
I am impressed by the number of people who wrote out all 100 answers to div2 A and the 1022 answers to div2 B
BTW who wrote 1022 answers for div2 B?
Just go to the status page of problem B and sort them by Solution Size
i totally did. :)
LOL. I understood C as "for which pair (xi, yi) do there exist A, B > 0 that Axi + Byi is not less than other Ax + By" instead of A / x + B / y :D passed more than 40 tests
You didn't take the case in which you have more people of the same type.I think you could take AC :))
I changed that couple of minutes ago and I get WA on #43. Testcase is:
loool , i made the same mistake , modify it to division and you get Accepted
writing twelwe instead of twelve and getting WA in problem a.div2. is it a dictation test or a contest?
I had a hard time trying to understand prob statement of C div 2. Maybe I need to sleep more, lol!
me too. i think it is very hard to understand.
I didn't solve any problem... Guys! let's make it unrated! what u think?
Now, lets not. I think, i have solved more than usual
very good contest!!
First time failed all problems in CF contest :( feels so terrible :(
Me too :( Solved only B but failed even it because of wrong array size.
Only 10 minutes before the end of the round, I was very close to ending up the same as you. At least I knew how it'd end.
(For the record, I've had that experience.)
Anw, now that I have time to carefully think about my failure yesterday, I think I learnt something:
Could anybody help me please?,
I can't see my mistake, i'm getting TLE in pretest 37 my algorithm is O(n) z algorithm
this is my code code
You have a mistake in your z_function implementation. On the first iteration (which is unnecessary, as z[0] is undefined) the string will be compared to itself, z[0] — set to n, and r — set to n — 1. Then you have (r < i) in your if statement (instead of i < r), which will never be true. So, for each i you will iterate through the whole suffix (well, in case of a string like aaa...a), and it basically works in O(n^n).
that was because of my incomplete template, anyway thanks!
Using picture is good and positive point
Where are the ratings,man?
i found saddas , best friend (not girlfriend)of tavas who love karafs a lot
Can somebody explain me DIV 2 C for this test Case 1
2 1 1
1 5 3
Why is the answer 4 and not 3 A=2 and B=1 so Sequence 2 + (i-1)*1 == i+1 so for l=1 we have Seqence =2,3 ,4 ,5,6
now we have 5 tries original — 2 3 4 5 6 1st try 1 2 3 5 6 2nd try 0 1 2 4 6 3rd try 0 0 1 3 6 4th try 0 0 0 2 5 5th try 0 0 0 1 4
so we get S[3]=0; so answer =3 and not 4 Can somebody exmplan me wher i am wrong
2 3 4 5
2 2 3 4
2 1 2 3
2 0 1 2
1 0 0 1
0 0 0 0
does we have a constraint on distinct reduction of Distinct Karafses, You are reducing 1 1 to 0 0, which are Same not Distinct?? please correct me if am wrong
distinct indexes, not distinct height
okay so if u have distinct height selection do u have ideas how can we achieve the same
congrast to all new candidate masters!
Very nice problem! I love it! Thanks for problem.
Antihash in 67th test for D is awesome.
I really enjoyed the problem set after a while being away from lovely Codeforces rounds. Thank you PrinceOfPersia for putting such an effort preparing the round and so quick editorial.
So, finally...
Thanks to the great performance of doing A and B :D.
Today's Last position holding contestant of div1 got back to his previous position!
Achievement unlocked :)
Moreover — with more than 1,5 min margin :D.
You know, when I saw this, it was like oh, I have no idea how this solution can be proved, but this is definitely right one, becuase Swistakk submitted it already:)
Or another reason behind probable simplicity of solution could be that this was A ;). Talking about a proof — easy greedy works :).
Rather weak tests for B(e. g. 10723410 fails on
)
So... Whens your next round?
LOL i didnt expect to win after i spent so much unnecessary time on problems B and C. Nice problems BTW
finally increase in ratings. #HappyMe :-)
Damn!!! I should have known before that the rating decreases even if you make no attempts!!! What was that? :(( I thought a "fail at test #1" is an exception :(
damn ... i missed this round :(
Can someone explain me why line
mid=lef+rig>>1;works correct in the solution 10719921?I think the correct usage in binary search is
mid=(lef+rig)>>1;">>" has less priority than "+"
Ohh.. My world has changed that moment! I thought bit operations are the most prior
Sorry for the bad idea
I don't get it.
This is the well-known jd and truk meme. This is another comic on Internet Explorer.. They're scared of "Failed on system test".
My code got accepted in problem D but fails in this case
8 2
ababa
1 3
expected 26
found 0
http://mirror.codeforces.com/contest/535/submission/10724364
where is the tutorial?
How about reading the "UPD2" from the announcement or looking at "Recent actions"?
Wow, thanks very much!!
Thanks for problem C. For me it's harder than D and E :)
And for majority of people it was easier than A :D
UPD: Ugh, sorry, that post is about #299 not #305, I don't know how I have found myself here x_0
In Problem D div 2 what should be the answer if the test case is : n = 10 , m = 2 p = "ibic" m --> 1 3 as I found 2 AC solutions one of them get answer 0 10922320 and the other gets 456976 10746306
The answer is 0. My AC solution gives 0.
Thx for this contest, and I became candidate master.0.0~
problem c was too easy :D