VK Cup 2016 — Round 2 (announcement)
By AlexFetisov, history, 9 years ago, translation, In English

In 6 hours 2nd Round of the VK Cup 2016 programming competition is going to happen! If you haven't registered for the round — don't worry! There is an extra registration!

The teams who has advanced from VK Cup 2016 Round 1 and VK Cup 2016 Wildcard Round 1 can participate in this round. The competition has regular Codeforces rules. Also in the same time with official round there is a regular rated Codeforces round played on the same problem set for participants from both div1/div2 divisions.

This round was prepared by AlexFetisov and winger. That is the first round which we have prepared as authors. We want to thank Gleb Evstropov (GlebsHP) for his help. Gleb is doing great job as Codeforces coordinator and I wanted to tell that one more time! Also we want to thank Kamil Debowski (Errichto), Mateusz Radecki (Radewoosh), Boris Minaev (qwerty787788), Pavel Kunyavskiy (PavelKunyavskiy) for their help in testing the problems and for great suggestions. Huge shout out for Mike Mirzayanov (MikeMirzayanov) for everything he has done for all of us!

To advance to Round 3 team should have a positive score and has score not less than the score of the 100th team in the final scoreboard. Also note that all teams advanced to Round 3 will get a special edition t-shirt of the competition. Also top-50 participants of the round 3 will get this t-shirt as well.

Good luck and have fun!

Update

Round has been finished. There were some problems during round but we hope that you enjoyed problems. Congratulations to the winners!

