Автор 300iq, история, 8 лет назад, По-русски

Всем привет!

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. Разбор

  • Проголосовать: нравится
  • +424
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Nice anouncement, hopefully the problems will be cool. Good luck to everyone and no rating drops!

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Nice announcement. Hopefully all the problems will be cool. Good luck to everyone and no rating drops!

»
8 лет назад, # |
  Проголосовать: нравится +157 Проголосовать: не нравится

My profile picture advertises Tinkoff nearly a year. I think that I deserved automatic invitation for the final :)

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -52 Проголосовать: не нравится

Wishing problem description will well translated in english.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -80 Проголосовать: не нравится

.

»
8 лет назад, # |
  Проголосовать: нравится -37 Проголосовать: не нравится

Is the round rated?

»
8 лет назад, # |
  Проголосовать: нравится +144 Проголосовать: не нравится

Are travel cost and staying cost paid for top 100 participants?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I thought the same thing, usually there are div1/div2 mirrors for things like this.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me how difficult it is

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится -44 Проголосовать: не нравится

/

»
8 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

The name "Tinkoff" sound super cool to me, though I don't know Russian. I really want to get the Tinkoff vest!!

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Hopefully the statements will be short not like Google Code Jam yesterday xD xD

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Any previous round of Tinkoff Challenge?

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Is this contest rated for div2(<1900) people?

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Это раунд вида "div.1 + div.2 combined" по уровню задач(round D = div2D = div1B)?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

Let's stay up late tonight!

»
8 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Will this contest be rated for all?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Will there be any geometry in the contest?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

Why? UPD:Fixed

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Still no scoring announcement?

»
8 лет назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

55 minutes after the end of Tinkoff Finals, GCJ Round 2 begins. I wonder if the Finalists can participate in GCJ.

»
8 лет назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

Seems like the round is delayed for 10 minutes (19:45 MSK). Then right after this round is finished, El Clasico will be started. :")

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

I wanna watch el clasico...please Start it soon :((

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

10 minutes late.

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Was the contest delayed? I thought it was at 19:35MSK but it looks like it's at 19:45MSK.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why delay in contest time?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Are the judging servers frozen or something?

»
8 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Long Queue :/

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Что не так с 24-ым тестом в задаче D?

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

что за 7 тест в задаче С?

»
8 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Well this round certainly "eliminated" me.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Anybody knows the reason of WA10 on C?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Something like point can have speed vector of zero length

»
8 лет назад, # |
Rev. 7   Проголосовать: нравится +46 Проголосовать: не нравится

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...

#ggneedaglasses

PS. More unfortunate, I set wrong initial value for my dp array and led to TLE.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This thing just ruined my contest. Didn't even think about it before I read your comment :(

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Очень радует, когда много задач на идею, и не нужно много реализовывать !)

»
8 лет назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится

B и С очень интересные.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

Someone fooled me by #define int long long :(

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How to Solve C?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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 x came to trap at time t} {mouse x came out of trap at time t}. 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're n mice, we just output this period of time.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Hack case for C?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +68 Проголосовать: не нравится

for C , double -> WA , long double -> AC
UPD:WA

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

    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).

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    WHATT?? NOOOO! :(

»
8 лет назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

Пока решения не проверились, я могу быть хоть более-менее объективен. У меня вагон и маленькая тележка причин опасаться за своё решение по задаче C. Такие задачи, на мой взгляд, очень не подходят для формата CF, ведь маленькая бага в верном решении может стоить слишком дорого. Задача слишком багоопасна.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Целочисленное решение с использованием long long зашло. Больше не буду начинать раунд с таких задач, слишком тяжело психологически писать и тестировать локально такую жесть. Я бы поменял эту задачу местами с D.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is c ternary search on max distance between point and rectangle?

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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).

»
8 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Why is the hacking page so unstable? I really wanted to hack, but the page was just showing "loading circle" infinitely.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    the hacking page was stable for me the whole contest.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    I encounter the same trouble after hacking one submission.

