ZeptoLab Code Rush 2015
By viktork, 10 years ago, translation, In English

Hello, Codeforces!

The problems were suggested by users roosephu and Sunayuki. The great help in preparing was provided by Aksenov239, GlebsHP and Codeforces team. ZeptoLab Team did its best while working on statements.

The round will use smoother dynamic problem scores with 250 points steps.

In 2014 we hosted our first programming contest together with Codeforces, and we liked it!

Let me shortly remind you how it was. The contest consisted of 6 problems, 2.5 hours were given to solve (you can have a look at the problems of the previous year and try to solve them here).

Of course, even on a purely coding event we stayed true to ourselves, so all problems were designed based on our games, and, of course, we illustrated them with care:

Zepto Code Rush 2014 broke the existing Codeforces record of round popularity. Also we were glad to read a positive feedback about problems. By the way, the first three places were taken by developers from Russia. Some of them even came to pick up the prizes at the office, where they had a mini-tour and the highlight of the program: of course, the game in a giant Cut The Rope and our standard corporate "going green" welcome kit at the entrance (we call "going green" a welcome kit, full of fun gizmos of our corporate green color).

Somebody got even luckier: they stayed for more than just a tour and they still amaze us with their professional achievements. Here're some thoughts from one of them, Grisha WhiteCrow Nazarov:

I first came for the candies (just kidding), but if I share experiences now — what's especially important is that I can be myself here to the end. Zeptolabians are tolerant of my oddities and appreciate me as a person. In addition, Zeptolab leaders set goals, taking into account the abilities of each developer, including me. And when the head is also "into" algorithms, I can realease my potential. In the end I became a sort of client-side back-end developer, which, in fact, I wanted in the first place. Yes, I know some of the data structures that are unlikely to come in handy in Zeptolab soon (they would be more useful, for example, in developing a search engine); I almost never use this part of my knowledge in my daily routine. But these skills are useful to me on the internal algorithmic contests :) What I can say about Working moments: my last task was to improve packaging of atlases in preparing of game resources – a well-known NP-hard problem. I managed to make significant progress: to improve the famous algorithms, the best in 2013 in a variety of metrics. As a result, the memory consumption in all our game projects decreased by megabytes. With the appetite of our artists, I think it's not for long :) Maybe we'll publish my work in one of the next conferences. Overall, sports programming skills are highly valued here, and this, in my experience, is what isn't appreciated enough in other companies.

And this post is made to inform you, dear algorithm lovers, that: Zepto Code Rush 2015 starts on Saturday, April, 4, 16:30 (UTC).

We are working on problems for the contest and ready, but we are ready to announce cool prizes!

You cannot get a vest like that in other ways besides taking part in the contest. The vests are great!

And as usual, the person who shows good results in the competition, will be able to get a job in our company by a simplified scheme. You can read about ZeptoLab on our official website.


Want to apply to ZeptoLab?

ZeptoLab Code Rush 2015 will use standard Codeforces rules, it will be a rated round for the both divisions.

Announcement of ZeptoLab Code Rush 2015
  • Vote: I like it
  • +886
  • Vote: I do not like it

Comments Comments (171)
| Write comment?
»
10 years ago, # |
  Vote: I like it -14 Vote: I do not like it

This contest will be rated ?? or get any editorial ??

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

Div.1 vs Div.2

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

The vests are great! :))

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

Nice Jacket. I liked It :)

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

    Rare! This is one of a few clothes you can win from a programming contest, and you can actually wear it in some not-programmatical place.

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

No T-shirts =(

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

    I agree, it's not that funny when there aren't T-shirts :( .Anyway, I hope the problems will be as interesting as last year or even better :)

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

    There are 15 vests and 50 plush toys to win and you are complaining that there are no T-shirts (100th opportunity to get programming T-shirts?) -_-... Codeforces community can be so cruel sometimes ; d

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

I would kill to get that cute toy and vest!

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

I love ZeptoLab. The code rush will be good!

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

i really wonder if viktork is fake account or a specialist host the zeptolab code rush!

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

    Well green matches well with the vests..

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

tourist would you leave the IPHONE 6 this time ?

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

Still waiting for last year's Tshirt..

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

    I think You are Going to Get Two T-Shirt Simultaneously :) Best Of luck For All

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

your company's games are full of fun,and they are popular in my country!

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

How can we register guys?

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

    The registration system is same as you register in codeforces round.....

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

