Errichto's blog

By Errichto, 9 years ago, In English

Hi everybody.

The IndiaHacks finals will take place tomorrow (on Saturday). The contest is being organized by HackerEarth. Just after the official finals, the CF round will start (check-your-time) with almost the same problems. You can treat it as a standard CF round — there will be 5 problems in each of 2 divisions, and 2 hours to solve them. Two divisions will compete together on the problem set with 7 problems, with 2 hours to solve them.

I want to especially thank I_love_Tanya_Romanova for testing the problems, GlebsHP for help with making the CF round possible, and MikeMirzayanov for his awesome attitude and for the Polygon system. Setters: Lewin, k790alex, Sokolov, Errichto. Testers: I_love_Tanya_Romanova, Errichto. Small help: belowthebelt, raviojha2105, johnasselta, Radewoosh. And my big thanks to HackerEarth for inviting me to Bangalore, it's truly a vibrant city.

Some info only for 40 official finalists — Remember not to discuss anything until the CF round ends (so, at least 2 hours after the official contest ends). You will find all important information at link-to-the-contest. You can ask me questions by PM on CF or on HE, and I will put answers in the "Challenge Details" at the link provided. Do not use comments here because it can only confuse others. You can use some old blog about the IndiaHacks semifinals if you want to discuss something.

I wish you great fun and no frustrating bugs. Enjoy the contest.

Scoring: 500-1000-1500-2000-2500-3500-3500.

WINNERS

  1. jqdai0815, the only one to solve all 7 problems!
  2. JoeyWheeler
  3. jcvb
  4. andrew.volchek
  5. ikatanic

In the official finals there were technical issues with the stack size (it was again only 8MB) and constraints in E weren't correct at the beginning. We want to fix it as much as possible, without any guessing though — we can't say how much time did you waste because of something. If you were affected then write to me PM with the description of the situation. Your time penalties will be canceled (and maybe some earlier submission will be accepted, if only the stack size didn't allow you to get AC).

Editorial is being created here.

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

| Write comment?
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

So the official finalists lose a rated contest? Or is there a way to add ppl to the standings afterwards and let them be rated?

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

    Yes, they do lose a rated contest. It's impossible to add them to the leaderboard, too many differences in the problem set.

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

    most of them will probably lose two rated contests if they are competing on-site

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

      The top 19 or so won't be competing onsite. World level vs country level...

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

We always expect some photographs in these onsite contests :)

»
9 years ago, # |
  Vote: I like it -17 Vote: I do not like it

A rated div2 contest after a long time.

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

Welcome to India Errichto! :)

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

Idk why, but March is so adored by different cups and competitions. It's hard to take a part in all of them, especially (speaking about me) because there is some All-ukrainian competition in this time too (I'm talking about Math and Informatics). So, can someone explain me why March is so adorable?

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

Note changes in the blog — the contest will be combined for two divisions. Make sure to register again.

»
9 years ago, # |
Rev. 2   Vote: I like it +75 Vote: I do not like it

It's goodbye 1394(in Iran)
Happy new year(1395) :)))

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

I think these 2 contests (CROC & IndiaHacks) are closer time-wise in history of codeforces.

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

Thanks for Announcement .

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

The name of this contest is "IndiaHacks" and none of the writers or the testers of this contest are Indian. Not that I am saying it's a problem but it feels a little weird.

»
9 years ago, # |
Rev. 2   Vote: I like it +47 Vote: I do not like it

Still decreasing in Div 1 after 6 months :(

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

    finally positive rating changes :))))

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

"The duration is 2 hours. I will try to inform you about the duration in a few hours."

Just in case the duration will change again.

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

Will the format be ACM or standard CF?

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

    It's never written about ACM, so I think it will be standart CF

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

I submit a hack but get Unexpected verdict.I want to know what happened.

»
9 years ago, # |
Rev. 5   Vote: I like it +6 Vote: I do not like it

I feel many submissions will fail in B. Will generating all strings give time out? And can it result in int overflow?

PS

