hetshah1998's blog

By hetshah1998, history, 2 months ago, In English,

Engineer, the annual technical fest of NITK, Surathkal, in association with HackerEarth presents Inscription, the online algorithmic programming contest of NITK. It is also the flagship event of Engineer's Computer Science Events' Committee. The previous editions of the event witnessed tons of participants from various countries and also successfully managed to attract some of the best coders of the world to compete for the top spot. This year once again Inscription strives to achieve its previous glory.

     Poster

The details of the competition are as follows:

Timings : 09:00 PM IST (14-OCT-17) to 02:00 AM IST (15-OCT-17) (Check your timezone here)

Contest Link : https://www.hackerearth.com/inscription-17

Prizes only for top 3 Indian winners.
- First Prize : 10000 INR
- Second Prize : 6000 INR
- Third Prize : 4000 INR

To be eligible for prizes, please fill the form : https://goo.gl/forms/QmDYxuLFWIE06x572

RULES:
1. This is an individual contest.

2. You will receive hundred points for solving a problem (passing all test cases — no partial credit), regardless of the level of difficulty of that problem.

3.The total time is the sum of the time consumed for each problem solved. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submittal of the first accepted run plus 20 penalty minutes for every previously rejected run for that problem. There is no time consumed for a problem that is not solved.

We have tried our best to create an interesting problemset, and we hope that everyone finds something interesting in the tasks. Editorials will be published for all of them at the end of the contest.

Here is the link to : Inscription '16

We hope you'll have an amazing time! Happy Coding!! :)

Reminder : Contest starts in less than 45 minutes.

Hope you had fun! Please spare some time to fill the feedback form https://docs.google.com/forms/d/e/1FAIpQLSfvYCJ_U_PgeVqc9_ytyYova8nIuAw-qRE1OrEV974O2JPmBA/viewform

Editorials for The Saracen Showdown, Arrival of the Saboteurs, Hungry Jerry and the Saracen Defence can be found here : https://docs.google.com/document/d/1rkdYj_TQP9sUlmIPFUglSThIZ9q-vozHh39U5hCJyBg/edit Remaining editorials will be released day after tomorrow

Winners of the contest are :
saharshluthra
jtnydv25
adkroxx

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Editorials?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

My solution: Calculate lengths of path inside cycle for both and let their difference be d. Now take smallest factor of (b-a)(Assuming b>a) which does not divide d(this is answer). with special cases of b-a=0,d=0.

IS this correct?? Any other Ideas??

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

    It is clear that the pointers cannot meet outside the loop if their speeds are different. Assume B > A. Suppose they meet at time T from the start, then the pointers would have traversed T * A and T * B nodes. The slower pointer would have traversed K nodes of the straight path (including node 1). The faster pointer would have traversed K — D nodes of the straight path (including node 1).

    We can now find the number of nodes traversed by each pointer inside the loop. The slower pointer traverses T * A - K and the faster pointer traverses T * B - (K - D) nodes. If they meet at time T, then both those numbers must belong to the same residue class mod L , where L is the loop length.

    T * A - K = (T * B - K + D)modL
    T * (A - B) = DmodL

    For such a T to exist, GCD(L, A - B) must divide D. So the problem reduces to finding the least L such that GCD(L, A - B) does not divide D. It is equivalent to finding the smallest factor of abs(A - B) which does not divide D.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Did you get AC with that?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        Yeah, I was the author of that problem (:P). That was the expected solution.

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

          Did exactly that, but one test case overflowed in intermediate calculation. Passed 99/100 cases but could not get that one case accepted :/

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the approach for palindromic tree

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

What is the intended solution for Saracen Showdown?

If I have understood the question correctly shouldn't it be simply: allow x to be connected to y if with whatever cost the question has given. Run Hungarian. I tried this approach and got WA.

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

    Yeah, that was exactly the expected solution. The problem statement asked for the indices that are connected. You got the minimum cost right but you printed the residue values instead of the indices.