Tinkoff Challenge — Elimination Round
By 300iq, history, 8 years ago, translation, In English

Hi!

On April 23, 19:35 MSK will be held rated Tinkoff Challenge – Elimination Round.

Problems were prepared by me — Ildar Gainullin, Alexander wrg0ababd Kurilkin and Nikolay KAN Kalinin.

Big thanks to Vladislav winger Isenbaev and Alexander AlexFetisov Fetisov for testing round, and also to Mike MikeMirzayanov Mirzayanov for systems Codeforces and Polygon.

Participants will be offered seven problems and two hours to solve them. Scoring will be announced a bit later.

This round is eliminational for Tinkoff Challenge.

Best 30 participants will be awarded with warm vests and other pleasant souvenirs like stickers and notepads. Best 100 participants will be invited to Moscow to visit Tinkoff's office with panoramic view on the city.

Best 20 participant who will be able to arrive will advance to Tinkoff Challange – Final Round.

We hope everyone will find interesting problem for themselves. We wish everyone a successful round and high ratings!

UPD. Scoring: 500 1000 1500 2000 2500 3000 3500

UPD. Editorial

  • Vote: I like it
  • +424
  • Vote: I do not like it

Comments Comments (280)
| Write comment?
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +157 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +109 Vote: I do not like it

    Unfortunately almost nobody noticed your profile picture is about tinkoff before you say that :D

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -52 Vote: I do not like it

Wishing problem description will well translated in english.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -80 Vote: I do not like it

.

→ Reply
»
8 years ago, # |
  Vote: I like it -37 Vote: I do not like it

Is the round rated?

→ Reply
»
8 years ago, # |
  Vote: I like it +144 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone tell me how difficult it is

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it -44 Vote: I do not like it

/

→ Reply
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Any previous round of Tinkoff Challenge?

→ Reply
»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

Let's stay up late tonight!

→ Reply
»
8 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Will this contest be rated for all?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Will there be any geometry in the contest?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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:

    1. Yes, there will be a geometry problem.
      How would you react to that?

    2. No, there won't be any of that kind.
      How would you react to that?

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i bet no

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    You've jinxed it...

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    :C

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

Why? UPD:Fixed

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Still no scoring announcement?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    UPD. Scoring: 500 1000 1500 2000 2500 3000 3500

    → Reply
»
8 years ago, # |
  Vote: I like it +52 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +50 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

10 minutes late.

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why delay in contest time?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +26 Vote: I do not like it

    Why not*

    It's codeforces' usual

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    FA Cup Semi-final: Arsenal vs Man City match perhaps :p

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Better delay the round rather than have long waiting queues during the round =)

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are the judging servers frozen or something?

→ Reply
»
8 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Long Queue :/

→ Reply
»
8 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Well this round certainly "eliminated" me.

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Anybody knows the reason of WA10 on C?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Something like point can have speed vector of zero length

    → Reply