My submission was running too slow for this test case

6 26

aa a

ab a

ac a

.. .. till az a

PPS — I was wrong. I forgot that we can only use a,b,c,d,e and f.

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

    6*6*6*6*6 = 7776 won't time out and neither will 6^6 = 46656

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

    Considering that the length must be between 2 and 6 inclusive, I really don't think that generating all the possible strings will be a problem

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

    46656 total strings possible in worst case and O(n) operation per string. Why should it tle? And no chance of overflow as total possible strings are 46656

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

    You can only use 'a', 'b', 'c', 'd', 'e' and'f', the test case you provided is invalid

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

      I forgot that. My bad.

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

        I think the test case is fine. You just have to put a check and skip the ones with 'g' and all. A possible hack case?

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

          "It's guaranteed that... all ai and bi consist of only first six lowercase English letters."

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

Such a difference between B and C. I think in B condition "a.i!=a.i for all i!=j" makes the problem much more easy

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

Anyone can share his idea about D/E?

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

    D. Max-flow with some tricks: Binary search on the answer. For answer being tested edge capacity equals maximum number of bears that can go through it. Calculate max flow. If it's more or equal than number of bears — such answer is achievable.

    E. Let's consider graph with all non-forbidden edges (G). G' = G with vertex 1 removed. Proposal: Answer is possible if and only if following conditions are met:

    1. Degree of vertex 1 in G more or equal than k.

    2. Number of connected components in G' is less or equal k.

    3. Each connected component in G' is connected to vertex 1 in G.

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

    In D, I did the following:

    1). I used binary search on the answer.

    2). How can we check if we can use this weight?

    2. 1). Calculate the weight that one bear carry. It will be totalWeight / x.
    
    2. 2). Now, for each edge, we can count how many bears can go through this edge.
    
    2. 3). Count maximum flow. The weight capacity of the edges in the graph will be the values we've counted in 2. 2).
    
    2. 4). When we've counted maximum flow, it will be maximum count of bears. If this value will be more or equal than x, then the bears can carry this weight.
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used the same approach but I am getting WA on test 44. Its because of precision issue, but I do not know how to handle this. LINK Correct answer: 1.000000 Output: 0.99991126

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

        You should change condition in binary search. Now you EPS = 10^(-9) * x Correct condition is (Math.abs(r — l)*x / (Math.max(r,1)) > E)

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

          Very old bump, but can someone explain the WA44 here? I don't get why my solution also only outputs 1 to 4 or so not 6 decimal places

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

    D: Binary search on doubles the check with maxflow if you can travel to the end with each bear's weight equal to the current middle in the binary search.

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

There is a strange bug(?) happening during contests. Whenever I'm seeing someone's solution, and this solution is hacked or resubmitted, a message pops up and I automatically log out.

This happened in yesterday's contest too.

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

When will start system tests?

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

How we can solve C simply?

