belowthebelt's blog

August Clash 2016
By belowthebelt, history, 8 years ago, In English

Hello, Codeforces community!

I want to invite all of you to participate in August Clash at HackerEarth. The contest is scheduled on August, 13. The contest duration is 24 hours, so there should be some comfortable time for every timezone. :)

There will be six tasks in the problemset. Five of them will be standard algorithmic problems with partial solutions allowed — you get points for every test that your solution passed. And the last task is an approximate problem — your score for this task depends on how good your solution is comparing to current best solution.

SmallBoy and MadNick are the authors of this problemset. They've done a great job preparing the problem-set. And I hope you guys will enjoy the questions prepared by them. I would personally say that the problemset is extremely interesting, We also hope that several problems will be not too hard for beginners. (Hint: partial scoring) Some tasks are challenging enough to make this contest interesting for more experienced contestants.

Sumeet.Varma worked on this contest as the tester and editorialist — he is responsible for taking care of the problems. And not surprisingly, he has done a commendable job for testing the problem-set. I hope you guys will not be disappointed. I was working on this contest as the moderator, and tester for the system(s). :)

As usual, here is one more reason for you to participate in this contest:

Top5 of leaderboard will also receive some nice prizes:

  1. $100 Amazon gift card + HackerEarth T-shirt
  2. $75 Amazon gift card + HackerEarth T-shirt
  3. $50 Amazon gift card + HackerEarth T-shirt
  4. HackerEarth T-shirt
  5. HackerEarth T-shirt

Good luck to everybody — hope to see you at the scoreboard.

Update:
Here are the winners:
1. mugurelionut — 600 points.
2. anta — 599.215 points.
3. LHiC — 562.644 points.
4. azneyes — 558.818 points.
5. ceilks — 544.81 points.

Congratulations to the top 5, great performance! :)

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

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

Here come dat smallboy

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

We've the first full score on the leaderboard, in the form of mugurelionut. anta is inches away from claiming the top spot again. This is an interesting round of Clash! :)

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

Can anyone explain the solution of Joseph and String briefly? I'm having trouble understanding the editorial.

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

    I solved the problem using Suffix Tree. I think my approach is simpler than the approach described in the editorial.

    Consider the suffix tree of the input string. Then, the score function is "(the number of leafs in the subtree rooted at the node) × (the depth of the node)" for a corresponding (explicit or implicit) node in the suffix tree.

    The answer of a query now corresponds to the maximum in a path on suffix tree. We can consider only explicit nodes and the ends of the path.

    We can solve it by standard techniques eg. doubling or HL-decomposition. Total complexity is .

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

Am I right that in Nick and JosephLand, edges in each biconnected component can be directed in a way that every travel starting and ending in the same biconnected component will have cost 0, and thus I should only care about brides? I tried to implement this idea and got WA but maybe I had a mistake in my code, I was very sleepy so I just went to bed.

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

    You are right. Did you take care the multiple parallel edges? Standard implementation can fail on multi-edges.

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

      Thanks, at least I was on the right way! And yeah, I didn't handle parallel edges, although I knew I should handle them and I thought I handled them, now I see, thanks :)

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

Three hardest problems involved trees — it's a bit too much. Also, I would say that they were harder to implement than to come up with a solution. Still, it was a nice (useful) practice for me because I suck at implementing not-trivial codes on graphs and trees.

Regarding statements — Nick and JosephLand was quite elegant/natural but in Joseph and String the story didn't make sense. Why something on Facebook page? Why was it in bold? Also, kudos for nice format of statements — this is how problems should look like.

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

Is a solution with Mo's algorithm and binary search possible for Greedy Chairman? I haven't thought much upon it so I am unsure if it would work.

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

I tried to solve problem A using the 'small to large' approach mention in this editorial. Some solutions which implements the approach runs very quickly.

I used policy based data structure to implement my set. I am under the impression that my solution is O(Nlog^2N) + O(QlogN). But it fails in most test cases. Actually solution with vectors passed more test cases than this.

Any ideas why the 'small to large' solution is timing out?

Code using policy based data structure: http://ideone.com/QydU6N

Code using vectors: http://ideone.com/EvNAot

Edit: In my eternal attempt to reach heights of stupidity, I was basically swapping the set variable not the pointer. So the swap operation was not constant. Got it accepted after changing the swap operation.

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

What was the favorite problem of the entire set for people who participated? My personal favorite was the approximate problem for a lot of reasons.

→ Reply