»
8 years ago, # |
← Rev. 7   Vote: I like it +46 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Someone fooled me by #define int long long :(

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to Solve C?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +29 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Hack case for C?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes. I didn't take care of this part. Thankyou!

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      :( didnt check strictly inside

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +55 Vote: I do not like it

      Very cool picture in the statement:

      I thought when mouse at borders it means mouse in mousetrap

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +68 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +20 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    WHATT?? NOOOO! :(

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, the approach is correct, probably there is an error in the implementation.

    → Reply
»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the hacking page was stable for me the whole contest.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thx, I'll try in the next contest.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I encounter the same trouble after hacking one submission.

    → Reply
»
8 years ago, # |
  Vote: I like it +230 Vote: I do not like it

IMO problem C ruined the contest

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    B also.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      What's with B? Is 4 state visited array enough to ac ?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it +9 Vote: I do not like it

        Only implementation, as you can see even reds skipped this implementation because it is annoying.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it -21 Vote: I do not like it

          http://ideone.com/9QCTSi As you can see, it's quite easy to implement, you even don't need bfs

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            ← Rev. 2   Vote: I like it +11 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              I did it in a clean way without any case handling: Click

              EDIT: Nvm , it failed systest :(

              → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What was the Hack case for C ?

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why?

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Task were tehnical, tehnical and tehnical.

Good bye, my rating.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Welcome to div2 :)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +143 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I agree with you !

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      My solution for D failed pretests because I forgot about -1

      → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +114 Vote: I do not like it

Contest duration was obviously not long enough.

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    used the same :)

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same

    → Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can anyone explain how to solve D ? thanks!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

So hard problem for B :(

I wasted about 40 min on it :(

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it -17 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Seems like that wasn't the case :|

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

Upvote if your solution fails it)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    the answer is?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      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.

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    coordinates must be non-negative

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My program gives 1.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      After one second both points will be exactly on the borders of rectangle, so -1

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -20 Vote: I do not like it

      Upvote my comment.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    Can I downvote please if my solution passes it?

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    should the answer be -1?

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Mine passes but I still couldn't get past pretest 4 :(

    → Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I too did try to do the same but shame on my poor implementation :(

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
8 years ago, # |
  Vote: I like it +66 Vote: I do not like it

→ Reply
»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +45 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +14 Vote: I do not like it

          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)

          → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +102 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Why system testing is so delayed and still pending ?

Update: System testing started now :)

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    think about the case which a mouse in the rectangle at the beginning?

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The mouse should be "strictly inside" the rectangle and not on the border.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How this can be rated contest for div2?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we see others' solutions please?

→ Reply
»
8 years ago, # |
  Vote: I like it +119 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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!

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    So the answer is always 0 or -1?

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I sorted the array too but mine passed

    Here is my submission

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      yeah I guess problem is with java. You have used c++. May be something to do with java implementation of quick sort.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Java's sort isn't guaranteed O(n*logn), it can be O(n^2) sometimes. You should shuffle the array randomly before sorting.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So many failed submissions for C kek

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You are revisiting single index again n again

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Actually, you need to store the direction you're going in, and how many changes you can still make. See http://codeforces.net/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.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          I really like the implementation, it is amazing, short and clear. thank you.

          → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +56 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you share the hack's test case?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it +5 Vote: I do not like it

        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

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just as the first contest I took in Codeforces, I got 2 FST and in the end rank 1000+. :(

    → Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Any clue what case 24 is for Problem C ?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Everyone seems to fail on 24

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 0 0 100000 100000 0 0 1 0 Output 0.0000000 Answer -1

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

All solutions for G has failed :(

→ Reply
»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Wake me up, when markysha's submission testing ends

→ Reply
»
8 years ago, # |
  Vote: I like it +111 Vote: I do not like it

Oh nice!

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -70 Vote: I do not like it

    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;
}
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yay, i got -50 :) Thanks, for sure you can downwote, pls

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    My TripleGunShot ;) 26616550

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Many Thanks to You all, got it now

    → Reply
»
8 years ago, # |
  Vote: I like it +48 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Represent in the form: p / q.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why my solution is wrong for B?

https://ideone.com/EmkO4J

UPD: AC (new code: http://codeforces.net/contest/793/submission/26626324)

→ Reply
»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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?

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Problem C

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

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
8 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    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!

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The problem was with this statement:

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

      Probably, the buffer was not being cleared !

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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!

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +154 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it -9 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            ← Rev. 2   Vote: I like it +68 Vote: I do not like it

            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.

            → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +83 Vote: I do not like it

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

        → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. 26641777

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain =D ?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +358 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +154 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      I agree with most of your points, but div2 butthurt? reread the comments above. I see red, yellow and purple complaining about C.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Maybe, I could miss this. I just know that many people are mad, and nobody of them is my yellow-red friend.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +67 Vote: I do not like it

          So you teammate is not your friend, huh?

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Or maybe he don't see you as red :P

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              it's not actually about me

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                sorry, I misunderstood.

                EDIT: maybe he don't see his teammate as yellow-red.

                → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it -17 Vote: I do not like it

            I noticed no butthurt from him, just disappointing and misunderstanding

            → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +86 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +144 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +56 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +71 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
»
8 years ago, # |
  Vote: I like it -23 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply