crap_the_coder's blog

Invitation to D'Code 2023 from Amalthea, IIT Gandhinagar
By crap_the_coder, history, 2 years ago, In English

Hello everyone! Hope you're all doing well.

Guess what? The next edition of D'Code by IIT Gandhinagar is here!

We have 6 algorithmic problems prepared for you to put your mind to test your problem solving skills.
The contest starts today at 9 PM IST and has a duration of 2 hours. Link of the contest: https://www.codechef.com/DCDE2023

Need an incentive? We've got you covered. There are exciting prizes worth ₹26,000 for the top performers!
NOTE: You need to register here, to be eligible for prizes.

Setters/Testers: mshandilya, crap_the_coder, nishuz, Karan-Gandhi, dewansh461.

Good luck for the contest and we hope you all have fun! :D

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

Comments Comments (22)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

problems not loading

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

Clashes with Meta Hacker cup. Pls reschedule.

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

Status: Wrong Answer Submission ID: 1028653819 Memory: 3.7M Sub-Task Task # Result (time) 1 0 Correct (0.00) Subtask Score: 100% Result — Correct Total Score = 100%

Sorry, i am not familiar with the platform. Total Score is 100% while Wrong Answer! How does it work?

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

bruh wtf is the time limit for D ??

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

nishuz orz

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

Is there a mistake with this idea for Trade Center? Or is it just a mistake in my implementation?

  • Goods from city $$$x$$$ will always travel on the shortest path from $$$x$$$ to $$$t$$$.

  • The shortest path routes represent a tree rooted at $$$t$$$ (since it is "guaranteed that there exists exactly one cheapest path between the Trade Center and any other node")

  • Query 1 is equivalent to $$$w_{u} \cdot dist_{u}$$$.

  • Query 2 is equivalent to $$$\sum_{x \in subtree_{u}} {w_{x}}$$$ in this new tree.

  • Query 3 is equivalent to $$$lca(a, b)$$$ in this new tree.

Query $$$1, 2, 4$$$ can be handled by using any point update, range sum query data structure on the dfs order of the tree since $$$subtree_{x}$$$ represents a contigious range $$$[in_{x}, out_{x}]$$$ in the dfs order. LCA can be calculated normally by your choice of implementation.

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

Posting announcement 3 hours before the contest? Do you think people live on CF or what?

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

How to solve break stick? I used gnu pbds but it gave me TLE.

Also where can the editorial be found?

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

    Gnu pbds has high constant factor. Here, Use Fenwick tree, it is very fast.

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

      Hi can i use lazy segment tree? for range updates

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

      https://www.codechef.com/viewsolution/1028659335 ???

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

        I don't have access to your submission. My ordered set soln was also giving TLE.

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

          I tried this after failing with seg tree and ordered set and still got TLE

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

            Where are you submitting your code? The problems are not available for submit for practice for me.

            My AC code
            → Reply