Hi everybody!
When you've seen my nickname you probably thought: "Finally! At least this round is not made by Sereja! And you are right! I, Dmytro Berezin(Berezin) give this round... and my neighbour Sergii Nagin(Sereja)
The action will take place in Friday, 25th october, 19:30.
Thanks to Gerald Agapov(Gerald) and Maria Belova(Delinur) for help in preperation and translation of problems respectively.
Thanks to Yaroslav Tverdokhlib(KADR) for help in testing.
You have to help Dima equip his personal life :)
The point values for this cause is 500 1000 1500 2000 3000.
Sergii strongly recommends you to read all the tasks.
I highly recommend you also to try to solve them.
Thank you for your attention, and have a successful round!
Tutorial: http://codeforces.me/blog/entry/9334
I hope that it will be a good contest for every point of view as Sereja's contests.
I hope so )
the law of conservation of Sereja : Sereja can be neither created nor destroyed, but he always go from a contest to another contest!
I hope you guys have managed to solve the problem with the servers from last time.
Testing was a breeze. Thanks a lot guys.
I hope that the English problem set is not the same level of English as this post!
I am really sorry for the level of my English, if you read my bad-english post attentively, you will find, that english problems are not translated by me.
What?? You have advanced level Enlish in university and bad English at codeforces))
problem set is level of English? do you knoving engrish?
Sereja is a hard-working and good problem setter :)
good luck all :)
I hope it will be a interesting contest and everyone will enjoy and learn more knowledge from this contest .
I don't know if I'm the only one but I'm having tough time understanding the statements.
This is the first time it has happened to me since I've joined CF. :(
Why so hard-thinking & tough understanding problems in this round... Dying for none solved problem...
a very awful only DIV 2 contest
Could someone explain solution of Problem D?
DP problem: DP[i][j] 1<=i<=n 0<=j<=1
DP[i][0]=the answer of the first i hares when before i,feed i-1;
DP[i][1]=the answer of the first i hares when before i-1,feed i;
final answer will be max(DP[n][0],DP[n][1]); sorry for bad english.
I'm still not sure if this solution will be accepted, but here's a simple one:
State is the current hare and a flag whether the last hare that was processed was fed before the current one: 1 if it was fed before, 0 if not. So if the last hare was fed before the current one the value for this state is max(b[current]+state(current+1, 1), c[current]+state(current+1, 0)). Otherwise it's max(a[current]+state(current+1, 1), b[current]+state(current+1, 0)). The reason why this works (I hope) is because the only thing you care is whether the current hare was fed before the current-1 and whether it was fed before the current+1.
Problem C
Tell all extracted numbers to Inna and then empty all containers.
I guess lots of people who got WA#10 didn't see then empty all containers.
Also I found a bit tricky that the sequence of operations doesn't necessarily end in 0, so you can do whatever you want with the last numbers.
yes my very first submission failed on this test case (pretest 3).
but there was another tricky case is when there are more than 3 elements before a 0 with the same maximum value (pretest 5). example
5 5 5 5 0
this failed my second submission 4886056 :Pmy third 4887916 passed all the pretests, and, thankfully, the system tests! :)
I am one of the victim :( .
oh my god...i missed that... so sad......
I missed the exact same point!
What a great problem for C! One of the trickiest problem i've ever seen. Fully apprecieted, thanks @Sereja!
Although, i spent too much time on it. After i solved it [as i think now, before system test :D], this problem idea made my day! Nice~!
It was Dima's problem)
Oh, i see ...
Thanks a lot @Berezin !
Thank you :)
please explain problem c for me I dont understant that
I'm quite astonished. After finishing C, I wrote a DP solution for D, but that runs in O(N^3). After getting TLE in pretest 12, I just had one minute left so I just limited the internal loop to 100 iterations, so the DP would not be computed correctly in some cases. But still, my solution passed the final tests. So lucky :D
4890679
here is my problem C, wrong answer on pretest 3 http://codeforces.me/contest/358/submission/4890344 pretest 3, give 0 as n, which is totaly against what it says in the problem: The first line contains integer n (1 ≤ n ≤ 10^5) — the number of Inna's commands.
The input of pretest 3 is clearly seen:
2 0 1
So, I advice you to check it again more carefully.
yeah i figured it out, nothings wrong
very quick system testing for 3500+ users. problem A gets severely affected.
In problem B it was mentioned that message size will not exceed 10^5 but test 24 was. 100000 i . . i For which message size will be atleast 3*10^5 . It cost me WA . Its cheating. :'( :'( . Someone must look into this.
Not really, it would have to be at least 3*10^5 if the answer was yes, but it's no.
no, the problem only guaranteed total length of all words doesn't exceed 10^5 which is valid for that test, and that doesn't mean it also guaranteed all words + '<3' also will not exceed 10^5
Not really. It does not say that the text message will contain all the read words.
how did so many users fail the system tests of problem A?? o.O
was there a tricky case? there must have been one, because it's impossible that so many users were incorrect with their ideas!
Can someone explain how Prob A is to be solved? I started off wrongly and got entangled, realizing mistakes after every wrong attempt.
the only way there is a self-intersection is, when there are 4 points of the form
i j i j
, meaning that a semicircle goes from point 1 to point 3, and also another goes from point 2 to point 4.a.k.a you have two segments, given by coordinates x1a,x2a(left,right) and x1b,x2b(left,right) and the first should start before(strictly) the second and should end before(strictly) the second
There are four cases, handle them and you get AC:
let A,B be the last two points entered, and C,D be each pair entered before. These patterns are the only one producing entanglement:
ACBD BCAD CADB CBDA
(Note that if you have XYZ entered before, you handle the pair (x,y), then (y,z), etc)
actually the cases can be reduced if A = min(x1,x2) and B = max(x1,x2)
it is easy to check when they do not intersect, so you have [a1,b1] and [a2,b2].
they do not intesect if b1<a2 or b2<a1- the case when EXAMPLE: E1:([1,4] and [5,10]) and
E2:([5,10] and [1,4]) and when one interval is subinterval of the other so: (a1>=a2 && b1<=b2) || (a2>=a1 && b2<=b1) example:
E1:([4,7] AND [1, 8] ) E2: [1,8] and [4,7]) so you check every connected pair of points.
Thank you, everyone! :) I got it! Consider x1, x2, x3, ... , xn. Make pairs (A,B) for all x(i),x(i+1) such that:
A=min[x(i) and x(i+1)] and B=max[x(i),x(i+1)]
Now, consider 2 segments (P,Q) and (R,S).
P ---------------------- Q
'R' can lie either within PQ or outside it.
R---P--------------Q
S can either lie outside or inside. If S lies inside PQ, then there is an intersection, else there is not.
R---P------S-------Q (intersection) R-S-P--------------Q or R---P--------------Q---S (no intersection)
P -------------R-----Q
If S lies Outside PQ, then there is an intersection, else there is not.
P -------------R-----Q---------S (intersection) P -------------R--S--Q ( no intersection)
So, it is just 2 cases we have to check, if we make a min/max pair.
Actually you can get past the problem with brute force( O(n^2) ) by treating only one case.
Awful translation, made me unable to solve problem D. If hares 1 and n only have one neighbour they should be unable to be in the state where they have both neighbours full or empty but in the first test case it is clearly visible that the answer is 4+3+2+4 or 4+2+3+4, both cases leading to the last hare getting its happiness from BOTH his neighbours being empty (what an evil hare!!!)
Can someone explain that?
By the way, Sory for mi bad englando!
What's the problem, then? The sample clearly explains that question. That's what the samples are for — clarifying the problem statement (and testing the program, of course).
And it kind of makes sense, if you imagine the happiness values given per number of full adjacent hares, which is at most 1 for the border hares.
"Inna knows how much joy a hare radiates if it eats when either both of his adjacent hares are hungry ... or both of the adjacent hares are full".
Last time I checked both was considered as being two.
Yeah, the translation isn't precise, I give it that. But I'm saying it shouldn't pose a problem in the contest, as long as you look at the samples and try to understand them carefully.
Being less than precise, it's contradictory.
I understand that nobody is perfect and I do not mind grammar and other translation mistakes but the fact that annoyed me was that at the question :
" In the first test case, to get to 13 happiness the last rabbit should be fed before both his adjacent hares ("Number ai in the first line shows the joy that hare number i gets if his adjacent hares are both hungry") but this would be imposible because the last hare does not have two adjacent hares. What should be done? "
I received: "Read the problem statement."
I'd have replied something along the lines of "That's allowed" instead, since the inclarity really comes from the problem statement being what it was.
But the way I see it, you're nitpicking about formal correctness too much during a contest, and that might have cost you points. You really could've just decided based on the samples, instead of asking. (I try to understand the samples instead of the statement quite often :D)
I understand that I might be too strict about these things but I learnt from life( pointing at programming contests ) that If you don't make sure of every last detail you will most certainly regret it later.
And along the lines of understanding the problem from the sample cases, why not go as far as to give the contestants only the sample input and output: "Let them figure out the problem statement!" ?
Trust me, there are much worse statements. Here, the basic idea of the problem was clear, yours was just a minor question. For example, I didn't even think about it (but I would, if there was an answer "Impossible" mentioned in the statement) when I read the problem. (Apart from it being formally incorrect, ) it's not nearly as bad as you make it seem.
I guess it just takes experience with reading problem statements.
"Just because other kids do drugs at his age we should go easy on our own for skipping school."(or something along those lines)
Besides, not everyone has the same mentality:
While you and probably the majority of the "red community" could make out a poorly formulated problem from the available test cases, I and maybe others below the "purple grade" will have difficulties in understanding it. To be fair for everyone, why not make it correct?
Lol, it says my comment can't be nested anymore. We need to go deeper :D (Maybe it's best to consider this the end of discussion, since we don't really have more to add.)
On topic: yeah, I'm that kind of guy. I simply accept small imperfection (and bash at large one that much more :D).
Of course, all is a matter of opinion. I just want to say what I think about it. But it may be precisely because of mentality that I got this far — to be precise, it's "if you aren't doing well enough, just try to improve as much as possible". Things like this, I take as a challenge. I still have ways to go, though. Red is just the "can solve easy/medium problems in time" level.
Very nice round — congrats to writers — , but I think that you sould put more pretests if you make statements that request answers "yes"/"no".
Does E involve eulerian/hamiltonian paths?
Yes, it involves Euler tours on an undirected graph.
First, vertices: for each possible K you can extract a graph of which points were directly visited: Assuming the upper-leftmost point is at (sx,sy) then exactly all points of the form (sx+i*k, sy+j*k) are intermediate positions for the victim.
The remaining '1's indicate moves from one intermediate point to another, so if there is an unbroken line of points between (x,y) and (x+k,y) or (k,y+k) then an undirected edge should be added between them.
A valid sequence of kicks corresponds to an Eulerian path through this graph, so you just need to apply the standard algorithm for verifying that one exists.
I was taught that a fully-Eulerian path starts and ends at the same vertex, but a semi-Eulerian path begins and ends at distinct vertices.(upd.: above definition is wrong.)In the former case, any vertex will do as a start point because the tour is closed and cyclic.
In the latter case, the two endpoints will be the only ones with
edges.length()%2 == 1
and either will do as a start point.In practice you don't need to explicitly identify start and end points -- you can just check that the graph is connected and has either 0 or 2 vertices with an odd number of edges.
Ok, thanks!
Interesting, I was taught that a Eulerian circuit starts and ends at the same vertex, while a Eulerian path in distinct vertices.
Yes, after a quick check it turns out that "fully-Eulerian" and "semi-Eulerian" are supposed to describe graphs, not paths.
Maybe my teacher was a little confused. Alternatively, maybe it's time to invest in a hearing aid and/or start paying more attention in lessons.
Revised the wording -- thanks!
Sorry but for B, why this case is a "yes" ? 3 i love you <3i<3love<23you<3ww I thought he can only insert "digit", "<" and ">"
Then Dima inserts a random number of small English characters, digits, signs "more" and "less" into any places of the message.
oh I missed that, so sad :( small characters mean "lower case" right?
yep
by the way the accepted solutions output is "yes" for 3 i love you <3i<3dont<3love<3you<3
as "dont" can be counted as " a random number of small English characters, digits, signs "more" and "less" into any places of the message. " it is within the bounds of the statement
The contest is over, so now we can see the truth: Dime will never send such sms, so the answer is "no" :) P.s. but the comment above is correct when speaking about contest rules.
as a matter of fact it's not an encoding, decoding system, the better way was not using the terms encoding and decoding, the translation is one way it should be noted finally I should thank the writers there is a little mistake doing a great work
haha :D
costed me 3 WAs, but finally ACed
Tired of being victim of overkill :( Solution of B was doable in 10 lines, instead I choose the long way..
Could anyone help me why my submission 4899840 can't pass Test 12?
For: 3 i love you <<<<3333iloveyou
Your code outputs yes while it should output no. The problem with you code is that it does not check if the characters are in the right order i.e (<3word1<3word2...), it just checks if they are there.
It's something similar to this: If your program would check if two words are the same, the words "love" and "elov" would be the same.
Thank you so much for answering. I found where the problem of my code is with your help. I changed
pos=sts.find_first_of(s[i]);
in my code topos=sts.find_first_of(s[i],pos);
and it was accepted successfully. :)Loved the contest. Just depicts where a contestant's reading and interpretation skills stand.
I wrote the code for Dima and the Text Messages in CodeForces Round 208 division-2 in Java. Every time I submit the code it says TLE. But don't know why it says so even if I am using BufferedReader and PrintWriter for reading and printing the values. My solution code in 4901148.
In Java
a + b
is slow for strings (copies botha
andb
), you have to useStringBuilder.append()
instead.