Official VK Round 2:

  1. Who`s On First Base!: -XraY-, ershov.stanislav
  2. Beer and lemon tea: sankear, Zlobober
  3. MYCOPOBO3: V--o_o--V, LHiC
  4. Never Lucky: subscriber, tourist
  5. 33% less bad jokes: ifsmirnov, Arterm

Div1 results: Congratulations to anta who is the winner of this round div1 solving the hardest problem of the contest.

  1. anta
  2. jqdai0815
  3. Petr
  4. dotorya
  5. ikatanic

Div2 results:

Congratulations to alexrcoleman who is the winner of this round div2 solving all problems less than in an hour!

  1. alexrcoleman
  2. nherceg
  3. santjuan
  4. mkisic
  5. unused

Editorial http://codeforces.net/blog/entry/44538

Announcement of VK Cup 2016 - Round 2
  • Vote: I like it
  • +104
  • Vote: I do not like it

Comments Comments (229)
| Write comment?
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Auto comment: topic has been translated by AlexFetisov (original revision, translated revision, compare)

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

Stay away tweety :p .

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

What the difference between the VK round 2 and the codeforces round. Like for example if a div 2 coder participated in the codeforces round and solved few problems can he participate in VK round 3 or do I have to participate in VK round 2 exclusively. And can't I just participate in VK round 2 AND codeforces round so if I solve a problem in one of them I solve 2 so my rating will go sky high. :-)

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

"Also note that all teams advanced to Round 3 will get a special edition t-shirt of the competition. Also top-50 participants of the round 3 will get this t-shirt as well"

Is there a mistake here?

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

    "All teams advanced to Round 3 and TOP-50 participants of online-mirror of Round 3 will get t-shirts."

    (Translation from Russian)

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

      Does it make sense? Shouldn't it be TOP-50 from today's contest? Top participants from VK round 2 are awarded with shirts, so why unofficial round 3? Am I right?

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

      Does that mean I won my first shirt ever??

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

        Nope, this was Round 2, and T-shirts will be devlivered in Round 3

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

is Div 2 for Russian speakers only ?

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

.

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

First: I have opened the announcement. Second: Ctrl+F Rated, Ok, then let's go on.

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

Wtf?

What is it???

A rated CF contest???

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

No skeleton images saying waiting .... till now .
Wierd!

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

rated round??? is that an extinct dinosaur ???

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

The number of downvoted comments is too high!

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

The first rated round in forever and I can't compete! This sucks lol. The wait for Friday begins.

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

Scoring — standard or dynamic?

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

nice problem in Div.2, 669D - Little Artem and Dance

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

    How to solve it.

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

      You can sum all the rotations and remember that value. And for swaps, only parity of the current rotation sum matters. When you do two swaps with the same parity, they cancel each other. So you simply need to count the final number t of non cancelled swaps, and the parity of the first swap in this sequences.

      Each number goes to t positions left or right, depending on the first swap parity and the parity of the number. And then you rotate the whole array by the sum of all rotations.

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

        Solved it in 5 minutes, spent the rest of the contest debugging. Fix a test another one fails, fix the other the first one fails. I wanna kill myself >_<

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

          very well , do it.

          maybe we will get more rated contests :v

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

          Was similar for me. I had the solution which passed all samples and all my tests. But got 7 WAs. And 3 minutes before the end I realized that parity of the first swap matters, and managed to submit it.

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

      just store number of moves for odd positioned boy and even positioned boy and finaly calculate the position of all I don't know its right or not but it has passed pretest :)

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

Was it possible to avoid TLE on problem D with a O(n+q) solution ?

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

How to solve Div2E?

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

    Hash table mapping an integer to a binary search tree of integers.

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

    Hi, My solution was maintain a Binary index tree with unordered_map<int,int> in each node, which is o(1) , then just do classical update, query on it.

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

    I used one Segment Tree for each unique value. Just store  ± 1 for each insertion/deletion and perform sum queries.

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

      Shouldn't having a big array for each unique value memory limit?

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

    I used STL map which maps each integer to a set of time.The solution passed pretest but it got TLE in Test case 11.

    I think that this solution take O(n*(log(n)^2)) Can you please tell me time complexity of the solution that uses segment tree or fenwik tree?

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

      Mine is O(nlog(n)) using Fenwick Tree

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

        Ok, Thank you. I tried another solution where I stored pairs of integers in c++ STL sets and this solution is O(nlog(n)) still it is giving time limit exceeded. Can anyone explain why the solution is slower than than other O(nlog(n)) solutions?

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

          Your submission is actually N^2; std::distance used on set iterators takes time linear in the distance between the two iterators.

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

      My solution with Segment Trees: 17494007

      This is O(NlogN)

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

I have a doubt : Sometimes like today's D scanf/printf seems to perform exceptionally well over cin/cout. Though I was using ~~~~~ ios::sync_with_stdio(0); ~~~~~

with no endl i.e. flushing of output yet my program ran in about 1.9 seconds changing cin/cout to scanf/printf reduced time by 3.

What is the reason behind it? I lost more than 150 points due to re-submissions

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

I realy don't understand why linear solution for D (O(n + q)) gets TLE...

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

    You need very optimized I/O... this particular problem pushed the limits of what can be done in 2 seconds in that regard.

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

      I always use C#. And never got this problem before. Something went wrong today...Of course i will investigate the problem after systests. But I think time limit should be such that the solution has passed not only on C++...

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

        I passed it with Java but needed to do several things I wasn't used to with the I/O (namely, use a BufferedReader directly instead of a Scanner, and use a BufferedWriter rather than println()ing a string made with a StringBuilder).

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

    got 4 TLE on pretest 11, even by using ios::sync_with_stdio(0) on a O(n+q) solution. But as anh1l1ator told that scanf/printf were running on time, I think it was more of language based question.

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

Am I the only one who consider that precision problems in div1C were more than annoying? I still don't consider I've made any mistake and I don't know why sometimes I get WA on pretest 8 sometimes on 9...The intended solution was with product and sum of the partial sums?

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

    Div. 1 D maybe?

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

      I don't think so. I was talking about div1C from unofficial contest. Maybe in official contest they were numbered some other way

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

    Its very weird. My solution with long double didn't pass pretests but when I changed it to double it did. B/w I also did the same thing.

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

      ... Nice avatar :)

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

      My solution uses long doubles, fails pretests under G++, passes pretests under MS VC++ (when all else fails: change compiler :) ). Let's see after systests, though...

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

        Btw, MSVC doesn't have long double type, it's the same as double on it.

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

    I also got a few WA on pretest 8. It seems it was because I was taking the square root of a negative number when it should have been 0.

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

I tried to hack a solution with O(n) on problem A div2 but it was unsuccessful (n=10^9) :(

why?!

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

    If it was just a while loop with addition/subtraction it's more than possible they could have gotten a billion operations done in 2 seconds.

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

    the same happened to me, I tried to hack a O(n^2) in B div2 and it passes!!!!!

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

    Some sort of compiler optimization?

    Like This

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

    I try it on custom invocation and this is the result

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

How to solve problem 4 Div 2. i was encountering the problem when x is odd.

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

I think ABCD should be circular-shifted.

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

In problem B div2, little artem and grasshopper,

second sample test 3 >>< 2 1 1 area starts from 1 and ends at 3.

start from cell 1, jump 2 steps right, reach cell 3. direction is again right, jump 1 step ahead reach cell 4 and get out of the area. but the note in the problem says, Second sample grasshopper path is 1 — 3 — 2 — 3 — 2 — 3 and so on. can someone explain why?

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

    Because each cell had a direction and length associated with it... this was not a sequential list of commands but rather the grasshopper sees a sign on the cell giving the directions... the problem asked whether the grasshopper would ever step out of bounds or whether it would keep hopping in an infinite cycle.

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

      In the example given, the grasshopper sees a sign on the first cell saying to go right 2. Then it sees a sign on the third cell saying go left one. The dutiful grasshopper then sees a sign on the second cell saying go right one. These last two loop forever, and hence the solution is infinite.

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

    No you should move in the direction of the '<' in cell 3 you will back 1 cell so you will be in cell 2

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

Solution to problem E: #66TUPO

I mean you really think it is a bit hard? Or I should expect some unexpected verdict?

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

    Nice! I mapped each x to a segment tree :D

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

    I didn't write the round, but it's the first thing came into my mind. Very straightforward. Even without this cheat, coordinate compression + fenwick trees don't make it less straightforward.

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

    This problem is very hard when you are shocked by unknown WA of C. (and this problem makes one angry, when you realize some crappy precision error was the one who blewed up such easy problems)

    Actually, I searched for your policy-based data structure article in contest — because n <= 1000000 and segtree solution will get MLE. (I calculated 240MB with dirty compression) sadly OSX clang can't compile gnu__pbds, so I used ideone to debug — it was painful.

    Soon it turned out that these efforts were useless because 1. n <= 100000 2. I read statements wrong.

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

      I can't compile that either, but what I do is use a set and once I'm sure it works I just change the code to use the policy based ds, which should be around 2-3 lines, go into custom test and check if my code still works, worked fine for me during contest :)

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

Too bad there wasn't a lot of hacking happening this round — strong pretests I suppose

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

    problems were relatively easier than previous round #347

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

Edit : Div2 A

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

Div1 C:

Also, probabilities should be non-negative and their sums should differ from 1 by no more than 10 - 6

I wonder, how many solutions will fail because of this case? Mine certainly will :/ EDIT: Actually, it seems like I passed.

https://www.dropbox.com/s/08m764rlxuvnd6q/hack.txt?dl=0

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

    I will get WA too. I tested it on your hack and my program output all nan. It was meant to be purely a math problem, not a programming problem -_- EDIT: I somehow passed systests...

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

    Is there anything specific in this case? My solution works fine with it.

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

      I think people who use sqrt function in their solution will see something like 1.00007 and 0.999934 when they add up the sum of their output, which will be > 1e-6 error.

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

    I can see that you did not make any hack with this case.. Thank you, I can still hope to pass systest! :)

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

    Is that a good probability? They are produced by my solution that passed pretests :P

    a[i]=15083328916245932279840823609130527921079628476947190293794832049848427950033787764642925414628390330310916731933701947465371533061711148760114759803382653601121625233155946862022851427067088008522984157822017083296402464626853429590473211951849790874316769424402880358084931661613943529882190463340932869005131383232439121936748517148328737418372810911926497042735900081847898594371012194165746830896795480609079081172302829734639014034645165655017825088703634305866700555015137682443072942387017868033906236880579419521133614288513156362590844990804612816574232074299859735223614812296545257397381507457860747751574308225499542843354186170024701235438344817574100140731253729526497350066797319223996129851165727915197654461897429418079299555662797004798095895094086282391980738121825921877282118365893597035261873904749959394553190509543153197575014620757453443744428830827654721563319109783119882310723355051640716023096845418774027557237149504187519938022673234264064.0000000000, b[i]=-15083328916245932279840823609130527921079628476947190293794832049848427950033787764642925414628390330310916731933701947465371533061711148760114759803382653601121625233155946862022851427067088008522984157822017083296402464626853429590473211951849790874316769424402880358084931661613943529882190463340932869005131383232439121936748517148328737418372810911926497042735900081847898594371012194165746830896795480609079081172302829734639014034645165655017825088703634305866700555015137682443072942387017868033906236880579419521133614288513156362590844990804612816574232074299859735223614812296545257397381507457860747751574308225499542843354186170024701235438344817574100140731253729526497350066797319223996129851165727915197654461897429418079299555662797004798095895094086282391980738121825921877282118365893597035261873904749959394553190509543153197575014620757453443744428830827654721563319109783119882310723355051640716023096845418774027557237149504187519938022673234264064.0000000000

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

    What is the correct answer to this test? My solution said that there is no such one, because of negative discriminant(it is not precision issue).

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

      According to statement,

      The answer will be considered correct if each value of max(a, b) and min(a, b) probability distribution values does not differ by more than 10 - 6 from ones given in input.

      When each die has equal probability for each number that condition is satisfied. Specifically, 12500-sided dice with each number occurring with probability 8 × 10 - 5.

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

        Yes, but that doesn't say anything about validity of the input. Values from the input should represent exact probabilities of min(a, b) and max(a, b). So I assume probabilities from your input are rounded probabilities for the dice you described.

        Problem would be way harder if you just had to find probability distributions such that min(a, b) and max(a, b) are within 10^-6 from ones given in the input.

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
        import sys
sys.stdout = open("input.txt", "w")
a = []

n = 12500
for i in xrange(n):
    a.append("%.20f" % (((i + 1) ** 2 - i ** 2) / 1.0 / n / n))
print n
print " ".join(a)
print " ".join(reversed(a))

        This generator produces right probabilities. My solution works ok on such test.

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

Announcement that n is up to 1e6 not 1e5 in D after 1h and 20 min passed, really --__--???

EDIT: Ofc, I meant the other way around xD

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

    Be happy it wasn't the other way around :)

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

    Wait, it was the other direction. We announced it was 1e5 NOT 1e6. But still this is no ok (

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

    well, not sure if changing TLs (in at least two problems) sliently is much better

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

I don't know why i read rotation being done as right rotation instead of left rotation initially in Div 2 C.

How to solve Div 2 D?

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

    The relative positions of boys at odd position will remain same and boys at even position will remain same. So count shifts of odd places and even places individually. After counting, just check from which position you have to start.

    Code

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

Why did this solution of mine get TLE on pretest #9 on problem div1C? (I can virtually see no way it will do worse than O(n))

http://codeforces.net/contest/668/submission/17498093

Or pastebin: http://pastebin.com/0hCpNWx6

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

    Could it be because of the use of cin, cout?

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

Can not wait for system testing!

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

What was the pretest 4 Of Little Artem And Dance ?

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

    I don't know what exactly was the test case, but my solution which failed on test case 4 gives wrong answer on this test.

    6 2
2
2

    The answer should be 1 2 3 4 5 6

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

I got TLE on pretest 3(problem F). I tried to optimize my code in ~20 min, finally found(after contest) my code failed on testcase n=1,k=1. T_T

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

    My solution passed after fixing this small bug. T_T (what a sad story.

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

      I guess it was too difficult to find during the contest...

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

Can anyone explain why this solution gets WA3 and this solution passes pretests?

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

Can someone explain why my solution with scanf/printf gets WA on pretest 6 and the exact same solution with cin/cout passes the pretests?

http://paste.ubuntu.com/16038368/

http://paste.ubuntu.com/16038378/

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

    I'm assuming it is because z is uninitialized.

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

      oh, you're probably right. I can't believe I missed that!

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

Can anyone tell why did I get MLE verdict on my solution of Div2B 17492812 ?

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

    No one can view your code now, so you have to wait after system test or you can write it on Ideone and give us the link

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

what was the pretest 6 of div2 C

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

Could anyone solve F with matrix-tree theorem? It seems possible but when unfortunately diagonal cell becomes 0 modulo 10^9+7 I cannot continue anymore...

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

    I think the solution is based on tree decomposition. The tree width of this graph is very small.

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

      What makes you think the treewidth is small? I can't really construct a good example (always hard with treewidth) but it seems to me that you could make some very unfriendly graphs.

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

        Because it's k.

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

          The treewidth is k? How would you construct the decomposition? I'm guessing every time you add some vertex you want to put it in a bag with its k neighbours, but how would you build the tree?

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

            Think of it as following:

            • for k = 1 you will always have a tree
            • for k = 2 you will always have a planar graph whose dual is tree (the graph where triangles are vertices and edge means that two triangles share a side)
            • for k = 3 you will always have a 3-d structure constructed of several tetrahedrons sharing their faces. Its dual (the graph on tetrahedrons where edges denote that tetrahedrons share a face) is also a tree
            • similarly, for k = 4, 5 you will get a tree on k-dimensional simplexes where two simplexes are connected if they share a (k - 1)-dimensional face
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
              ← Rev. 4   Vote: I like it +3 Vote: I do not like it

              Ah, I get it now, thanks :) Then the DP-state for a bag {v1, v2, ..., vk + 1} in the tree would probably be something along the lines of: for each partition of the bag into non-empty subsets: in how many ways can we create a spanning forest covering all vertices in the subtree rooted at the bag, according to the partition we are considering (that is, two vertices are in the same set in the partition iff they are covered by the same spanning tree). Does that make sense?

              EDIT: Nevermind, you overestimate the answer a lot this way, for some edge {u, v}, u and v may be in a lot of different bags together, and this way you're counting adding this edge (between two spanning trees) in a lot of different bags. You probably have to somehow single out the one vertex that is added each step.. I'll think about this some more :)

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

                Maybe solution can be obtained on the following way. DP over the tree decomposition. State is a bag + some tree that spans vertices from the bag. And in transitions one should preserve edges which are already added in the parent bag. Number of states would be N(k + 1)k - 1 ≈ 1.2·107 and one should be careful with transitions (perhaps some precomputing will help). Does it make sense?

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

Gah... cin and cout in Div 2 D

Well I guess lesson learned: Be wary if they put such an easy problem as a Div 2 D. It literally took me 3 minutes to think of. This means that there's a trap.

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

It's jqdai0815 to start system testing!

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

Please start system testing, I wanna go to bed :-(

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

Waiting for sys testing is worse than waiting for game of thrones season 6 :(

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

From now on, I will try not to trust problem setters' problem difficulty estimations.

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

Wrote a wrong and unnecessary special case. FeelsBadMan

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it +25 Vote: I do not like it

really..

when you find out that you mistyped m to n in problem A after the contest had finished.... Nezzar

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

Problem B write too difficult to know :( :( At least for me... And I waste so many time to understand... Down to 1k5 again :(( :((

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

Could anyone find the contest on contests page? Has it gone???

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

waiting for t-shirt...

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

any hacks on Div2 B?

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

Someone please tell me... is System Test starting or should I go to sleep? :(

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

1:38 AM in Bangladesh. Still waiting! Hope

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

In Div2D=Div1B it is algoritmically easy to find O(n) solution, but what the hell the bounds of input are of order 10^6?? Very intelligent method to make the problem more difficult:( Is it really interesting to play a game "Who didn't forget about scanf/printf?"?

(I have 1964ms on pretests using cin-cout with standard accelerators and I noticed that it is so close to TL only after the end of the contest.)

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

4:46 AM here, wating for system test.

By the way, my mid-term exam starts at 1:00 PM..... (cries)

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

System testing of div 2 finally started!

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

I had some difficulty in understanding DIV 2 E / DIV1 D's problem statement.

1 1 1

2 3 1

3 2 1

Should the answer of this case be 1 or 0?

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

    The answer is 1.

    You add the number at time 1 and remove it at time 3. So the number is in the multiset at time 2.

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

I got TLE in fourth task. I think it isn't possible. My complexity is O(n+q) + I done it in Pascal and I don't have bad loops.

My code

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

    same happened to me. I think we needed to use fast I/O

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

      This is really bad. My appeal to codeforces to check it again.

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

        they should have mentioned to use faster I/O but there were 4*10^6 IO operations

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

    I got TLE too, fast I/O was needed I believe. I always trusted in codeforces servers but it looks like reading and writing 10^6 numbers isn't fast in off using cin/cout even here.

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

why did O(n+q) get TLE in div 2 D? And we weren't even given any warning to use faster I/O :(

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

System testing pausing at 95% is like watching a football penalty shootout and boom, there comes the blackout. T^T

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

Frankly saying, it would be good to have it unrated XD (inb4 I'm 29th, so that's not that bad). That one zero too much in D's (or E's) was really something with very bad influence on contest (n<=1e6 and TL=1s doesn't look like even n log n should pass and it was announced after 2/3 of contest has passed) and tests to C were really weak. I got AC in C, however in test posted by FatalEagle here my solution produces completely shitty output and I expect a big part of solutions having similar precision issues which are really hard to omit in that problem (which is pretty sad, that makes this problem a bad fit for a contest).

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

    Also using cin and cout with ios_base::sync_with_stdio(0);cin.tie(0); passes pretests in div1B but fails system tests...

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

      I got lucky, because I got TLE on pretests xD. But if it is the case for some people then it really sucks.

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

    On FatalEagle's test case, I got WA too. In addition, it took about 5 seconds to run, and n=12500,so I have no idea how I didn't get TLE for n=1e5.

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

    I am getting a deja vu. Tweety is that you?

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

    And I used to think that people in Poland find giving TL=1s, n<=1e6 for NlogN solutions completely OK, after looking at some of your problemsets :)

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

Let us be able to practice please.

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

How to solve E(about 2-SAT)?

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

    Build directed graphs like what we usually do in a 2-SAT problem.

    Claim: If u is reachable from not u, u must be true. After you deal with these variables, you can assign other variables in any order you like.

    First you should check whether they are satisfiable. If both of them are satisfiable, check whether there exists a vertex pair (u,v) s.t. v is reachable from u in one graph but not the other. Then set u=True and v=False, and find a solution in the graph where v is not reachable from u.

    I haven't got AC though :p

    Edit: AC :)

    Note: I use bitset to build the transitive closure too.

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

    Suppose that both expressions are satisfiable. Let's try to find a solution for the second expression that doesn't satisfy the first one (then we can swap the expressions and repeat this again).

    If the set of variables doesn't satisfy the first expression, there should be a clause which is equal to false after substitution. Let's iterate over all clauses from the first expression and try to find a solution of the second expression which makes this clause's value equal to false. If the clause of the form (a or b) is false, we know the values of these variables (in this case they should be both false). So we need to check whether there exists a solution for the second expression in which the values of these two variables are fixed. Let S(a) be the set of nodes that can be reached from vertex a in implication graph (the graph where each variable has 2 vertices and where we add edges !a -> b and !b -> a for each clause (a or b)). What we need to check is whether contains both x and !x for some x.

    We can use bitsets to find transitive closure of the graph and also we can use them to check if contains a pair of x and !x. If it doesn't, then we know there exists a solution where the values of the given two variables is fixed and we just need to find any such solution. First, we need to fix values of the variables reachable from a and b. Then we can repeat the following: pick any variable which is not fixed yet, try to fix any value for it and then fix all values of the variables reachable from it. If there's a contradiction, flip the value of the current variable and repeat the process again. Note that we don't need to do dfs for this as we already have transitive closure computed.

    Overall complexity is O(N3 + M·N) which is fast enough if you're using bitsets (my solution got AC with time 378ms).

    → Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it +111 Vote: I do not like it

This is my first win on a rated (don't make it unrated please) Codeforces round ever!

In problem F, my solution will fail on a test case that their answer is 0 (a multiple of 10^9+7) (I could add one line to fix this bug). Can anyone construct a hack input?

PS: I was wrong. The condition of the bug of my solution is not just "answer is 0" but that must satisfy a specific condition in addition to that.

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

Why can't I submit solution to problem E now?

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

    Because they didn't enable the practice mode yet

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

Please don't make this round unrated. As is codeforces has very few rated events nowadays. Yes there was a minor issue with testing in problem C, but when people take time out of their schedule for a rated contest, it's really disappointing to see it made unrated just because the problem setters didn't make good tests for one problem.

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

Tutorial please !?

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

Was reading comments... All these people saying things like "oh lord so many numbers, i'm too slow for it", "it's not right", "it's not fair!!!!!", "oh look at me I'm little girl and bad authors gave me too much numbers", "CF servers isn't good enough to provide fast I\O so my perfect solution pass all systests". Guys, are you OK? It's your problem that you didn't know that 4·106 I\O operations work not really fast. It's only your problem, not author's fault, not CF's slowness, it's your amateurism, that's all. If you want to improve your skills, stop crying like a little girls, blaming everybody for you fails and start learning from your mistakes.

When I started to code on Java, I looked through code of people with high rating, found out some hints and of course took fast I\O from Petr's code. And I'd never had problems with I\O. Same with C++: when i started to use this language, Burunduk1 showed me his fast I\O template, I really liked it, and since then I use it almost always. It's nice and several times faster then usual I\O, so I never think about I\O time.

What about contest... I hate myself so much! I ruined it for my team by planting amazing bug in my C solution. if (x % 2 == 1) changeParity(); See what's happening here? That's right, bullshit (-1 % 2 == -1). And I was searching for this bug more than a hour of contest. My teammate also wasted a lot of time helping me. Finally I wrote stress-testing and first test with query 1 -1 failed my solution.

In conclusion I would like to say that contest was good, problems were interesting, just don't understand why E is E, but it doesn't really matter, such things happen sometimes and don't spoil anything. Thanks to authors! Now looking forward to marathon, hope I'll have chances there.

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

    Thanks! That comment made my day :)

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

    I used x & 1 instead of x % 2 so hadn't any troubles :D

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

      Oh, i told this short stupid boring story to my teammate after contest:

      In my Java-days I was always using bitwise operations, because it worked faster. But in C++ x /= 2, x *= 4 and all other similar operations work the same time, because of compiler optimizations. So when I started using C++, I stopped using bitwise operations and began to use usual operations, because it looks clearer and more logical, as for me. And today, when I was writing this if, at first I wanted to write x & 1, but then said to myself: "Come on, boy, why do you need to do this? Use division, it looks nicer, but works just as well". So I agreed with myself and wrote x % 2 with stupid smile on my face (I'm sure it was stupid).

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

    Come on, why should "little girl" know when this freaking CF compiler work slow(Normal gcc's IO is not as slow, with speed approx. the same as scanf), which functions it doesn't support just because it doesn't (I'm about to_string, for example), etc

    After all, that's an algorithmic competition, where ability to construct algo's is intended to be checked not the knowledge of pitfails of specific wierd compiler

    PS: checked all your public c++ submissions, and didn't see anything like fast template.

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

      Normal gcc's IO is not as slow

      And what if next contest will contain a problem with 107 I\O operations? You'll also be talking about freaking CF compiler getting TLE with cin\cout? What does "Normal" mean? On your computer? I think you know that CF servers are not your computer, maybe have different compiler options and for sure different perfomance. So if you see some weak parts of your code which can cause some negative verdict, you should perform actions to prevent it. I think none of people who was thinking about I\O time on contest and knew how to read and write numbers fast didn't have problems with it.

      In my opinion, it would be more correct to say "Competitive Programming". Programming. So to participate well you need to know your language well: speed of I\O, precision of sqrt and all other features, which can be abused by problem's authors. And I also think that's sometimes authors must give problems which requires accuracy or maybe even additional efforts while using some usual built-in methods, so people know how does their language work and not just write some keywords having no idea why does it work.

      I don't know what did you check, my last public submissions contain it. For example: 17076273

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

        Normal means this one and it means on pretty much every Linux or MacOS computer(and probably any other PC that support gcc itself)

        There's a difference between the language and compilers, you know.

        Your submission was not shown in submission tabs because it's unofficial one anyway, you said you've used in

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

How can Div2 D be solved?

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

    I solved it this way:

    Notice that, no matter what operation you do, the odd and even numbers will always be in increasing order ({1,3,5,7,...}, {2,4,6,8,...}) (in a circular fashion), and the whole array will never have two consecutive even or odd numbers.

    So you can keep track of where the 1 and 2 are after all the queries. Then you can deduce the position of the other elements.

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

    Let’s notice the following:

    • offset is the same for all elements of the same parity
    • when a swap operation happens, we have to swap the offsets for odd and even guys, adding or subtracting 1 to denote the swap
    • when a shift operation happens, we simply have to add the same number for both odd and even offsets and swap them if the shift value is odd.

    Then all we have to do is print the offset values for each guy, remembering to do it in a fast way, as n can be big enough for iostream to be too slow.

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

Why are we still not allowed to practice?

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

Auto comment: topic has been updated by AlexFetisov (previous revision, new revision, compare).

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

I am not able to see others code. Is it just me or is it not unlocked yet?

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

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

    newbie question: after contest, looks now I can only view myself's source code? when I try to click other people's submissions, I can not view the source code?

    is there any way to view other people's source code? thanks.

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

      I think soon it will be possible.

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

WTF?! Is E is actually E?! I didn't read it during contest because I thought that it was something like Div.1 E. After contest I read it and just wrote solution in 5 minutes using std::map<int, std::map<int, int> >.

I will always read all problems during contest... :-(

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

Someone please share your code of Div2 C so that others can find answers to their test case.

Thanks.

My Code

Now we can see others code!

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

@AlexFetisov: It should be noted that mkisic also solved everything within an hour :)

KILE ANIMAL!

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

Problems were really good. but getting TLE (in problem B Div1) because of not using "scanf" was really unfair! I used cin/cout without syncing with stdio and got TLE...

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

    I think something is strange going on in CF compiler or server. On my PC scanf/printf works as fast as cin/cout.

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

In Div-1 C, when we are solving the quadratic equation to calculate the probabilities of the two dices, can we select either one of the two roots as the required probability, or does it matter which root we select?

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

    It can be easily proven (Well I didn't think about it, I just realized) that this equation either has one answer or one of its answers are not valid (and it is 0 I guess). But in the first equation there are two answers which are the two numbers we want. (Because of symmetry).

    Many people failed this problem (including me) because sometimes we encounter sqrt(0 — eps) which is produced by double errors and the return value will be nan instead of 0.

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

      How can we prove that only one of the answers is valid?

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

        I didn't prove and maybe I'm wrong, as I said before I just guessed :-D, also I think if there exists another valid answer, we can continue from that and find anohter answer for the problem which is a valid one.

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

in problem B div2, when I run this code in my computer gives correct answer "INFINITE", but, when codeforces run this code gives "FINITE" and I receive WA.

this problem happens in the Test Case 2. someone can explain to me?

3
>><
2 1 1

17484721

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

There is something that i thought was weird during the last round after solving the A&B problems it locked to try hacking other solutions and when trying to open the submission i couldn't so i tried to open and see the hacks and i could see no hacks was there something special about this round that i missed or was there something i did wrong on my behalf?

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello , In the Problem Little Artem and Grasshopper.

I made 2 cases,

First case — When string's current index is having '>' as direction , then if this index + the distance he has to jump exceeds n-1. Then he will go out of the array.

Second case — When string's current index is '<' as direction , then if this index — the distance he has to jump is less than 0. Then also he will go out of the array.

But this logic is giving me WRONG_ANSWER on test case 29. Can anybody help me ?

→ Reply