»
8 лет назад, # |
  Проголосовать: нравится +230 Проголосовать: не нравится

IMO problem C ruined the contest

»
8 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Task were tehnical, tehnical and tehnical.

Good bye, my rating.

»
8 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

Didn't read this for almost 50 minutes, got WA 7 times, :'(

»
8 лет назад, # |
  Проголосовать: нравится +143 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    Yes, B is hard for a B. and C is too long.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    I agree with you !

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

    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 -1 in samples (except the case when finding the test with -1 i stricky and requires good thinking skills).

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I think this problem can't be B problem :(

»
8 лет назад, # |
  Проголосовать: нравится +114 Проголосовать: не нравится

Contest duration was obviously not long enough.

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    used the same :)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Tried the same but didn't notice that edges are directed :(

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    same

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Can anyone explain how to solve D ? thanks!

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

So hard problem for B :(

I wasted about 40 min on it :(

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there an error in the following function?

Get Time Inside Of Rectangle

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.

»
8 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    Some people including me used only integer arithmetics in C. And you don't even have to do binary search.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      Seems like that wasn't the case :|

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    I think the goal of the problem was to require integers (or understand float numbers well).

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Test for problem C:
2
0 0 2 2
-1 -1 1 1
1 0 -1 1

Upvote if your solution fails it)

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I did the same.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i did the same, though i wonder if i will get ac

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
8 лет назад, # |
  Проголосовать: нравится +66 Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Statement for problem C is awful, just awful. It never explains what 'strictly' means exactly, and the sample picture leads to the wrong conclusion.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's a common term and you could have asked about it.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +45 Проголосовать: не нравится

      That means that the answer is always either 0 or -1 since otherwise the minimal required time doesn't exist since the set of all possible times is open.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +14 Проголосовать: не нравится

          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)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hmm, you also had Wrong answer on pretest 7, didn't you? =)

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

That moment when a legendary grandmaster hacks you (⁄ ⁄•⁄ω⁄•⁄ ⁄)

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +102 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Why system testing is so delayed and still pending ?

Update: System testing started now :)

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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 ?

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How this can be rated contest for div2?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can we see others' solutions please?

»
8 лет назад, # |
  Проголосовать: нравится +119 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    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!

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    So the answer is always 0 or -1?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

WHEN YOU FOUND A SOLUTION FOR PROBLEM B AND CODEFORCES SAYS TO YOU "CONTEST IS OVER"

»
8 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

Ориентированные дорожки, серьезно?) С условием было тяжело, несколько задач пришлось перечитывать и разбирать на семплах. B по-моему уже была на каком-то раунде. И тогда задача не казалась сильно интереснее. Интересно, что в G все отправили, надеюсь авторы тесты сделали к такой задаче.

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I alone think that this contest required 2.5 hours as many Combined Rounds before?

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

So many failed submissions for C kek

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    You are revisiting single index again n again

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks for the answer. Do I have to use dp 2d array to save turn needed from each position?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +56 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I'm the only one in room who solved it. Thanks to arsijo for hacking me

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you share the hack's test case?

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

        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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I thought the contest went well... I changed my mind...

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Any clue what case 24 is for Problem C ?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