I checked 7 possible states!!! :(

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

    Iterate through the array if you found a bad index i then you must swap i or i + 1. So try swapping i and i + 1 with the rest of the array and check if each swap will fix all the bad indices.

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

      OH MY GOD , thanks!!! My brain stopped in the contest. How stupid am I !!!

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

How to solve C? :)

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

    I think that you can find all "invalid" positions (d[i] <= d[i+1] or >=, whatever), and brute force to "fix" it with swapping with any other position. It's not hard to see that invalid positions cannot be too many (i set limit = 9, but should be <= 6 or smth), and you need a O(1) checking then.

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

      Ohh sh*t, that is actually too easy, thanks!

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

      I timed-out when trying all swap combinations, I never thought to only check bad indexes! :(

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

      How did you deduce that the number of invalid positions would be less than 6?

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

        We touch only two numbers. Let indices be i and j. Proposal: swapping them can fix only positions {i — 1, i, i + 1, j — 1, j, j + 1}. So if we have more than 6 "bad" positions, some of them will still be unfixed.

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

      Hello can you suggest similar problems! I fail on such easy to "see" problems.

      I knew that 4th was binary search with max flows but I don't know much about any algorithm of Max Flow so couldn't solve it! I was solving C yesterday using ternary search( I didn't knew much theory about it ) and couldn't debug (although I had that sliding window in my mind) I switched to D but was unable to deduce the fact! So Probably I am having very bad contests these days! I think I should take a break :/

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

    Considering positions i and i+1 as invalid if sequence[i] >= sequence[i+1], for odd i, or if sequence[i] <= sequence[i+1], for even i.

    You must notice that if there are more than 6 invalid positions then a single swap won't fix it, so you output 0.

    When there are 6 or less invalid positions just test all possible changes with them.

    The complexity is O(6*N) if you check if one change makes the sequence nice in O(1).

»
9 years ago, # |
Rev. 2   Vote: I like it +51 Vote: I do not like it

Looks like problems in the Codeforces round are significantly easier than those in the HackerEarth round.

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

    is it bad?

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

      Well, this round was initially announced as an online mirror of IndiaHacks Algorithm Finals, but now it looks more like a different contest. Also, because the problems are different, it is not possible to easily compare results of this round with those of the official participants, and discussing problems is also more difficult because some problems are different, and all the problems are in a different order.

      Not to mention that I spent some time solving problem E with a wrong constraint.

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

The period of waiting for systest to begin, is painful. They lock problemset and all. Maybe next time I'll contribute too so they can get more servers and keep them open for generic solving >.>

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

What is the idea for problem D ?, I tried to solve using binary search the maximum amount of weight one bear can deliver and check if it's possible using fordFulkerson. But I am getting WA in pretest 6. Am I missing anything ?

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

Damn it, integer overflow in D!!!. T^T

»
9 years ago, # |
  Vote: I like it -28 Vote: I do not like it
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Thank you. I myself would not have found.

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

How to solve D. I figured out that if I obtain residual graph and after that find flow from each edge which is leaving source node than I have to distribute 'x' bears over them. But how to do it? Or I started wrong?

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

Summary of HackerEarth problems:

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

    How to solve F from this problem set?

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

      If I'm not mistaken, if you already have a valid flow for x0, then the answer for x0 + 1 depends on the least amount of wood each bear needs to lose to create a new augmenting path from source to sink. If you compute, for each edge in the residual graph, how much wood each bear would need to lose to be able to send one extra bear through that edge (it can be 0 if the capacity is not full), then this is equivalent to finding a path from source to sink with the minimum maximum weight, which can be solved in O(E log V) by Prim or Kruskal.

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

        It seems to be true. Thank you!

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

        Yeah, that's how I solved this problem. The algorithm looks more like Dijkstra though, with the sum replaced with maximum. I tried to find the initial flow in the same way, but it didn't pass TL, so I had to add binary search.

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

    my solution for B( codeforces) and E ( hackerearth) has a complexity n*26*q .code

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

      Your program doesn't solve E from hackerearth.

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

        Is there any way to access the problemset from onsite ? I tried looking at hackerEarth recent contest but couldn't find anything.

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

          I think it will become available in a couple of days, maybe tomorrow.

»
9 years ago, # |
Rev. 2   Vote: I like it +177 Vote: I do not like it

Human stupidity at its finest: taking 50 minutes to notice a compilation error -.-'

(I'm so happy I did it before the contest ended, though :P)

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

    I know that feel bro, same sh_t with MLE, so now I catched -27 to my rating

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

    Wow so you just submit and don't wait to see whether you passed the pretests?
    #justgrandmasterthings

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

      I usually think so:

      "I`m not going to waste my time on waiting, see later"

      trying to solve next problem

      forgot about previous

      "OH WAIT WTF"

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

    I had a similar issue.

    I've noticed that I actually got TL for C only after successful submission for D. I'm pretty sure that I've seen "Pretests passed" for C and I think that it is the issue of twitchy status line that can change from "Running on pretest 7" to "Running on pretest 3" and back several times before showing an actual verdict. That's pretty sad :(

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

Why didn't my submission fail?

This line is wrong according to me

z.pb(a[k]+c[j][i-3]);

It should be

z.pb(a[k]+c[j][0]);

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

A total rating gain of 1 in last 24 hours

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

    A total rating change of 0 in last 24 hours :P

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

      Same here because I didn't participate in any of the contests :D

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

12 Legendary grandmasters! :D

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

Lol

Hashes with modulo = 264 passed :)

16814596

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

    Time limit for this problem was intended to be 1 second or 2 seconds for slow languages like Java to avoid these kind of solutions.

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

jqdai0815 rating looks like typical track in Gravity Defied now

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

I have got WA 2 for Problem C.

But locally with gcc 4.9 and on ideone.com with C++ 14 this code on this test was executed correctly.

http://mirror.codeforces.com/contest/653/submission/16816483

What's wrong with this code?

»
9 years ago, # |
Rev. 2   Vote: I like it +46 Vote: I do not like it

Somehow, tests for D allow to search only for blocking flow, not for maximum. Compare this accepted solutions: 16816698, 16816675 on next test:

4 5 2
1 2 3
2 3 3
2 4 2
1 3 2
3 4 3

(outputs are about 3 and 4, second one is correct).

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

There is a overflowing bug in my code of problem D.

My code will fail on the following case:

4 3 100000
1 2 2
2 3 1000000
3 4 2

And some other participants also passed the system test using int to store the capacity of edges.

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

What are results of onsite(?) round?

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

HackerEarth scoreboard.

Remember, HackerEarth has different problems.

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

Can you guess or prove why does it work?

Problem E solution. 16820873

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

    I suppose the testset in E is pretty weak. My original solution was too slow... so I just done some hacks in order to pass pretests: 16814798. I was super surprised when it was accepted on the main tests, because I'm almost 100% sure it's wrong.

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

      Have you tried to find some tests?

      I tried but has not found.

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

        Yes, for my solution I can came up with simple test on ~50 vertices (constant that I use in the code) that will fail. Essentially, there will be one bridge that connects one separate vertex to the fully connected component, and all the edges except one from this component to this vertex will be prohibited. Then this edge won't be discovered and the vertices will be considered disconnected.

»
9 years ago, # |
Rev. 4   Vote: I like it +76 Vote: I do not like it

Another suspicious North Korean code!

http://mirror.codeforces.com/contest/653/submission/16815024

http://mirror.codeforces.com/contest/653/submission/16811842

I think those codes are really identical — simply some names are the difference (ex, 'doit' <-> 'foo', 'xvalue' <-> 'dat')

I actually didn't really care about those stuffs before, but my 2599 rating makes me bit sensitive. MikeMirzayanov, can you investigate these deeper?

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

    Says the South Korean...

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

      Regardless of nationality, The fact remains :)

      (And the desire for IGM also remains..)

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

    Is it possible that this is some sort of template or part of an official solution to an earlier (North Korean) problem?

    Also, it's interesting that those nearly identical submissions still make a difference of 15 ms.

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

      It's not possible that this is some sort of template — problem E from this round wasn't that typical. Considering the huge simillarities between those two submission (they only replaced some name) maybe they were a part of an official solution, but then there is no way to punish cheaters (since the same logic belong to any cheated code). So this should be decided upon other reasoning like previous decisions.

      Also, "completely identical" submissions can easily make a difference of 15ms, so IMO it's not that interesting..

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

Will be tutorial?

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

Editorial Please!!!

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

wrong answer 1st numbers differ - expected: '1.0000000', found: '0.9999918', error = '0.0000082'

What a sad story :((

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

What's the meaning of dsu? I can see it in Problem tags sometimes.

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

Why has the round been made unrated ?

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

    My rating is as low as it used to be. Nothing's unrated.

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

      It was made unrated for a while because they were recalculating the ratings to remove cheating cases etc. I think.

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

Errichto And India
Thanks for coming to India. I hope you had a great time.
Image1
Image2
Image3
Image4
Image5