satyaki3794's blog

Invitation to August Easy '16 on HackerEarth
By satyaki3794, history, 8 years ago, In English

Hello Codeforces Community!

I invite you all to take part in HackerEarth's August Easy, scheduled on the 1st of August at 21:30 IST.

Problems have been set by me(satyaki3794) and tested by akulsareen. I am also grateful to HackerEarth admin belowthebelt for his help and guidance.

You will be given 6 algorithmic problems to solve in 3 hours. Partial scoring will be used (you get points for passing each test case). Although the contest is targeted towards beginners, we hope even experienced problem-solvers find one or two problems to be interesting. The contest is rated and prizes will be awarded to the top 5 beginners.

The main characters of this round are Mancunian, a die-hard supporter of Manchester United Football Club and his arch-nemesis Liverbird, who supports Liverpool FC. You will help Mancunian get the better of Liverbird by solving algorithmic problems. :D

GL && HF

UPD1: Contest is finished. Congratulations to the top 5.
1. codingstar7
2. zeliboba
3. Morphy
4. dk2nnth
5. azukun

UPD2: Editorials are live.

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

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

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

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

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

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

Did anyone say Manchester United?

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

25 minutes to go. Good luck, everyone! :)

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

We are sorry for the weak test cases which allowed sub-optimal solutions to pass. We somehow overlooked the possibility during testing and apologize to anyone who was affected by the issue.

Editorials have been released.

Any feedback, positive or negative, is welcome.

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

Why I am not able to view other's submissions ?

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

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

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

  1. simple brute force

  2. Graph traversal and while traversing keep storing the current closest ancestor for particular color in some array.

  3. Create new graph with nodes with pairs (i,0/1) where i is original node and 0,1 indicate even/odd time and use BFS to find shortest path.

4.Use MO's algorithm to calculate final answer,maintain inverse modulo for fun[] array to speedup the time.

5.I couldn't do in time but I guess approach was to if dis(N1,M1) <= k and dis(N2,M2) <= k and M1 is conncted to M2 then we can always pass to desired positions.

6.I guess we have to use suffix array somehow but I couldn't figure it out how,Hope if someone can help.

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

    The last question can be solved by hashing/palindrome tree. You're correct about the 5th one. Some of the editorials are out. The rest should be up soon.

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

I don't really think having a disconnected graph in problem 5 is appropriate.

What if M1 and M2 is connected and N1 and N2 is connected but M1 and N1 is not connected. Now the distance between M1 and N1 is undefined and we cannot determine is the distance exceed K.

I think you should at least define the distance between two disconnected points in the problem statement if disconnected graph is in the test data.

→ Reply