All solutions for G has failed :(

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

What is intended solution for G? Where are big pretests?

»
8 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Wake me up, when markysha's submission testing ends

»
8 лет назад, # |
  Проголосовать: нравится +111 Проголосовать: не нравится

Oh nice!

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What was the most elegant solution to B supposed to be?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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).

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -70 Проголосовать: не нравится

    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.

    #include <bits/stdc++.h>
    using namespace std;
    int main()
    {
    	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    	int N, M;
    	cin >> N >> M;
    	char A[N + 2][M + 2];
    	int D[N + 2][M + 2][4];
    	pair<int, int>dir[4];
    	dir[0] = make_pair(0, 1);
    	dir[1] = make_pair(0, -1);
    	dir[2] = make_pair(1, 0);
    	dir[3] = make_pair(-1, 0);
    	int sX;
    	int sY;
    	int fX;
    	int fY;
    	for (int i = 0; i <= N + 1; i++)
    	{
    		for (int j = 0; j <= M + 1; j++)
    		{
    			A[i][j] = '*';
    			D[i][j][0] = 3;
    			D[i][j][1] = 3;
    			D[i][j][2] = 3;
    			D[i][j][3] = 3;
    		}
    	}
    	for (int i = 1; i <= N; i++)
    	{
    		for (int j = 1; j <= M; j++)
    		{
    			cin >> A[i][j];
    			if (A[i][j] == 'S')
    			{
    				sX = i;
    				sY = j;
    			}
    			if (A[i][j] == 'T')
    			{
    				fX = i;
    				fY = j;
    			}
    		}
    	}
    	D[sX][sY][0] = 0;
    	D[sX][sY][1] = 0;
    	D[sX][sY][2] = 0;
    	D[sX][sY][3] = 0;
    	queue<int>x;
    	queue<int>y;
    	queue<int>k;
    	for (int i = 0; i < 4; i++)
    	{
    		x.push(sX);
    		y.push(sY);
    		k.push(i);
    	}
    	while (!x.empty())
    	{
    		int a = x.front();
    		int b = y.front();
    		int c = k.front();
    		x.pop();
    		y.pop();
    		k.pop();
    		for (int i = 0; i < 4; i++)
    		{
    			int price = 1;
    			if (c == i)
    				price = 0;
    			int aa = a + dir[i].first;
    			int bb = b + dir[i].second;
    			if (A[aa][bb] != '*' and D[a][b][c] + price < D[aa][bb][i])
    			{
    				D[aa][bb][i] = D[a][b][c] + price;
    				x.push(aa);
    				y.push(bb);
    				k.push(i);
    			}
    		}
    	}
    	int X = min(D[fX][fY][0], min(D[fX][fY][1], min(D[fX][fY][2], D[fX][fY][3])));
    	if (X <= 2)
    		cout << "YES\n";
    	else
    		cout << "NO\n";
    	return 0;
    }
    
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    My TripleGunShot ;) 26616550

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Many Thanks to You all, got it now

»
8 лет назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I started with C and succeeded with integer solution. But it was too painful to implement and wait for system testing results.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Represent in the form: p / q.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    Actually, Change EPS to 10 - 12 will get AC with long double. Because error can be small as 10 - 10.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why my solution is wrong for B?!

https://ideone.com/EmkO4J

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
»
8 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    The crossroads are connected with m oriented bicycle lanes (the i-th lane goes from crossroad ui to crossroad vi), the difficulty of each of the lanes is known.

    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

»
8 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    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?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

Problem C

WA on Test 40: sadness [ #define eps 1e-9 ]

Accepted: madness [ #define eps 1e-15 ]

»
8 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

После этого контеста думаю у многих останутся плохие воспоминания о "Тинькоффе". А жаль, могли ведь сделать лучше.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have two big idea bugs in E and it still passes

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

    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)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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... :-(

»
8 лет назад, # |
  Проголосовать: нравится +106 Проголосовать: не нравится

На контесте, увы, не получилось сдать задачу F за квадрат. Но я-то знаю, что 10^10 должно проходить в 2 секунды =)

Собственно, вот решение за O(N2) в 1.6 секунды.

Если в кратце, то вот такой вот забавный тернарник:

 a[j] = (a[j] >= x ? i : a[j]);

вместо if'а:

 if (a[j] >= x) a[j] = i;

меняет вердикт ТЛ на AC =)

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +59 Проголосовать: не нравится

    Забыл про еще одну магическую строчку:

    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
    

    С ней 600 мс.

    Справедливости ради, на весьма примитивном тесте, где каждая нитка — это пара i, i + 1 мое решение работает больше 2-х секунд. Странно, что авторы не добавили такой тест.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      а что делает магическая строчка ?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        Позволяет компилятору забыть о кроссплатформенности и использовать специфические процессорные команды, в частности SSE.