I think After this contest Color me pink (magenta) will be

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

    OMG

    What a nice grammar..(plz don't edit your comment... ;D )

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

      No this is not my grammar,this is google translate grammar

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

        Try to learn english in appropriate way! google translate isn't such good tool :|

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

If you want to highlight both the upvote(green) and downvote(red) arrows simultaneously you should first click on the upvote arrow and then "very quickly" after clicking on the upvote arrow , click on the downvote arrow .

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

    Other way around (firstly downvote and then upvote) works as well ;)

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

    As long as you don't reload the page.( I'm disappointed ).

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

Hopefully there would not be many unknown giant-non-rated(div1 coder competing in div2) coders here!!!

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

    Huh this is combined division contest. This only happens in div2 only contests. So no need to worry.

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

I thought that more than 6000 participant will join to the contest

But now it's only 3500...

Maybe it will be(I hope)

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

iPhone 6 is gone. tourist is participating. :)

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

come on sorry_dreamoon !

iPhone 6 is waiting for you !

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

Still waiting starting the raund :))

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

Good luck and have fun!

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

tourist vs Petr ... I'm waiting :)

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

I moved the round 5 minutes forward just to be sure that everybody are ready and registered. May the Force Om Nom be with you!

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

Welcome kit of Zepto Lab is "going green", but for codeforces, it is "going RED"!!

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

Wow, the prizes are awesome, and I'm sure the problems will be just as good. It's a shame that with >5000 participants a few people (including me) don't stand a chance at getting one of those cool vests. How about giving away a few vests or buttons to random participants besides the top 50, or better yet, a vest for someone random in the top 500, in the top 1000 (places 0-1000), and so on? That way the more skill you have the better the chances for getting a prize, but everyone still has a chance. But then again, prize or no prize, I'm sure we'll have a great time solving the problems :).

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

It's starting in 5 seconds...

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

Nice Contest thanks all :)

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

It Ended in before 10 minute

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

