Привет всем!
CF раунд #333 (обе дивизионы) состоится сегодня. Авторы раунда — я и Baklazan.
Просто случайно, мои задачи пронумерованы чётно и задачи Баклажана пронумерованы нечётно. И тепер можете раздумать, если они пронумерованы от 0 или от 1 :D.
Как обычно, благодарим GlebsHP за его помощь (в частности, за помощи упростить некоторые задачи), MikeMirzayanov за CF и Polygon, Delinur за перевод условий задач на русский язык и тестерам misof, Mimino, AlexFetisov и winger.
Желаю хороших результатов и изменений рейтинга тем, кто их заслужат, и также всем сумма-нуль изменение рейтинга.
По традиции, разбалловка появиться прямо перед соревнованием.
Div.2: 500-1000-1500-2250-2250
Div.1: 500-1250-1250-2000-2500
A contest authored by Xellos! I bet the statements will be really funny!
By Xellos and Baklazan. I bet that the problems will be really interesting. Even the announcement is nice and precise.
LOOOOOL
There are many hacks in this contest. This contest will be very interesting.
nevermind
I can't stop listening to this!
"as well as a zero-sum rating update to everyone"?
you can take this blog as an example. The amount of positive vote Xellos gets here is proportional to downvotes other get. so, the amount of all downvotes here including yours + the amount of upvote Xellos get is almost zero. Hope this helps.
the soonest announcement.
what do you mean of posting a programmer cat photo?
I think you have to swap links of (animated version, original)
No, I don't. It's correct the way it is.
You have also changed the screen of the laptop...:D
Deleted
А на русском нельзя написать?7??7?7? Не все тут британцы то всё-таки.
КАК МОЖНО БЫТЬ ТАКИМ ДАУНОМ, ЧТОБЫ ЭТО ДИЗЛАЙКАТЬ?????????
Нельзя, поскольку автор контеста не знает русского. Тем не менее, условия задач на русском конечно буду.
Не нашёл благодарности за перевод, как обычно, поэтому немного страшно стало, но этот комментарий поставил всё на свои места. было бы хорошо благодарность тому, кто перевёл условия выразить.
Xellos write:
"I'm the author of even-indexed problems and Baklazan the author of odd-indexed problems"
So,The the index of the problems start with 0 or 1?(In other words,A Div2 indexed by 0 or 1?)
Yes.
Yes? :-/ What yes? :-/
Yes, with 0 or 1.
No,I say Which problem indexed by 0?(A div2,C div2,... or B div2,D div2). It seems that A div2,C div2,... are indexed by 0.(by reading you last answer.).Is it right?
Why would you even consider the possibility of B div2 and above being indexed by 0? That would mean A div2 indexed by a negative number.
if we indexed A by 1,B by 2 and ... ,problem B div2 ,D div2 and ... are even-indexed but if we indexed A by 0,B by 1 and ... ,problem A div2 ,C div2 and ... are odd-indexed.Is it out of mind?
Yes — it's on screen.
I can keep this up longer than you :D
Holy heck, you guys are pricks. The guys was asking a genuine question and all you do is downvote him. I mean, yeah sure it's fun messing around with someone for quite a while, but you know... You could just answer his question in one of the comments.
Oh and in case you're in the "hurr durr i is veri smart cant read broken englando"-zone, he asks:
"Since you are the author of even problems and Baklazan is the author of odd problems, does the indexation of problems begin with 0 or 1? In other words, which problems did you design: A, C, E, Div1 E or B, D, Div1 D?"
Why it's so hard to read the post?
I'm the author of even-indexed problems and Baklazan the author of odd-indexed problems. Now I'm going to let you wonder if it's 0-based or 1-based :D.
Oh, what a horrible thing I did! FYI I don't want to reveal it yet, so that people could read the problems in arbitrary/strategic order.
Since the debate reached its maximum indentation level, not sure who you guys talking to :p
In the comment headers, there are
^and#links. Have you ever wondered what they mean?No. I have better things to wonder, because.
Hi Xellos,
You did not mention Maria Belova (Delinur) in your round announcement. I'm guessing she did not do problem statement translations?
Not yet, since the problem statements aren't ready yet. Mystery of the Early Announcement...
I volunteer for problem statement translation, whenever they're ready.
From English to English?
What proof do you have that I am not Russian? Or, say, that I don't understand Russian?
tu russian nahi Xellos ka kutta hay :D
He's abusing Xellos, calling him dog. Google translate.
So, I_love_Captain_America is Indian. But, Guys he is such an evil. Google can never translate any of my words: Click for Proof. The real translation is:
"tu russian nahi" — means, you are not russian
"Xellos ka kutta hay" — means, you are a bitch of Xellos
I didn't abuse any dog calling Xellos.
@Bullspeck, Why did you mislead a whole community against me? Learn to respect your own country. People like you are a shame to its own nation.
People here are not idiots. The link you gave doesn't translate shit. I translated words, not the whole rubbish you wrote.
I didn't abuse any dog calling Xellos.
Shame on you.
After he mentioned India, I translated using some Indian languages, and this is the result click
viesis, calling any human a dog is disrespectful. Did I_love_Captain_America/Xellos say anything disrespectful to you before you posted that? btw, the translation is wrong.
@ruhan, I think calling that I_love_Captain_America as bulldog would be fine. but if you think it is disrespectful to the dog-species then let's call this user ass whole, would it be ok?
If that is true, then why did you tag me in your next comment? I got an unnecessary mail in my inbox drawing my attention to your nonsense comments and forcing me to give you one final reply.
You illiterate dipshit dont you know how to use Google translate? There are many languages in the options as source language, and you uneducated shit using both source and destination as English facepalm
I used almost all the languages in drop down menu to come to the realization that the word means dog. I kept changing language till the word didn't translate to the word itself. Took 5-10 minutes that's all.I didn't know it was Indian language at the time, I just figured out what it meant.
I am not Russian, and I was shitposting about translating to Russian, for fun. But I am not Xellos' dog, you little twat-faced bitch. I will not respond to any more of your cum ments so GET THE F*** OUTTA HERE YOU BASTARD.
I don't know how to post gifs, but you can post this instead...
My new favourite song...
Lada ull Baklazan
>contest will take place in a few days
>proceeds to schedule the contest in 16 days from the announcement
I'm calling shenanigans
The "16 days" is when I made a template with pretty much nothing. Blog post "publishing" times can be misleading.
From now on, all(or most of) the contests are held in 'unusual' time, right? A 300000-millisecond-delay!
What's even-indexed problem if our eyes aren't real?
15 people get the joke, and I ain't one of 'em sigh
How Can Mirrors Be Real If Our Eyes Aren't Real
Cat. Keyboard.
#include <string>?More like
So the main character of this round will be Pusheen? :D
negative votes please :)
Here you are
Hey, why do you have to conduct all of your competitions on Tuesdays? I can neither participate in round #333 nor #334, because of a Tuesday schedule conflict. Can't you reschedule #334 on another day?
There was a blog post about a week ago saying all competitions have been on Wednesdays and Thursdays (or Fridays?) recently. Actually, the statistics of standard CF rounds for the past 2 months including the upcoming contests is:
Well, at the very least it would be nice to not have two competitions on the same day of the week (Tuesday) in two CONSECUTIVE weeks, like the case is now... Is there a way to suggest this to admins?
Is there a way to suggest this to admins?
Yes, you can write to them.
Auto comment: topic has been updated by Xellos (previous revision, new revision, compare).
Gif is working :O
Is it rated?
why not?
What is story of your handle ( dibil1000)?
MikeMirzayanov would be wrong to expect 333 coderforces t-shirt ( one extra for me to draw attention about it ) for this 333 round :D As 333 round comes only once in a codeforce life time we can expect 333 codeforces t-shirt :D
I thought 333 comes once again after N, as other numbers do :)
In the email CF sent
Attention! Unusual start time: the round starts on Tuesday, November, 24, 2015 16:35 (UTC).
but this is the usual time :D
Auto comment: topic has been updated by Xellos (previous revision, new revision, compare).
Nice Russian translation :D.
I will translate later.
Yea,but i hope statemant will translate another person.
I am afraid of this contest :(((((
So am I :D
"сум-нуль"
Есть кто-нибудь, кто знает, что это значит?:D
Нужно зайти на английскую версию поста.
это значить, что сумма всех изменений рейтингов должна быть равна 0 — сказано одним словом...
Автори -> Авторы
Wow. The number of "This comment is hidden because of too negative feedback" comments is way too high for this blog post.
I've been shit-posting a lot for the last couple of months, hardly did any competitions, and hated solving problems altogether. I didn't realize that the reason I started hating it is because I've already solved the easy problems and the difficult ones are left. Today I got a real nice kick to think my actions over, and so, after this one, no more shit-posting, only learning and competing and repeat.
Auto comment: topic has been updated by Xellos (previous revision, new revision, compare).
base64
heh heh heh !
The Contest starts with Score distribution announcement :D
lool Decoded it using ubuntu :D
will be revealed right before the contest
It's funny that ubuntu base64 couldn't decode ZDJsc2JDQmlaU0J5WlhabFlXeGxaQ0J5YVdkb2RDQmlaV1p2Y21VZ2RHaGxJR052Ym5SbGMzUWdL R0ZqWTI5eVpHbHVaeUIwYnlCMApjbUZrYVhScGIyNHBDZz09Cg==, but Mac base64 could.
No I have ubuntu and it works for me
ZDJsc2JDQmlaU0J5WlhabFlXeGxaQ0J5YVdkb2RDQmlaV1p2Y21VZ2RHaGxJR052Ym5SbGMzUWdL R0ZqWTI5eVpHbHVaeUIwYnlCMApjbUZrYVhScGIyNHBDZz09Cg==
Base64-decoded it ...
d2lsbCBiZSByZXZlYWxlZCByaWdodCBiZWZvcmUgdGhlIGNvbnRlc3QgKGFjY29yZGluZyB0byB0 cmFkaXRpb24pCg==
Base64-decoded it again ....
will be revealed right before the contest (according to tradition)
I don't get it. How is 'Will' = d2ls ? Please explain it :)
Base64
Thanks
downvote me
As you wish :)
if you are too lazy to double decode, here's the score distribution : Div. 1: 500-1250-1250-2000-2500 Div. 2: 500-1000-1500-2250-2250 glhf!
В определеннии константы Липшица подразумевается целая часть? Округляем вверх или вниз?
As you asked in the English site, I'll answer in English: it's the ceiling function, rounding up.
Sorry, my bad. Thank you.
Hack Div.2 B выдает ошибка
FAIL the absolute differences between consecutive A[i] must be <= 1 ()Codeforces was down for me almost all the contest, I couldn't load the page at all, did this happen to anyone else?
Codeforces was up for me almost all the contest, I could load the page without any trouble at all, did this happen to anyone else?
I ask because this is the first time this happens to me, I tried with various internet connections, It took me over an hour to get to the front page.
yes it did
Я аплодирую стоя авторам задач за умение обманывать.
UPD: Конкретнее — наверняка я не единственный, кто слишком поздно понял, что в A div1 один из видов транспорта сможет добраться до N города за единичку и вообще не будет мешать второму транспорту. То есть простой БФС, замаскированный под... что-то более сложное.
В B div1 у меня ушло много времени, чтобы осознать, что мы никогда не будем брать два числа на расстоянии больше единицы. Ну хотя тут это уже скорее что-то со мной не так, нежели авторы это замаскировали.
Very interesting problems...
Submitted solution of B in last 3 seconds and pretests passed! Phew, that was close!
How did you solve it? Could you, please, explain? :)
Div 2 B was DP . dp[i][0] = longest sequence such that its last element is a[i] and it is the smallest element in the sequence Similarly, for dp[i][1] (if a[i] is the largest element in the sequence) Transitions are : 1 . a[i+1] — a[i] = 1 : dp[i+1][1] = dp[i][0] + 1 2. a[i] — a[i+1] = 1 : dp[i+1][0] = dp[i][1] + 1 3. a[i] = a[i+1] : dp[i+1][j] = dp[i][j]+1
I also have a solution without dp.We can deal with the initial array a to a new array p so that the continous same element will combine.Then for each p[i] we find left_max and right_max and judge whether they can be combined.But this solution is n^2 , we can use a array v to mark the element we have dealed . Because once it was dealed , we dont have to deal it twice. By this trick,it will be a O(n) solution.And thank you for your solution, you know i am not good at dp:) I will deal it with dp tonight:)
It's two pointer approach question. We start from i=0 and left=0 and keep track of minimum and maximum elements while traversing and we stop when abs(a[i]-minimum)>1 or abs(a[i]-maximum)>1. Then if(abs(a[i]-minimum)>1) we put left=minimum index + 1 and if(abs(a[i]-maximum)>1) we put left = maximum index + 1. Then again we start traversing with i and these steps repeat until i!=n.
It looks like the pretests are very weak. I submitted two solutions to C that had a bug in them and passed the pretests.
That is the point of the hacking bro :)
jqdai0815 solved from E to A, like in a div.2 round :'(
Good tactic if you can usually solve E reasonably quickly. Relatively easiest to relatively hardest :D
It seems my solution to D will fail system test. I find it's wrong right after the contest.
What do you think is wrong there?
Size of array is too small. I use a stack to store trash nodes. But I forget to add the trash nodes to the stack. So it required
space.
I think I should test my code instead of playing game. (>_<
Game name please
The worst-case memory should be
ints. If you're not allocating memory in very a stupid way, it shouldn't be a problem.
Oops, my solution passed system test. I don't know what happened. >_<
So, this contest was too simple for you? ;p
Why are you so young and so red?
Asian. :P
PS — No offense intended.
That sudden realization 5 minutes before end of contest, that if first city doesn't have a road to the target city, means it has a railroad to that city. So it's a one-dimensional BFS then...
These slow Estonians...
Holy crap you just ruined my whole day
Oh... I didn't realize that! How can I not figure it out??
почему в B в Div2 проходило N^2? (на претесты только)
Я думаю, что после системного тестирование N^2 решение упадет.
Div-2 A: I think many forgot the fact that pow(x,y) != ceil(pow(x,y)) Hacked 6 in my room with
How? it should be a simple if(25>24) — I used manual powers tho.
25 > 24, but pow(5,2) will return 24.9x, so if you store it as long long, it will get stored as 24.
on my compiler long long x = pow(5,2) returns x = 25
You can try this :
I am unable to understand why could that happen. I tried this on my system, as well as on ideone — link. Both terminate without any output.
Could you provide an insight on why would pow(5,2) be 24.9 and not exactly 25?
Because pow accepts it as a double and double being a floating point type has precision issues. http://www.cplusplus.com/reference/cmath/pow/
Kind of similar why one cannot compare doubles precisely.
But same thing runs fine on my system as well as on online compilers. Why should that behave differently on codeforces?
I don't know the exact reason. The output depends on the compiler I guess. I use Codeblocks and I got (long long)pow(5,2) = 24
Codeblocks doesn't use g++. It uses a variation of it.
That was really tough I tried to solve problem A by converting all values to base 10 and then comparing them,like this,but I kept getting the sum as 0,don't know why,could anyone help?
Why do you set int s = n-1 outside the loop then make a new variable with the same name inside it?
You're declaring a new variable called
suminside the loop. Changeint sum = sum + l;->sum = sum + l;so that it updates the outer scope'ssum.I updated it to this I still get 0 as sum
In the for loop 's' is initialised to n-1 but the check is s <= 0. Shouldn't it be s >= 0 ? In the present code, the for loop is not getting executed.
…
Thanks I am not a retard.
Why are you declaring int s inside for loop??
Should it not be ~~~~~ for(s; s <= 0 ;s--) ~~~~~
i started contest 40 minutes late but it was fantastic!
thanks Xellos ! :D
" thanks Xellos ! :D "
Hey! I feel offended...
You should feel not active enough on CF :D
thanks Baklazan ^_^
be happy to get thanks from a higher rated coder than amsen
be happy to get reply from rated coders!
thanks also misof, Mimino, AlexFetisov , winger !
Div2D can be reduced to finding sum of max (a[i]..a[j]) with l <= i <= j <= r.
Again, headshot-ed by D. Even O(N log N*Q) solution get TLE. Is there a way to solve D in O(N*Q)?
Yes
И так скоро будут разбори, но как кто решал Div2.E?
Could someone tell me what the hell is wrong with my code??? http://mirror.codeforces.com/contest/602/submission/14455186
Phew finally found it. Try this
7
1 1 2 2 3 3 3
Your code gives 4 but answer is 5.
PS — You need to update the value of maxVal and minVal as you traverse through input that's where the problem lies.
Nice contest. I wish i hadn't wasted much time on B though and moved to C directly :\ I am not even sure for B but C was sure if i could submit in time :\ So yeah i was right, 5 more minute would have made it for me :( http://mirror.codeforces.com/problemset/problem/602/C --> http://mirror.codeforces.com/contest/602/submission/14457506
I was very close to do an unsuccessful hack because of this pearl:
#define int long longI guess it helps some coders to not even think about overflow cases but I can imagine many people have fallen for it and failed their hacks. What do you guys think?
Right at the same time I complained about the same subject !
And unfortunately this trap screwed me in hacking :[
I made the exact same mistake last contest. A smart idea actually since ratings is a zero-sum game.
4 unsuccessful hacking attempts !
2 of them defined int as long long on A, what's wrong with you people ?
For problem C, suppose that the condition that "all pairs of nodes without a railroad connecting them must have a road connecting them" was removed. How then could we solve this problem?
2D BFS (my actual solution without realizing the condition you mentioned, probably failed)
In a node of a BFS you save position of the bus and the train. Then when you dequeue it, you add all the nodes where bus can go * where train can go, except if their destionations equal.
So, if the state is (2,3) it means bus is at the 2nd node and train is at the 3rd node. Then you look where bus can go: for each destionation you look where train can go (except the same destinations) and add them to the queue if they are not visited.
We can just do it with bfs. Train or bus will get to the city n in 1 hour for sure, because the edge (1,n) belong to bus or to train. For transport, that can't do it, we can just do bfs.
The user I answered to asked what if the condition that train or bus will have a road to the target city would be removed, meaning what if there would be pairs of cities without any roads inbetween.
A new legendary grandmaster is born...
It took me 15min to pass pretests on Div1 B, and then I spent over an hour trying to get an idea of Div1 C, even though they were valued the same :\ . What did I miss? What's the approach for Div1 C?
There are 2 steps here:
I'm not sure I understand. So what if I find the probability that one opponents has better score? How does it scale to M opponents?
E(# participants with better score)
= (M-1) * E(1 participant has better score)
= (M-1) * (probability that 1 participant has better score).
I got to step 2, knew it was DP but couldn't figure out how to do it. Looking through the solutions, I see something with prefix sums and a DP table of dp[processed races][current sum], but still don't know how it works :(
Really sorry for them whom are getting WA on 45 in DIV2 A.....I think many of you don't know pow function doesn't work appropriately in codeforces.
The problem is not in codeforces, but in c++.
Can you Explain,pls?I was sometimes ago getting wa while upsolving a problem.In a test case my code was showing different output for my compiler and the judge compiler.Then somebody tell me pow function doesn't work appropriately in codeforces.But I really confused that time,Can u pls tell the real reason
Pow() returns double. FE, int(pow(5, 2)) = 24. Because pow(5,2) = 24,999...
And what is the right solution for this trouble?
Just write your own little pow function with long long or use the Horner Scheme to calculate the numbers.
Or just calculate numbers from right to left.
I suppose you mean this? https://en.wikipedia.org/wiki/Horner%27s_method
No, i know that is horner scheme.
I mean this: http://mirror.codeforces.com/contest/602/submission/14444101
Okidoki :-) Now i understand :-)
But I still don't get it. On my machine,
int(pow(5, 2))gives25. I use g++ 5.2.0 on x64 linux.Try this
a=pow(5,2);
printf("%d\n",a);
Sorry but still the same result... This is my submission: 14443620 My codes gives me the correct result on my machine.
Change pow() to powl()
Please use your own power function. Codeforces has many post related to this.
Problem with pow() function
will ceil(pow ()) do the job ?
powl() will work but it's better to make your own function.
What's the solution of Div1 B?
По моему, на задачу B были слабые тесты. Мое решение с ошибкой которое выдавало на тест
ответ
1вместо3, как-то прошло все тесты.Я сильно удивился, когда увидел это.
Разность между двумя соседними числами должна быть не больше единицы по модулю.
What may be the reason of WA40 in div1A?
Maybe you use
powin c++, which is incorrect. Try this test:Answer:
=.Using an stl function pow.
Division 1, guys.
Seems we fail if the parity is wrong and there are no cycles to fix it or something. I don't have the edge n->n so it has to go away and return.
e.g.
I give 3 for
The method has no observation about one takes 1->n immediately, just does a BFS on the state (train at, truck at, who moved last).
Here was irrelevant message about other problem. Thanks for downvoting instead of simply explaining it.
i have solved problem C with O(n^3)! will it get TL?
I think no, because 400^3 = 64000000.
How to solve Div 2 C. Is it some kind of 2D BFS ? Can anyone share the approach ?
if there is an edge from 1 -> N then we can do a bfs for road system and report the distance of N from 1 , if there is no edge from 1 -> N , there is a road from 1 -> N so we can use that and find distance from 1 to N in rail network and print the distance of N from 1 using rail.
Thanks! I missed the observation that edge 1->N exists either for rail or for road network.
No, it is simple 1D BFS, you just need the observation that the there is a road or railway from city 1 to N that will take one hour that is only available for one vehicle and you just need to compute the shortest path of the vehicle that didn't have this edge.
I realized only afterward that if the traintrack isn't directly connected to the end position, then a road MUST be. So the Min time for either the train or the bus is 1. Then, from there on it's a straight up BFS over all the positions and the min number of steps to get to the end is the answer. I still solved it, just rather stupidly...
How to solve Div2 B? What is the main idea?
Idea of simplification was to add
1to all odd numbers of array, then find longest consequence of same elements. And repeat the same with even numbers.How did you come up with that? Did you solve a similar problem before?
You can try these
Hotels
Array Sub
Sliding Window
Problems
Thank you so much!
This is like a fishing rod instead of a fish. Much more valuable than just knowing the solution :)
Could you help me out to realize what's wrong with this sliding window approach?
http://mirror.codeforces.com/contest/602/submission/14458195
I'm just increasing the size of my window whenever I can do it and then decreasing when there are more than 2 different numbers inside the window, what means that the difference between max and min should be at least 2.
You might run into something like
1 2 1 3where you would run into 2 mins before hitting a max.Try this test case
6
5 4 5 6 4 5
ans is 3 but your code is giving 4.
Hi can you help me understand why this doesn't work ?
http://mirror.codeforces.com/contest/602/submission/14498228
My idea is to keep low and high and when the difference of either low-high or high-low becomes >= 2 then I move the low or high value to the right until it becomes a valid value.
Input
9
4 5 4 5 6 6 6 6 6
Correct output — 6
Your code is giving 8. Why? Because when it first encounters 6 then it increments lind to index 1 but it should have incremented to index 3.
Thx) Also I saw another versions of solution, someone uses RMQ, dichotomy... So variative)
What is RMQ and how dichotomy can be used for that problem? :)
I tried a similar approach.Finding the longest sequence of two or less numbers:14460365
Even O(n^2) are passing.Its sad.
very good contest!thank you a lot!
In this round fest and Shadow are cheaters.
Here are their solutions for B:
14455597
14455707
Check their ranks in Round 322 -> 276 and 277
yeah, their codes are identical. Any idea why their run-times differ? (One is 202ms and the other 187ms)
one is in c++ other in c++11
It's out of competition though right? Is that still considered cheating?
Could you explain what does the name of div1D mean? In Russian it's pretty nonsense not related to the problem (or I'm too dumb to notice it).
It has no connection to the problem other than what a tree with any letters is in chemistry. (Organic chemistry really has a letter for everything — R stands for "anything", for example.)
I'm actually stunned of how test cases are so strong for problem C and weak for problem B. If you want to know what I mean look at this submission. http://mirror.codeforces.com/contest/602/submission/14448575 and got Accepted! with complexity O(n^2)
Wow, so there was no need for dp. Now this really looks like a div2B problem.
I need to adjust my assumptions about the speed of codeforces machines, so maybe next time I'll do better in the contest :)
Why would it need a dp :| You can do it in O(n) without the need of dp anyways.
I didn't understand that when I wrote that comment.
Now I know that there is a very beautiful solution described here :)
I enjoyed all problems so thank you for a round Baklazan and Xellos.
Though I don't like your editorial. Hints are better than no editorial at all but I would prefer to be able to decide if I want to read whole solution immediately.
I would prefer to be able to format everything properly immediately. But we don't always get what we want.
This is still better than waiting for everything at once.
Where is the editorial?
I am getting correct answer on my PC but WA in CF: http://mirror.codeforces.com/contest/602/submission/14455593
During Educational Codeforces Round 1 hacking, I found distinct answer for a same code ran in my PC and CF. However, I didn't know why.
Maybe the precision of double
But I have not used floats or doubles anywhere in my code.
the function queryInternal doesn't return anything. Whether it goes wrong?
Thank you for helping. I corrected it and it got accepted. non-void function not returning a value is undefined behavior.
Admins Please take a note on this. Strange thing happened I don't know the reasong.
In my solution 14444210 to the Div 2: prob A. It says wrong answer to test case 45. I have tested with the same test case in my system as well as in ideone.com here and gives the correct output.
Please look into the matter. Thank You
You used pow function which gives say pow(5,2) is 24.999999. So when you take the long long you actually get 24...
but then why does it work on my pc (using g++ btw in linux system just in case) and also the online compilers. And that makes pow totally worthless!!
I am not entirely sure, but once I put round() around my pow function, it worked.
K... I had to implement my own pow function to get it accepted!! Btw thanks... I am not going to use pow again!! it was strange tho!!
Nice problems and nice day. But I still don't know why I get RE on pretest 8 in Problem B div.2 for my first solution.
What is the reasoning for not including any big tests to break single hashing in pretests?
Well. Why would they want such a test in pretests?
I mean, pretests should test basic correctness. If the solution is going to fail on most big tests, it seems to me pretests should check that.
Most of the reasoning for weak pretests is for hacking. (right?) D's don't get hacked a lot and it's pretty risky to hack so it doesn't seem to serve this purpose. I guess this is mostly about the point of system testing, which I don't think is to make people fail.
Well, anyway I guess I shouldn't assume that such tests are included next time and just double-hash to begin with :/
I think you should estimate the probability of collision first. https://en.wikipedia.org/wiki/Birthday_problem
You are absolutely right about checking probability. I mostly was thinking that pretests would catch bad solutions (as per CF's increasing tendency to have strong pretests, maxtests, etc.) Rather, I'm referring to what seems to me intentionally failing these tests in systests rather than pretests: (Also re: desert97)
I was assuming that the authors let hashes pass pretests intentionally and fail later, not just randomly. This is based on statements like "which is why there are anti-hash tests :D" (which might be referring to abbabaab... instead), but also how almost all hashers failed test 13, even with different hash systems.
If this is correct, this is the thing that seems kinda bad to me since it's just there to make people fail. I feel like that's what pretests are for and designed to do — make it so people don't think their solution is right when it actually has a big problem. Of course hacks lessen this problem, but who hacks on D? (oops rev1 was correct...)
I'm also a little annoyed at dropping from 10th to 105th due to systests :/, but I think I would still think the same way if I passed. Pretests are something that have always been a bit strange, and I guess I would appreciate a bit more clarity and consistency on their purpose.
I think the above thought process (referring to waterfalls's post) is not correct. Think about it this way:
Say there are 10 pretests (standard) and 60 total tests. Say that there is a probability p that you get hash collisions. (One can compute p with some NT maybe...) Let's assume p is fairly small.
The probability that you pass all pretests is: (1 - p)10. The probability that you pass all tests given that you pass pretests is
(1 - (1 - p)50) ≈ (1 - p)10·(1 - (1 - 50p)) = 50p. So if p is something like 1 / 100, you'll pass all pretests with something like 90% chance, but pass all final tests given that you passed pretests with only 50% chance. It could just be a probability thing. The 90% is probably even an overestimate given that most pretests are very small cases, so p ≈ 0 in those tests.
If I did shitty math, please tell me.
In problem B of division 2 O(N^2) is passing system testing
Good problemset I'd say.
My solution has been skipped ...
I do the Contest & solve the Problem for Upgrading my Rating ... then why this types of injustice ... Watch my submissions ... They didn't match to any others but any others submissions match to mine ... But why should I get the Penalty of rating loss?? what type of injustice is that ???
Newbie solved problem c kinda sketchy no?
Top 4 lines of your solutions A and C say it all :P
OMG, waiting for rate changing will kill me one time.
Auto comment: topic has been updated by Xellos (previous revision, new revision, compare).
for problem(A): My code passed all pretests but was rejected in systesting on testcase#45. When I run this testcase in my pc its giving correct answer, u can see my code in my submissions.
Test: #45, time: 0 ms., memory: 0 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER Input 9 39 10 20 16 36 30 29 28 9 8 9 38 12 36 10 22 6 3 19 12 34 Output < Answer = Checker Log wrong answer 1st words differ — expected: '=', found: '<'
dont use power function. your code power function does not work correctly.
so, if a=2,and b=3; find a^b; for(int i=1;i<b;i++) { a=a*a;
}
where does it not wok properly? why its working on my pc and not on codeforces ? plz explain.
Now it is midnight,but still wait for rating. After brainstorming ,pain in the brain. So,plz give the rating as soon as possible.
It seems that many O(N^2) algorithm are passing system tests for test B. I think the solutions for atleast B should be rejudged.
yeah, now today was surely a bad day I solved 2 problems within 50 mins and both of them was rejected during system testing and I dont't know why . for problem A if the power function doesn't work , then it should give wrong in my pc too but when i checked ,the answer is correct in my pc.for problem B its giving TLE after system testing. Is anybody having the same problem ? can anyone explain me why this mismatch is happening?
Man i am saying that O(n^2) solutions are not bound to pass because n=100000 but i saw various problems in which it is passing in 1900ms
Ok they have carefully applied n^2 breaking the inner for loop when required but the setter needs to create such cases where these solutions do not pass.
It is no first!
fnf47 do you have wrong answer on test 45 on problem A?
yes JustInCase in system testing it gives wrong but is fine when i run it on my pc.I read the above comments but still the concept behind this is not clear to me .There must be some valid logic behind this.
Do you use pow function?
yes,and now its accepted . I used ceil(pow()) instead of just pow(). But one thing is still bothering me , if pow(a,b) gives wrong result on codeforces for some a,b then why its correct on my system?
The way that mathematical operations are done on each computer can be different as different processors can use slightly different algorithms for certain mathematical operations. If you went out and bought the exact computer they are working on and compiled with the same compiler, you would get the same result as on CF.
Мне одному кажется странным что в топ30 ни одного нового пользователя? ^_^
When will rating changes be updated?
the ratings have been updated
http://mirror.codeforces.com/contest/602/submission/14446757
Guys, someone hacked my solution with TLE. Why isn't it passing, it's O(N^2) on 10e6 max
O(N^2) = 10^6 * 10^6 = 10^12 so TLE
It's 10^5 actually 100 000
so, O(N^2) = (10^5)^2 = 100000 * 100000 = 10000000000
Is it ok???
10^5 with O(N^2) passes in the tasks i solved.
No, only with some smart optimizations (breaks).
O(n^2) cannot pass all tests.
Editorial...
I had the problem after the contest finished: the judge skip my 2 solutions for A and B. I have taken part in more than 100 contests of Codeforces and although I didn't do it well, I never cheat or do something like this. I don't know why. :(
I tried Div2 B in Java during the contest : link
and got TLE in test case #22 in the main tests
Then, I tried submitting the same code in C++ : link
I've used the same logic for both the solutions, yet the C++ solution actually gives TLE only on test case #31.
Why is the solution time not adjusted depending on the languages? :/
Well, yes, this time it didn't make any difference, but some other time, maybe it would?
А где разбор?
http://mirror.codeforces.com/blog/entry/21755
What a likeness!!!
(602B - Аппроксимизация постоянного диапазона)=((6E - Экспозиция)-(cout<<b<<endl;))
It was enough to copy and paste someones code to get accept in this task.
Just read both problems.
And I found something more interesting.
Please see these two :
466C - Количество способов -> 12811058
21C - Полоска 2 -> 14870971
Exactly the same code.