»
8 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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 :/

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Maybe you forgot to set some variables as 0? Your compiler may do this automatically, but CF with optimizations doesn't

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

    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!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The problem was with this statement:

      std::ios::sync_with_stdio(false);cin.tie(0);

      Probably, the buffer was not being cleared !

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there anyone who have done problem B using bfs and not getting memory limit exceeding

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Many people, me included. I just use a array with size [1005][1005][4], how can it get MLE?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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).

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Можно побольше инфы про экскурсию?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +154 Проголосовать: не нравится

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:

  • Two easy problems A and B. Maybe B was a bit harder than usual, but still it was good.
  • A great problem C. I think that ability to estimate the required epsilon is good for a competitive programmer. If you feel unsure about epsilons, you may always write an integral solution, you only had to implement rational number comparison.
  • A beautiful problem D: interesting DP that requires some thinking.
  • Three hard problems E, F and G, all of them were really interesting to solve.

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +38 Проголосовать: не нравится

    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?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

          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?

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +68 Проголосовать: не нравится

            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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +83 Проголосовать: не нравится

        Well, I may be too choosy but as for me it was not interesting at all, just bunch of cases to check.

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Is it possible to solve B without using a second 2d array for the grid ?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you explain =D ?

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

My accepted solution for C uses doubles and doesn't have an epsilon; did I just get lucky? http://codeforces.me/contest/793/submission/26615231

»
8 лет назад, # |
  Проголосовать: нравится +62 Проголосовать: не нравится

А че у всех бомбит-то? Не умеете с даблами работать? Нормальный же раунд. Не идеальный конечно, но и далеко не худший, бывало и хуже

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Согласен. Например, прошлый контест (VK Cup Round 2) вообще был учебником по математике. Я считаю, что он был гораздо хуже этого. Тут хотя бы как-то связан раунд с программированием. Хотя, думаю, у многих бомбит от задачи B. По мне, так она вполне себе тупая и на уровень B тянет.

»
8 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Гайс, я раунд не писал, но че не так то? Вы хотите эпсилоны подгонять на контесте с постпроверкой?

»
8 лет назад, # |
  Проголосовать: нравится +358 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +154 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +86 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Так может это просто боты заминусовали.

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

downvotes > upvotes => it shouldn't have been this contest at all :'( sad
luckily I didn't read C statement after I saw test case :|
B and G were very interesting

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

В задаче F очень слабые тесты. Моё простое решение(которое работает в худшем случае за ) залетело за 327 мс. Сразу же нашелся контртест, который валит мое решение.

n = 1e5;
m = n - 1
1 2
2 3
3 4
...
(n - 1) n
q = 1e5;
1 1
1 2
1 3
...
1 n
»
8 лет назад, # |
  Проголосовать: нравится +144 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +49 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +56 Проголосовать: не нравится

      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 intervals gives 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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +71 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Here is a test case your code fail:

    4 3
    S..
    ..*
    ...
    .*T
    

    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)

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      can you please check why it shows WA at test case 11 for [http://codeforces.me/contest/793/submission/29730350],please help asap...

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        there's a problem with your dp[x][y][direc], it is not storing the minimum value.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          can you please provide some small test case,I can not figure out the mistake..

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            sorry I might be wrong. Maybe you can stress test it? I do not really have time.

»
8 лет назад, # |
  Проголосовать: нравится -113 Проголосовать: не нравится

Раунд интересный, необычный, но это же Tincoff challenge — то есть не очередной контест, а немного другие задания и формат соревнования. И странные, необычные задачи, а также слабые претесты возникают из-за другого формата, непохожего на стандартные соревнования, поэтому любое сравнение со стандартными раундами — не совсем корректно

»
8 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?