Can anyone give a hint about E?

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

    It is similar to WF2014 Problem K. I used the same method I used to solve that problem, but it may TLE on system test.

    Use greedy + dfs + binary search to solve it.

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

      What is your complexity?

      The O(N * log * Q) is quite obvious with the same method from WF2014 — K, but I think it'll TLE, so I didn't attempt..

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

        I think it will TLE too. I did some pruning so I can past the pretest. Let's hope it will not TLE on system test. :D

        UPD: It passed system test! [smiling face]

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

          Nice — mine linear per query TLEed :(

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

            My also TLEd (rather understandably).

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

      thanks :D

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

    To solve this problem, first, you need to compute, for each level, how many levels starting from this one would fit in one group. Then, use dynamic programming to compute for each level, starting from the last one, two numbers:

    • How many groups are necessary to store all the levels from this level to the last level, inclusive.
    • How many more levels, starting from the beginning, would fit in the remaining space in the last group.

    Now, the answer is the smallest number of groups among levels where the groups include all levels, i.e. minimum of the first number among those i for which the second number is at least i.

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

      Thanks guys

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

      I tried that but I get TLE :(, I did many optimization but still no success :(

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

        What's the time complexity of your solution? My solution has time complexity O(nq).

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

      Another solution with the same complexity:

      If the answer for a query is equal to R, then if you start with the first element and do greedy, your answer will be at most R+1. So lets try to start with the first element and get some answer R', and after that check if R'-1 is also possible.

      To check that, you can build an oriented tree with edges (P[i], i), where P[i] is largest position such that group [i, P[i]-1] fits. Now you have to find a path in this tree of some fixed length such that the difference between indices of the first and the last vertices of the path is at least N. Since the number of paths in O(N), you can easily check that using dfs.

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

        why is it always at most R+1?

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

          Because you can divide the group and the answer will increase by one.

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

    Mine O(N·Q) approach calculates for every starting position how many groups are needed and what is the sum of leftover elements at the end, which can be eventually grouped with the elements in the beginning.

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

inb4 90% of submissions on C fail and the problem gets 2500 points, sending people who solved it waaay up the scoreboard :D

(just so it's clear: I know that mine should fail — I have at least a typo)

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

    Does problem C have a tricky corner case?

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

    Is C a DP? I tried but couldn't think hoe to minimize size of array.

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

    How do you solve C? I failed pretty hard on that one :/ Was thinking of some binary search type algo to get logarithmic complexity but didn't work out... Any hints?

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

Good Bye Div. 1 till 2 months later :-h

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

Is D a DP? How can I solve it?

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

    I've solved using Z-Function.

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

      It's funny, because the great post about it by paladin8 — http://codeforces.me/blog/entry/3107 is currently on top 5 of recent actions :)

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

        It's extremely simple with KMP too: 10582275

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

          Can you explain your solution, please?

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

            Let's ignore K for a moment and focus on choosing A, B. We have that the whole string S must be periodic with period len(A + B). Therefore len(A + B) is a multiple of the smallest possible period P for the whole string.

            Suppose len(S) = mP + q, with 0 <= q < P. The last q characters have to be in A (as len(A+B) is a multiple of P). Therefore, the necessary condition to write S as A + B + A + B + ... + A is that len(A) = xP + q, len(B) = yP — q, and x+y divides m.

            Knowing all of this, which A, B to choose to get k repetitions? Suppose you choose A to have length L. After you remove the last A, you have to leave something which is (A+B) repeated K times. Therefore, you have that:

            • The prefix of length len(S) — L must be periodic with period T = (len(S) — L) / k.
            • The period T has to bigger than or equal to L (as it is equal to len(A + B)).

            From the first condition, we want L = len(S) mod k, and from the second condition, we want L as small as possible. So try L = len(S) mod K and check if it's valid, otherwise print 0.

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

          KMP indeed! How did you use the pos array?

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

          Can you explain the idea behind your code, please?

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

      what was the main idea?

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

        Check all possible lengths L of block A + B. For each L use Z-function to find number t of equal blocks A + B (by checking z[L], z[2L], z[4L], z[8L]...). if t ≥ k, then fill min(z[L * k], L) indices with 1 (at position L * k). Complexity O(nlog(n))

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

          Actually you can do it in O(N). In fact you only need to check if z[L]>=L*(K-1)

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

    Thanks!

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

Some hints for problem C ,please!!

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

    This is my solution

    Divide case into 2

    • Suppose that Hr/Wr > Hb/Wb

    1. Wr > 1000000 : check all posible case

    2. Wr <= 1000000 : In this case, number of blue candy is smaller than Wr so check all

    I'm not sure this is right

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

      Now I'm sure this is right

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

        Why the number of blue candy is smaller than Wr?

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it 
          We supposed that Hr/Wr > Hb/Wb, Hr*Wb > Hb*Wr

          So if number of blue candy is bigger than Wr, it can't be a best case.

          (blue candy)*(Wr) can be replaced by (red candy)*(Wb), which has more enjoy unit.

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

Can i filter standings table by color?

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

Is the problem F only this? http://stackoverflow.com/questions/1824388/finding-sorted-sub-sequences-in-a-permutation I just didn't want to copy-paste the code, which is probably not even allowed...

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

ignore

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

Is D some kind of KMP? I was trying to figure out something from the mismatch array but failed.

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

    D can be done using Z

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

      How do you track the intermediate Bs? or may be thats not even required?

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

    I've used Z-algorithm...

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

    http://codeforces.me/blog/entry/3107 Epic!

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

    A friend of mine used Z-algorithm. I'm not too familiar with that, so I used rolling hashes for string matching. As long as you have constant-time string matching, it can be solved in O(n lg n): for each value of m = 1...n/k, check if the first km characters is just k copies of the first m characters. If so, also check to see the longest prefix 1...i which matches km+1...km+i (using binary search). Then all strings from km...km+i will be regular (and with some minor details this gives you the output).

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

How to solve C ? Integer Programming seems too complex.

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

    I will describe my algorithm but I don't know if it is correct since I haven't got the chance to submit its final version because CF was not available in the last seconds :@ :@ :@

    We know that X * Wr + Y * Wb <= C.

    If we have fixed Y, then X <= (C — Y*Wb) / Wr. As we want to have maximum X, let's say that X = (C — Y * Wb) / Wr.

    Happines = X * Hr + Y * Hb. After replacing X, we get:

    ((C — Y * Wb) / Wr) * Hr + Y * Hb.

    Now, using binary search we can find when F(Y) starts to be less than F(Y-1), where F(Y) = ((C — Y * Wb) / Wr) * Hr + Y * Hb.

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

      I tried binary search and it failed.

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

        I tried too but it was implemented wrong and when I found the bug, the contest was over because CF was unavailable.

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

          Binary search will obviously fail because the function is not monotonic and even has several extremas. That's why ternary search is also not very good.

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

what's the best time complexity of problem c? I have solved similar problem on http://codeforces.me/contest/519/problem/C but here it's 10^9, and I always tle..... Could anybody give me some hint?

How about problem D?

Thanks : )

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

It was duficult.

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

I couldn't hack from Firefox (Chrome worked fine).

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

    Hi, could you prove that your solution on C works correct for all cases?

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

      If Wr is big, the number of red candies must be small. If Wb is big, the number of blue candies must be small. If both Wr and Wb are small, there are two cases: use less than Wb red candies or use less than Wr blue candies.

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

    To hack from firefox you would have to delete the browser's cookies

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

Problem C have been used in a regional contest in China.

http://acm.hdu.edu.cn/showproblem.php?pid=4091

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

Problem E: http://main.edu.pl/en/archive/oi/21/doo

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

So whats the dreaded test case 3 in problem C

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

    Here are two tricky test cases I used for hacks:

    999999999 10 499999995 2 99999999

    999999999 10000 494999 2 99

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

    Now that it's over:

    982068341 55 57 106 109

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

How to solve Problem B? I found out the path having maximum number of lights, but had problem in incrementing values of edges and distributing the increment among edges in a path. Maybe I complicated it too much.

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

Finally Division 1! :D

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

Became orange after 1.5 years not doing programming competitions xD

Btw, I solved C using some hacky brute-force constantly checking time limit until 0.9 second passes. How bad am I for doing is that?

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

    Very smart.

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

    Actually, it's easier to gain a lot of rating in a combined division round than a div1 only round for some reason.

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

      My wild guess: In div1 only round some fraction of participants prefer to skip the round, should they observe problem A is too hard. So you can't "steal" your rating points from them. Combined round has easy entrance problems, so much more skippers got trapped :) More people lose rating — more chances you get some

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

I solved problem a like so many other people did,a very bad solution that works because n<=100 here's my solution anyone knows why it's wrong? 10579934

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

Could anybody tell me why this solution of E is correct? It looks like magic. 10581607

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

Please, take a look at this submission.

We can see that an array check with 100 elements(indexed from 0 to 99) is declared.

int check[100]={0};

I tried to hack it with the following test:

100 *****...******

Here "..." means a lot of '*'s, not dots.

Let's take a look at the following for loop:

for(int i=0;i<s.size();i++)
{
    if(s[i]=='*')
        check[i+1]=1;
}

Here, the variable i can be up to s.size()-1 which is 100 — 1 = 99. Then check[i+1] will be check[100] but it is indexed from 0 to 99. Then shouldn't this be a runtime-error because it cost me -50 instead of +100 :@

PS: Something similar happened during Codeforces #297. I tried to hack this code. As we can see, the guy is pushing some things in a vector ot. And what if ot is of odd size:

for(int i = 0; i < ot.size(); i+=2){
  out += ot[i]*ot[i+1];
}

I think that if ot.size() is odd, then i+1 will be equal to ot.size() at some point which should be a runtime-error anyway but it wasn't...

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

    It doesn't give runtime-error. It causes undefined behaviour and sometimes works correctly.

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

      Ok, thanks! I thought that it should be RTE because usually on my computer it causes Segmentation fault and when I submit such code on lightoj it causes RTE :)

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

Can someone please explain the solution for problem E? I didn't understand it from the Editorial.

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

i wish i could won the jacket :(( its so nice :)

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

I really like the way in which testcases for E were generated.

All large tests are we'll give you 50 queires, but most of them will be same. Are you serious, guys? :) Looks like most of O(N * log(N) * Q) solutions can pass after adding memoization. My messy implementation (10587744) wasn't even able to pass pretest 10 during contest, and after adding memoization it runs in 1.6 seconds (10600918).

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

    Omagad, what a shame. It is reasonable to create a maxtest with worst case repeated, but in ALL of them -_-...

    What is more, there are some wrong submissions which passed (as pointed out above).

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

    What's more, just 21 tests.

    When I create tests, I usually also do something like "10 completely random tests" and variations of it several times. More tests won't kill anyone, especially on problems that won't have too many submissions. But this...

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

Is there any tutorial for this contest?

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

It looks like ZeptoLab has bad luck with repeating problems. As pointed above, C, E and F were already present in some places of the Internet and one year ago E was from Junior Polish Olympiad in Informatics (I watched editorial created by johnasselta during the contest :P) and F was used in Petr Mitrichev contest.

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

Will this contest an editorial?I haven't see it.

→ Reply