Всем привет!
23 апреля в 19:35 по московскому времени (время в вашем часовом поясе по ссылке) состоится рейтинговый Tinkoff Challenge — Elimination Round.
Задачи готовили я — Ильдар Гайнуллин, Александр wrg0ababd Курилкин и Николай KAN Калинин.
Большое спасибо Владиславу winger Исенбаеву и Александру AlexFetisov Фетисову за тестирование, Николаю KAN Калинину за помощь в подготовке раунда, а также Михаилу MikeMirzayanov Мирзаянову за системы Codeforces и Polygon.
Участникам будет предложено семь задач и два часа на их решение. Разбалловка будет объявлена ближе к началу раунда.
Этот раунд — отборочный раунд Tinkoff Challenge, анонс которого можно прочитать тут.
Лучшие 30 участников получат теплые жилетки и мелочи, в духе наклеек и блокнотов. Первые 100 мест приглашаются на экскурсию в московский офис с панорамным видом на Москву.
В финальный раунд в офис Tinkoff приглашаются 20 лучших участников отборочного раунда из числа тех, кто сможет приехать.
Надеемся, каждый найдет для себя интересную задачу. Всем успешного раунда и повышения в рейтинге!
UPD. Разбалловка: 500 1000 1500 2000 2500 3000 3500
UPD. Разбор
Nice anouncement, hopefully the problems will be cool. Good luck to everyone and no rating drops!
Nice announcement. Hopefully all the problems will be cool. Good luck to everyone and no rating drops!
rateng ke chenj haba?
My profile picture advertises Tinkoff nearly a year. I think that I deserved automatic invitation for the final :)
Unfortunately almost nobody noticed your profile picture is about tinkoff before you say that :D
Wishing problem description will well translated in english.
On April 23, 19:35 MSK will be held _rated_ Tinkoff Challenge – Elimination Round.Thanks.. I don't notice that.
.
Nope
Is the round rated?
for you no
Are travel cost and staying cost paid for top 100 participants?
Just a begginer's doubt: From what I understood, the round will be rated for codeforces, but shouldnt it therefore be called "Codeforces Round #411 — Tinkoff Challenge" or so?
As I know, the prefix "Codeforces Round" will only be added to the mirror version of a championship or a competition that didn't be held on Codeforces officially. However, Tinkoff challenge is held officially on Codeforces and that why they don't add the prefix.
I thought the same thing, usually there are div1/div2 mirrors for things like this.
Can anyone tell me how difficult it is
Does it matter ?
/
The name "Tinkoff" sound super cool to me, though I don't know Russian. I really want to get the Tinkoff vest!!
It means this guy :)
Oleg Tinkov
I am his big fan :D
I think you might have meant that you are his big fan. Although, even if "you are his big fun", who am I to judge ? ;)
Deleted
Hopefully the statements will be short not like Google Code Jam yesterday xD xD
Any previous round of Tinkoff Challenge?
Is this contest rated for div2(<1900) people?
why not?
Ok. thanks.
Это раунд вида "div.1 + div.2 combined" по уровню задач(round D = div2D = div1B)?
должно быть, да
Let's stay up late tonight!
Will this contest be rated for all?
YES, it is said in the article.
i registered 5 hours ago successfully, no doubt about that. But now showing i am unregistered :O :O , also that happens to one of my friends also. please fix this.
Will there be any geometry in the contest?
It is interesting to see your reaction for each of the 2 possible answers. Let's model the situation and you get the following comment from the author:
Yes, there will be a geometry problem.
How would you react to that?
No, there won't be any of that kind.
How would you react to that?
i bet no
I bet yes :'D
You've jinxed it...
:C
Why?
UPD:Fixed
Still no scoring announcement?
UPD. Scoring: 500 1000 1500 2000 2500 3000 3500
55 minutes after the end of Tinkoff Finals, GCJ Round 2 begins. I wonder if the Finalists can participate in GCJ.
GCJ Round 2 begins? what is this? Google Code Jam?
There is an answer in russian branch (you've studied russian, am I right? :)) from one of the event organizers: "I also want to write GCJ, so we will end until R2 begins"
Seems like the round is delayed for 10 minutes (19:45 MSK). Then right after this round is finished, El Clasico will be started. :")
I wanna watch el clasico...please Start it soon :((
10 minutes late.
Was the contest delayed? I thought it was at 19:35MSK but it looks like it's at 19:45MSK.
This contest has the most beautiful timing I have ever seen. Actually I am very happy because I don't have to wait for the system test.It's El-classico after this contest.
Я с тобой согласен)
Why delay in contest time?
Why not*
It's codeforces' usual
FA Cup Semi-final: Arsenal vs Man City match perhaps :p
Better delay the round rather than have long waiting queues during the round =)
Are the judging servers frozen or something?
Long Queue :/
Что не так с 24-ым тестом в задаче D?
Ага, молодец.
что за 7 тест в задаче С?
Well this round certainly "eliminated" me.
Anybody knows the reason of WA10 on C?
Send the code, so maybe we can find the error in it. I got pretest passed for first on C, but I know I'll fail system test, and I couldn't get another pretest pass from 3 more submissions. I got RE4 for the submission I think was good :P
I can only hope, the system test will be weak.
Something like point can have speed vector of zero length
In problem D debugged 1 hour in test 4 and find out the edge is directed in the last 5 minutes and don't have time to optimize...
#ggneedaglassesPS. More unfortunate, I set wrong initial value for my dp array and led to TLE.
This thing just ruined my contest. Didn't even think about it before I read your comment :(
Очень радует, когда много задач на идею, и не нужно много реализовывать !)
Идейная C. Мммм...
Так я тоже
B и С очень интересные.
как кратко решать B?
Someone fooled me by
#define int long long:(laughed too hard on this one
How to Solve C?
I did ternary search to get when will a mouse be inside, then binary search in both directions to get the total interval each mouse will be inside
Use binary search for the time. You can check if after some time the mice has went out already of the trap, is inside it, or hasn't gone to it yet.
First, you can see that a mouse will be in one segment of time
(tEnter; tLeave)(or it won't be in the trap all the time, then the answer is -1). To find these segments, we can find intersections with the lines that make a rectangle.Then, we make the events such as {mouse
xcame to trap at timet} {mousexcame out of trap at timet}. Sort them and process consecutively. If we found the "came to trap" process, we increment the amount of mice, otherwise decrement. If we found in some point of time that there'renmice, we just output this period of time.Let's pick a single mouse. Assume for simplicity that vx > 0 then the mouse will be in the right x area if x1 < rx + tvx < x2 which is equivalent to requiring that
(simple algebra). You can do something similar for vx < 0 and when vx = 0 you either pick the empty interval or all of [0, ∞) depending on whether x1 < rx < x2 or not. When you do the same thing for y and intersect these two intervals, you'll get the time during which this mouse is in the trap.
Do this for all mice, intersect all of these intervals and pick the smallest non-negative value it contains.
Hack case for C?
I didn't hack with it because didn't have time, but
1 99999 99999 100000 100000 -100000 -100000 1 1
seems a pretty good hack case to me.
Yes. My solution fails on this. Thankyou!
I hacked with this simple test:
1 1 1 3 3 0 1 1 0 (answer: -1)
The idea is the mouse runs along the border of the rectangle, but is never strictly inside it.
Yes. I didn't take care of this part. Thankyou!
:( didnt check strictly inside
Very cool picture in the statement:
I thought when mouse at borders it means mouse in mousetrap
Aware of the hack case in the last 5 minutes but I was panic and unfortunately only fix this after the contest end for 2 secs @@
for C , double -> WA , long double -> AC
UPD:WA
Let's wait for system testing and see how it goes :)
I implemented solution in such a way that it feels risky even with long double :)
Upd. You got WA due to using eps, not because of double. For me using double still works: 26638771 (I have no idea if it is actually OK to write it this way).
WHATT?? NOOOO! :(
Пока решения не проверились, я могу быть хоть более-менее объективен. У меня вагон и маленькая тележка причин опасаться за своё решение по задаче C. Такие задачи, на мой взгляд, очень не подходят для формата CF, ведь маленькая бага в верном решении может стоить слишком дорого. Задача слишком багоопасна.
Целочисленное решение с использованием long long зашло. Больше не буду начинать раунд с таких задач, слишком тяжело психологически писать и тестировать локально такую жесть. Я бы поменял эту задачу местами с D.
Is c ternary search on max distance between point and rectangle?
Can anyone tell me if this approach is correct for C?
Binary search on the time. Translate each point. If the line from the original point to the new one intersects the rectangle and isn't inside the rectangle then I need to lower the time. If the line doesn't intersect the rectangle then I need to raise the time.
If I need to both raise and lower the time, the answer is -1. I couldn't get past pretest 4 (I also made sure to find all corners of the rectangle since they didn't give the top left one).
Yes, the approach is correct, probably there is an error in the implementation.
Why is the hacking page so unstable? I really wanted to hack, but the page was just showing "loading circle" infinitely.
the hacking page was stable for me the whole contest.
It also might be browser related. The same thing was happening to me in chrome but I swapped to Microsoft Edge for a sec and the page loaded. Not sure if coincidence or not since I didn't try again.
Thx, I'll try in the next contest.
I encounter the same trouble after hacking one submission.
IMO problem C ruined the contest
B also.
What's with B? Is 4 state visited array enough to ac ?
Only implementation, as you can see even reds skipped this implementation because it is annoying.
http://ideone.com/9QCTSi As you can see, it's quite easy to implement, you even don't need bfs
Yeah, cool 80 lines for an B!!! How quickly did you get the idea comparing with how quickly you coded it?
P.S. I did it easier with 'only' 4 fors and a lot of ifs.
I did it in a clean way without any case handling: Click
EDIT: Nvm , it failed systest :(
Actually it is possible to code it nicely. You can just fix a column (row) of swaps and check with partial sums if paths (start, firstChange), (firstChange, secondChange) and (secondChange, end) are empty.
https://pastebin.com/iep38bf6
This is how I coded.
What was the Hack case for C ?
Why?
At the end of the day I'm really happy with this problem because I discovered something which was surprising for me.
I represented an empty interval as a pair (-1.0, -1.0). I mantained an interval of possible trap closing timestamps. I forgot to check at the end if it was empty. So sometimes I print -1.0000000000 instead of -1. It still passes, of course :D.
It was hilarious, really :D.
Anyway, I agree that it was messy.
Task were tehnical, tehnical and tehnical.
Good bye, my rating.
Welcome to div2 :)
Or nope :P
I can not believe that pretests for B were so weak, I forgot half of task and didn't realise it till end of contest.
Didn't read this for almost 50 minutes, got WA 7 times, :'(
I'll probably get down votes for saying this but I really did not enjoy this contest. The problems were not interesting to solve — just extremely annoying.
Yes, B is hard for a B. and C is too long.
I agree with you !
The sample cases on the tasks B and D weren't good also. In B, there were only cases with
n=m. In D, there was no case with-1.It's always good to give a case with
-1in samples (except the case when finding the test with-1i stricky and requires good thinking skills).My solution for D failed pretests because I forgot about
-1I think this problem can't be B problem :(
Contest duration was obviously not long enough.
How to solve D, I had following dp state -> (left,right,start,k) where [left,right] is allowed range, start is always left-1 or right+1 and k are required number of nodes to be visited?
I had this following dp[current_city][min_city][max_city][k]. At each state you can only visit another city x if min_city < x < max_city.
used the same :)
Tried the same but didn't notice that edges are directed :(
Yes, my recurrence is very similar.
solve(pos, left, right, done) where pos is current position, done are number of banks already gifted, and left and right is allowed range, initally 0 and n-1 respectively.
Then for the recurrence,
Iterate all i in range(ll,rr): solve(i,left,pos-1,done+1), if i is on left of pos solve(i,pos+1,right,done+1) if i is on the right
same
Can anyone explain how to solve D ? thanks!
you can use Dynamic Programming Your state is (int start,int end,int current,int taken) indicating left boundary , right boundary , current position and number of visited offices note that the state can be redefined to save some memory i hope it's efficient enough to pass xD
dp[l][r][last][k] = min cost when you can move in l,r and last city is last and we visited k banks. But it is slow. So we can notice that l or r will be equal to last, and we can remove r so it will pass.
So hard problem for B :(
I wasted about 40 min on it :(
I thought I was overthinking to use dfs in a B
Me too, at last, I use bfs
Is there an error in the following function?
I get the time to reach each of the sides of the rectangle and get the min/max from these 4 values. If the code is not clear, please tell me about it and I will try to improve its readability.
Too many real number problems now a days. Too many precision issues while solving such problems. I estimate atleast 2X people would have solved problem C today if we had to deal with integers only.
The real number part is such an unnecessary complication to a rather not so difficulty binary search problem.
Some people including me used only integer arithmetics in C. And you don't even have to do binary search.
Seems like that wasn't the case :|
I failed due to a dumb mistake, not because integer arithmetic solution was wrong.
UPD: I didn't handled the case that all mice do not move. Fixed it and accepted. :(
26625743
I think the goal of the problem was to require integers (or understand float numbers well).
Test for problem C:
2
0 0 2 2
-1 -1 1 1
1 0 -1 1
Upvote if your solution fails it)
the answer is?
The answer is -1.
At moment of time 1 they all stay on borders.
At moment of time 1 + eps one mouse enters the trap, the other one leaves the trap.
coordinates must be non-negative
you can just translate all given points, e.g x+=100,y+=100
My program gives
1.After one second both points will be exactly on the borders of rectangle, so -1
It looks like I've ignored the boldest part of the problem statement once again "... strictly inside the mousetrap."
I'll feel embarrassed if my solution passes after I change '<=' to '<' in my code =)
Upvote my comment.
Can I downvote please if my solution passes it?
I think the answer should be -1. The first mouse enters the trap as the second mouse leaves, but they are both never strictly in the trap. Correct me if I'm wrong.
should the answer be -1?
Mine passes but I still couldn't get past pretest 4 :(
I think problem D was a nice DP of the form Dp[d][left][right][v]. Where this value stores the cheapest path starting at v of length d using vertices only between left and right. Unfortunately I stored my vertices from 0 to n-1 and forgot to subtract 1 in the input. Now I'll have to wait a bit to check if it was correct.
Very Nice Problems, thanks.
Am I the only one who did C like this:-
Consider x and y coordinates separately, and for each mouse calculate the time interval [t1, t2] such that it's x coordinate will be in (x1, x2), and similar for the y coordinate using math. Handle cases where Vx or Vy = 0 separately (either they will give (-inf, inf)) or impossible.
Then take the intersection of all such time intervals to find the answer. Is this correct?
Link to solution
(Might not be visible just yet I guess)
I did the same.
i did the same, though i wonder if i will get ac
I too did try to do the same but shame on my poor implementation :(
it happens to all of us :)
I've been looking at your solution, it's quite clear. How do you handle strictly inside condition? I could not see anything for that.
I maintain (t1, t2) as the interval where all mice are inside the mousetrap, and notice at the end I check if t1 >= t2, the answer is impossible.
If t1 < t2, then there exists some x = t1 + epsilon such that at time x, all mice will be inside the mousetrap and x < t2. Therefore, we can print t1 as the answer since epsilon in infinitely small.
Another thing to notice is that the only possible cases where the mice will be inside but not strictly inside will either have Vx = 0 or Vy = 0 (which I handle separately), or the mouse will touch one of the corners, in which case the interval produced will be of the form (t, t) and hence it will fail the t1 >= t2 check.
How to solve D? I've tried to run floyd-warshall with a slight modification in the relaxation step:
if (i < k && k < j) continue;. For all paths with length k (number of offices), my answer was the one with shortest distance.What am I missing?
Statement for problem C is awful, just awful. It never explains what 'strictly' means exactly, and the sample picture leads to the wrong conclusion.
It's a common term and you could have asked about it.
That means that the answer is always either
0or-1since otherwise the minimal required time doesn't exist since the set of all possible times is open.This issue doesn't mean that "strictly" becomes a less known word. Don't expect organizers to think: there is that issue we didn't notice, so let's explain a word "strictly" in detail.
I agree, this doesn't make word "strictly" less clear, however, this makes the whole problem (and especially its question) more complicated and suspicious (since formally authors want something other than they ask)
Hmm, you also had
Wrong answer on pretest 7, didn't you? =)In B, what on earth test case 9 could've been? Got many TLEs on it, while having tested my algorithm for large inputs. Had to use a clock with time checks to bypass it :c
That moment when a legendary grandmaster hacks you (⁄ ⁄•⁄ω⁄•⁄ ⁄)
Nice difficulties (except for too complicated B, unless you didn't expect people to implement dfs) of problems but the contest was too short.
Please add more samples, especially to check that contestants understand the statement correctly. In B we had h = w. In C, samples didn't check for "strictly inside". In D — undirected edges also worked.
I don't know why CF sticks to 2 hour contest time. I haven't seen a rated round with more than 2 hours. I know it's about speed also, but sometimes (for example now) we could really use 30 or 60 more minutes.
Why system testing is so delayed and still pending ?
Update: System testing started now :)
I need some help in Problem C.
My Wrong Approach is :
For every mouse I get the time when it (enters) the rectangle By getting the intersection between the line made by the mouse and the 4 segments of the Rectangle.
If there is a mouse which will never enter the Rectangle or will stay forever on a border I will output -1.
Now I will get the time T at which the last mouse will enter the rectangle.
I will check that all the mice after time T will be in the rectangle or on the border of the rectangle. If this is true then I will output T, otherwise -1
So What is wrong with my approach ?
think about the case which a mouse in the rectangle at the beginning?
Yes, I handled it.
The mouse should be "strictly inside" the rectangle and not on the border.
Yes, but but if they are not moving towards a border then for sure they will enter after time T. So I outputed T because there is a tolerance of 1e-6.
How this can be rated contest for div2?
Can we see others' solutions please?
If you interpret it literally, the statement of problem C had a small problem: If all of the mouses are not already inside the mouse trap when the time starts running, there won't be a minimum time when all of them are strictly inside it. I guess that the problem was intended to have asked for the infimum of those times, but if the mouse trap is closed precisely at that time, some mouses might be on the boundary.
That's right, according to the formal statement, the only possible right answers are
0(if the mice are already strictly inside at moment 0) and-1(since there is no "minimum number strictly greater than a given number"). So, the statement formally contradicts the first example. Which is bad (Captain Obvious here).I remember the same exact issue handled gracefully in a statement here at Codeforces in the past, but don't remember the exact problem. If someone does remember (past coordinators perhaps?), please give a link!
So the answer is always 0 or -1?
So basically the time that at least some accepted solution outputs (for example, my solution in the upsolving) is the time, when at least one of the mice is on the border of the rectangle, and that's, strictly speaking, OK, because absolute error is infinitely small. But, if there is no such moment (for example, mice "meet" strictly on the border), the answer is -1, which is logical, but feels weird for some reason.
WHEN YOU FOUND A SOLUTION FOR PROBLEM B AND CODEFORCES SAYS TO YOU "CONTEST IS OVER"
The important thing is:
Ориентированные дорожки, серьезно?) С условием было тяжело, несколько задач пришлось перечитывать и разбирать на семплах. B по-моему уже была на каком-то раунде. И тогда задача не казалась сильно интереснее. Интересно, что в G все отправили, надеюсь авторы тесты сделали к такой задаче.
I alone think that this contest required 2.5 hours as many Combined Rounds before?
nlog(n) did not work on first problem. I unnecessarily sorted the array :(. But it is weird why sorting exceeding 1 sec time limit for 10^5 size array?
I sorted the array too but mine passed
Here is my submission
yeah I guess problem is with java. You have used c++. May be something to do with java implementation of quick sort.
Java's sort isn't guaranteed O(n*logn), it can be O(n^2) sometimes. You should shuffle the array randomly before sorting.
Yeah that's what I also thought. Thanks :)
So many failed submissions for C kek
I lost 1 hour to implement DFS in java for B but I got TLE on case 9... Anyone know why? https://pastebin.com/B42rBZgQ
You are revisiting single index again n again
Backtracking DFS takes exponential time. You need to keep track of which places you've visited in your DFS so you don't visit them again.
Thanks for the answer. Do I have to use dp 2d array to save turn needed from each position?
That could work, if you also keep track of the direction you entered the position from.
I did it a bit differently, instead of storing the minimum turns needed I just moved those to the state of the DFS. See http://mirror.codeforces.com/contest/793/submission/26612377
I have a doubt, if you have visited a place with 2 changes and you reach the same place with one change, what should be done? I think that you should take that "visited" node again, but if it is true, what would be the complexity of the DFS?
Actually, you need to store the direction you're going in, and how many changes you can still make. See http://mirror.codeforces.com/contest/793/submission/26612377
The problem with only keeping track of the visited locations in the grid is that, like you noticed, it doesn't capture the entire state of the process.
I really like the implementation, it is amazing, short and clear. thank you.
380 accepted solutions for D, 135 — for C. This summarizes pretty everything about C.
PS changed epsilon from 10^(-9) to 10^(-12): WA->OK. Nice
I'm the only one in room who solved it. Thanks to arsijo for hacking me
Can you share the hack's test case?
In fact, I had 2 mistakes. 1 was very stupid, I didn't check if min time that I calculated may be <0. He hacked me using this.
Test :
1
0 0 10 10
5 5 5 5
My answer : -1
Answer : 0
But when i tried to fix my solution, I understood that mouse speed may be 0. I think test
1
0 0 10 10
5 5 0 0
Or something like this should hack most solutions.
UPD: I checked test everybody had problems with and i don't understand why
I had the same problem. The reason is simply that
1/(1e5) - 1/(1e5 - 1) = 1e-10(roughly), so numbers with large denominators (velocities) can be very close to each other (about denominator^2) when compared.Yes, now that I have thought about it, I came to the same estimation. I just say that it would be great to include such a test (#40) in pretests, cause wrong epsilon is one of the most frustrating reasons for getting WA.
I thought the contest went well... I changed my mind...
Just as the first contest I took in Codeforces, I got 2 FST and in the end rank 1000+. :(
Any clue what case 24 is for Problem C ?
Everyone seems to fail on 24
1 0 0 100000 100000 0 0 1 0 Output 0.0000000 Answer -1
All solutions for G has failed :(
What is intended solution for G? Where are big pretests?
Wake me up, when markysha's submission testing ends
Oh nice!
What was the most elegant solution to B supposed to be?
Solved it with DP.
Code here.
dp[i][j][k][l] is true if we can reach destination being at i-th row and j-th column, after turning k times and moving vertical (l = 1) or horizontal (l = 0).
I think that you should almost everytime fill edges with '*', for simplier solution and use several queues, or struct :) Use Dynamic array, to save best known solution, for some direction.
Yay, i got -50 :) Thanks, for sure you can downwote, pls
My TripleGunShot ;) 26616550
Many Thanks to You all, got it now
On C, there is more "Wrong answer on system test" than "Accepted", right? How do we know actually which one is correct, then? :P
And yeah, this round is a very big disadvantage for those who attempt C first. Not a very good round IMHO
I started with C and succeeded with integer solution. But it was too painful to implement and wait for system testing results.
Represent in the form: p / q.
Actually, Change EPS to 10 - 12 will get AC with long double. Because error can be small as 10 - 10.
Why my solution is wrong for B?!
https://ideone.com/EmkO4J
Why my solution is wrong for B?
https://ideone.com/EmkO4J
UPD: AC (new code: http://mirror.codeforces.com/contest/793/submission/26626324)
In problem D, it says ->
The i-th of these lines contains three integers ui, vi and ci (1 ≤ ui, vi ≤ n, 1 ≤ ci ≤ 1000), denoting the crossroads connected by the i-th road and its difficulty.
which clearly misleads to undirected graph, whole time I was solving for undirected graph, removed one line after the contest and its accepted.
But yeah, I had a sneaking suspicion that it was a directed graph and good thing I found out that word in the statement, or else I would have got WA :D
I got two WA because of that :P
Are the memory limits for B correct, because my submission: 26625940 uses 291044 KB of memory which seems greater than 256 megabytes but yet it still passes, is this right?
To further elaborate why I am not terribly pleased by this, I submitted this Java solution, and saw that on the pretests, although it passed pretests, it already exceeded 256 megabytes of memory, I forget exactly but it was 280,000 KB or so. Thus I rewrote my solution in C++ and resubmitted. Now after contest I find out that my Java solution passes despite seemingly having a memory issue :( Is there some explanation / way to know in future what the actual memory limit is?
Is G solvable by simple recurrence? It's obvious that we want to model some flow network and run Dinic on it, but is this idea good?
We have some recursive function to model flow-vertices for a given rectangle area. If it contains any corners of forbidden rectangles (there are only 4q corners) then let's divide it somehow and solve by recurrence. If it doesn't, then there is exactly one rectangle made of not blocked cells. Is it enough?
How can we prove that a O(n^4 * m) solution for D doesn't give TLE?
BTW, this "brute force with DP" is much easier than the problem C.
At least in my implementation, it is not O(n^4 * m) but O(n^4 + n^2*m) because in each outer loop iteration, I go over each edge at most n times. Probably in your implementation as well.
Can someone point out the mistake in this submission for today's B problem Igor and his way to work ?
It fails on pretest 9
Problem C
WA on Test 40: sadness [ #define eps 1e-9 ]
Accepted: madness [ #define eps 1e-15 ]
same :/
После этого контеста думаю у многих останутся плохие воспоминания о "Тинькоффе". А жаль, могли ведь сделать лучше.
I have two big idea bugs in E and it still passes
To elaborate
1) I thought that each of vertices a and b may get in any place in its subtree (but it actually can't for example if there's big subtree on path from root to it)
2) Instead of checking that number of leaves in subtrees is less than half of all leaves, I checked that it's less than number of all vertices (which is probably always true)
Ah I just realized that I also made your mistake 1). So for the first time I do a really good score, it is because of weak tests... :-(
На контесте, увы, не получилось сдать задачу F за квадрат. Но я-то знаю, что 10^10 должно проходить в 2 секунды =)
Собственно, вот решение за O(N2) в 1.6 секунды.
Если в кратце, то вот такой вот забавный тернарник:
вместо if'а:
меняет вердикт ТЛ на AC =)
Забыл про еще одну магическую строчку:
С ней 600 мс.
Справедливости ради, на весьма примитивном тесте, где каждая нитка — это пара
i, i + 1мое решение работает больше 2-х секунд. Странно, что авторы не добавили такой тест.а что делает магическая строчка ?
Позволяет компилятору забыть о кроссплатформенности и использовать специфические процессорные команды, в частности SSE.
That moment when you read problem B, skip it and read problem C and realise, that its too late to skip this contest coz you already attempted A :/
This may sound very weird
But for question B ,my code gives the correct output 'NO' for the second pretest on my terminal But,it is giving 'YES' when submitted. I am not being able to figure this out.Help will be much appreciated.
This may sound very weird
But for question B ,my code gives the correct output 'NO' for the second pretest on my terminal But ,its giving 'YES' when submitted.
This may sound very weird
But for question B ,my code gives the correct output 'NO' for the second pretest on my terminal But ,its giving 'YES' when submitted.
Maybe you forgot to set some variables as 0? Your compiler may do this automatically, but CF with optimizations doesn't
You should add -O2 command to your compiler because without it, variable in the main function will automatically be set to zero if it hasn't been set any value yet UPD: I think I was wrong. Sorry!
The problem was with this statement:
std::ios::sync_with_stdio(false);cin.tie(0);
Probably, the buffer was not being cleared !
Is there anyone who have done problem B using bfs and not getting memory limit exceeding
Many people, me included. I just use a array with size [1005][1005][4], how can it get MLE?
Looking at your submissions, you got MLE on problem D, not B, and you used 4 dimensional N sized arrays, that is 85^4 = 52200625 ints, which is a lots of memory.
Can anyone give test case #31 for problem B? I don't know why is my solution giving WA for that case, because it seems flawless to me. Could someone point out the error? 26618834
Shouldn't the last dimension of visited be 3 instead of two (since turnsdid can be 0, 1, or 2)? Also, I don't think you need this dimension at all; getting to a given (row, column, dircection) in more moves is not useful, so you can just index visited by (row, column, direction).
Can someone help me? I submited problem C during contest and it passed pretests, but it got WA in test 40. However when I try the test in custom invocation it gets the correct output.
I am really confuse about this. Thanks in advance ;D
26623849
UPD: Solved, too big EPS. Thanks!
Можно побольше инфы про экскурсию?
Guys, why are you downvoting this post and the editorial? I've noticed that the rating of this post decreased from ~200 to 50 during last several hours.
My personal opinion is that it was a nice contest. It featured:
My personal complaint in an editorial post was that in problem G it is hard to prove that any flow-based solution should fit into TL, but KAN convinced me that certain class of solutions should work by mentioning a strong Karzanoff theorem, so the only issues I may possibly see in the contest doesn't actually exist (not even mentioning that this issue affects a really small number of coders).
So, even though my performance on this contest was not really good, I think that authors did a great job and that we should support them, not downvote because your solution failed due to epsilons. Consider this as a good lesson, not as a disadvantage of the problemset. What do you think?
I agree that E is cool (bad tests aside), I didn't have time to think on F and G, so can't say much about them, but great problem C, seriously?
I'm completely serious. It may have some defects in the statement like the fact we have to find a minimum in an open set, but I don't see why it is bad at all.
It's not CF format I think. Maybe they should've added the anti-epsilon test in pretests, it would be better than many failed solutions.
The fact that the smallest possible non-zero difference of two rationals with denominator of magnitude A has a magnitude of ~
? Yeah, that's not a fact for CF round, that's a fact from basic algebra course. Or should the authors always choose the constraints in such way that eps = 10 - 9 works?
I really don't see what's the issue here. You estimate the complexity of your solution by multiplying some numbers from constraints, estimating the epsilon is basically the same. Then why did you fail to do the same here?
Personally I failed because haven't even thought there can be such issue in div1A, so just used standard epsilon thinking "fuuu, another non-interesting geometry problem". If I had thought about epsilon, I would've chosen the correct one of course, but I simply didn't expect this and it was my fault, but I still think this problem is just waste of someone's time and nerves.
Well, I may be too choosy but as for me it was not interesting at all, just bunch of cases to check.
Is it possible to solve B without using a second 2d array for the grid ?
Yes. 26641777
Can you explain =D ?
Let's mark g[i][j] as '#' if it is possible to get from the start to (i,j) without any turns.
Let's find such (i,j):
Try to go upward, until you reach end of the grid or g[i][j] = '*'. Then repeat this for other 3 directions.
Then, mark g[i][j] as '^' if it is possible to get from the target to (i,j) with maximum 1 turn. Let's repeat the described above procedure from the target. It will find all (i,j) wich can be accessed from the target with no turns. Now, if you run it again from all points marked as '^' (obviously, you need to check only sides, perpendicular to your current direction), you will find all points, in which we can get from the target with 0 or 1 turn.
If at some step we need to mark the point as '#' but it is already marked as '^' (or vice versa), then the path with no more than two turns exists. Else it isn't.
Thanks a lot :)
For problem B, I got WA on test 62. Here is my submission: 26615111
Can anybody help me ? What's wrong in my code ?
Update: I have found my bug. I was using visited array as vis[row][col][mov], using visvis[row][col][dir][mov] got AC. here is my AC code: 26632674
I think your code makes at least two moves in the initial direction, so it might fail if we only want to make one move in the initial direction.
I have found my bug. I was using visited array as vis[row][col][mov], using visvis[row][col][dir][mov] got AC. AC code: 26632674
My accepted solution for C uses doubles and doesn't have an epsilon; did I just get lucky? http://mirror.codeforces.com/contest/793/submission/26615231
А че у всех бомбит-то? Не умеете с даблами работать? Нормальный же раунд. Не идеальный конечно, но и далеко не худший, бывало и хуже
Согласен. Например, прошлый контест (VK Cup Round 2) вообще был учебником по математике. Я считаю, что он был гораздо хуже этого. Тут хотя бы как-то связан раунд с программированием. Хотя, думаю, у многих бомбит от задачи B. По мне, так она вполне себе тупая и на уровень B тянет.
Гайс, я раунд не писал, но че не так то? Вы хотите эпсилоны подгонять на контесте с постпроверкой?
To be honest, I was completely shocked when I opened Codeforces today. Shocked and really, really disappointed, as for the first time in Codeforces life I saw a round post having a negative rating. The round had no bugs in validators or model solutions, no serious statement issues, no problems spoiled on the other judges and even no technical troubles. It only featured a signle problem that asked participants "Oh please, dear sir, would you be so kind to turn your brain on and try to figure out what the correct value of epsilon is?"
I think this is a very serious moment for us to stop and look close at our competitive programming community. I always used to be proud of being its part, but this time I feel shame.
I've prepared many contests, but I still experience inspiration and joy every time I prepare and conduct them. And I wish I can again feel how it feels for the very first time you see thousands of people submitting the problems you've been preparing tests for during the whole last week. The fact the authors got downvoted that much is so humiliating and insane it can't fit in my mind.
Dear Codeforces community, for god's sake I ask you to fix it immediately and let's just pretend this never happened.
The round was delayed -- but well, it didn't affect anyone during the round. However, you lie saying that there were no technical issues, but well again, no technical issues during the contest.
The main two problems are the following ones:
1) EF problems had weak systests. Read the comments. One guy passes E with two bugs (actually one of them is not a bug itself but makes the problem wider), and another one passes F for 10^{10} (in the upsolving, though, but this doesn't make the contest better).
2) The round isn't actually about thinking but about a careful hand jo^Wwork. Someone may think it's good for a CF round (and, erm, even claim that it's better than vkcup round 2 problemset), but let these ~5-10 percents of community say whatever they want.
As you see, the third problem is indeed not the main disadvantage of this round, it's just a cause of div2 butthurt. And, well, all checkers and validators are ok, all statements are fine, but without good tests the contest is objectively not very good.
Returning to the main point of your comment, I agree that authors made well enough to deserve positive post rating. I think each participant to get his piece of satisfaction and/or lesson. But please don't call the contest nice just because of absence of things which actually must not ever take place.
I agree with most of your points, but div2 butthurt? reread the comments above. I see red, yellow and purple complaining about C.
Maybe, I could miss this. I just know that many people are mad, and nobody of them is my yellow-red friend.
So you teammate is not your friend, huh?
Or maybe he don't see you as red :P
it's not actually about me
sorry, I misunderstood.
EDIT: maybe he don't see his teammate as yellow-red.
I noticed no butthurt from him, just disappointing and misunderstanding
First off, I have a lot of respect for you and for everything you've done for Codeforces.
However, what is the point of allowing upvotes and downvotes if whenever the results don't go your way, you ask for the community to fix it? We're all used to high quality problems on this platform, and downvoting is the only way to provide feedback when we feel the problems aren't enjoyable/interesting. I agree that negative rating is overboard, but maybe we can all have better contests in the future if Codeforces learns something from us too.
Starting from January I'm no longer a member of Codeforces team, so the text above is no more than my personal opinion. I agree, that upvoting system is a very important quality control tool, just expressed my opinion that the tool got broken this time.
Так может это просто боты заминусовали.
Мне кажется, что сейчас боты плюсуют
downvotes > upvotes=> it shouldn't have been this contest at all :'( sadluckily I didn't read C statement after I saw test case :|
B and G were very interesting
В задаче F очень слабые тесты. Моё простое решение(которое работает в худшем случае за
) залетело за
327 мс. Сразу же нашелся контртест, который валит мое решение.Regarding the problem C.
At first, I want to say that there is my fault that I haven't noticed the precision issue in this problem. In fact, authors' solution (to move the rectangle bounds by ε) worked with any ε from 10 - 6 to 10 - 15, so I thought this was ok.
Secondly, most of numbers we encounter in real life are real numbers, so we should be able to work and solve problems with them. And of course the knowledge about how computers work with floating-point numbers and the ability to estimate precision are not useless skills. That's why such problems have a right to appear on contests.
To summarize, I want to apologize to those affected by the precision problem. If I was preparing this problem again, I would give stronger pretests and/or smaller the constraints. However, I don't see any reason to not give this problem at all.
Well this problem is not suitable at all for a CF round. Man you have 2 hours only and 7 problems which I believe were hard. It is not reasonable to make your testcases that strict so you waste like 15-20 minutes of a lot of contestants time who will write the code very carefully. I mean at least you should make the pretests strong so like 80-90% of people who passes gets ac after the end of the contest.
It will make a good one for a 5 hour ACM-Style contest. I believe I am not the only one who skipped the round because of this problem.
Why do people spend their time only thinking about how to come up with asymptotically fast and correct solution? Don't you need to think about how to implement solution so that it doesn't take several hours?
The idea for this problem
Let's solve the problem for X-coordinates and for Y-coordinates independently, and then intersect time intervalsgives great advantage in implementing. Plus, this way of thinking makes you think about other edge cases, where move-coordinates are equal to zero, and it's easier to handle them.I didn't come up with it during the contest, so I couldn't get my solution accepted.
Many say that this is bad problem, because it doesn't require any idea. But I think, it's good, when there is an idea, which gives you a huge advantage during implementing. And contestant can choose for himself: either he wants to implement the first idea he has in his mind, or think to make his life easier.
Yes you are right :D I figured after that it's can be solved using fraction with 3 variables a, b (a/b) and eps boolean variable :D
This is an adequate answer, but still nothing about weak tests in E and F. Problem E has only 44 tests, being a YES/NO problem with non-trivial operations in implementation, which can lead to finding wrong solution instead of correct one, and this is the case not caught by YES/NO answer. So in this problem it's definitely necessary to write REALLY A LOT of incorrect solutions, which consider some steps of the algorithm incorrectly or simply have some implementation bug. If these things had been done as well as the tests against each such solution, there would have been way more tests in this problem.
And F is just another case with stupid optimized solution receiving OK. There was simply no test making this solution to do maximum number of operations, which is maybe musthave in any queries problem.
Both these cases are good lessons, so hope CF to avoid them in future.
Could someone please help me understand why I am getting WA on problem B on test case number 62?
What I basically do is the following:
1) all cells reachable from the S cell are marked with 1.
2) all cells reachable (and not visited already) from any cell marked with 1 is marked with 2
3) all cells reachable (and not visited already) from any cell marked with 2 is marked with 3
If the cell containing the bank is marked with a number different from 0 then the instance has a solution. It's basically a BFS.
code's here
Here is a test case your code fail:
basically, you are checking whether a grid is visited or not, but not the direction in which it is travelling. So you will need 1 more dimension for the direction. (something like v[i][j][dir] instead)
can you please check why it shows WA at test case 11 for [http://mirror.codeforces.com/contest/793/submission/29730350],please help asap...
there's a problem with your
dp[x][y][direc], it is not storing the minimum value.can you please provide some small test case,I can not figure out the mistake..
sorry I might be wrong. Maybe you can stress test it? I do not really have time.
Раунд интересный, необычный, но это же Tincoff challenge — то есть не очередной контест, а немного другие задания и формат соревнования. И странные, необычные задачи, а также слабые претесты возникают из-за другого формата, непохожего на стандартные соревнования, поэтому любое сравнение со стандартными раундами — не совсем корректно
What?
Well, problem C was not that bad to me though I am still getting WA. But observing the huge amount of WA in system tests after contests makes me think that, maybe, just maybe, there is someone in North Korea who is preparing to go to the Labor Camp, because Kim Jong Un was expecting him to become Red in this contest and he failed because of this problem :p
My Rust solution gets runtime error on the sample, even though it runs fine on my machine. Any idea as to what's going on?