Vichitr's blog

ICPC Amritapuri Practice Session #3
By Vichitr, history, 4 years ago, In English

Hello Codeforces,
I invite you to participate in the ICPC Amritapuri Practice Session #3 hosted on CodeDrills in coordination with ICPC Amritapuri. It would be a 1.5 hours long contest having 4 problems of varying difficulty.

Contest Details

Registration

You will need an account on CodeDrills to participate in the contest. If you have not signed up on CodeDrills yet, do so here. If you already have an account, no extra registration is required.

Prizes

  • Cash prizes of INR 35000 for top 15 ranks.
  • 1st Place — INR 5000
  • 2nd, 3rd Places — INR 4000 each
  • 4th, 5th, 6th Places — INR 3000 each
  • 7th, 8th, 9th, 10th Places — INR 2000 each
  • 11th, 12th, 13th, 14th, 15th Places — INR 1000 each
  • Only Indian participants are eligible for prizes but everyone can participate.

Special News

I hope you will enjoy solving the problems. Any feedback is appreciated after the contest.

Good Luck & Have Fun!
Hope to see you participating!!

UPD1: Editorial/solution outlines are out! Check them under Editorial tab for a particular problem!

UPD2: We have also received some feedback on penalty rules of the contest and will be looking to tweak them in future contests.

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

Comments Comments (19)
| Write comment?
»
4 years ago, # |
  Vote: I like it -42 Vote: I do not like it

Man, 14th Feb is Valentine's day. We all will be solving problems instead of ...

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

    We thought of large community of programmers who think their valentine is none other than code! So that they can spend some quality time with their valentine!

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

Reminder: Contest starts in around 30 minutes!

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

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

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

Anyone got AC using NTT in the last problem Unique Strings? When I did NTT ( which runs in $$$O(n \cdot logn)$$$) I got TLE. But when I did simple brute force multiplication of polynomials (which runs in $$$O(n ^ 2)$$$ ), I got AC within $$$80 \text{ms}$$$. Ofcourse, factor of $$$26$$$ will be there in both the cases.

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

    I AC'd with FFT-Mod in 80ms: Code

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

      My code is similar like yours , still it's giving WA. link

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

      Thanks! I also did the same thing. Initially I kept FFT_CUTOFF as $$$150$$$ but got TLE (link), after changing it to $$$300$$$ I got AC (link) .

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

        Can you please share your brute force sol link too.

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

          Link

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

            I will request you to clear One more doubt. this problem is same but here we don't have to explicitly find the n-tuples for Integer solution of $$$x_1+x_2+...+x_n=k$$$. and complexity here is $$$O(nk)$$$ like $$$O(26*k)$$$ (if only 26 boys like alphabets in unique string task) but for Unique String it's $$$O(26*k^2)$$$. So the question is — Is this increase in complexity because of we are interested in the n-tuples explicitly i.e. value corresponding to each $$$x_i$$$ also. Or is there any way to solve Unique string in $$$O(26*k)$$$? IceKnight1093 or Jaydeep999997 or anyone please

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

    We originally had the problem with large constraints, $$$n = 10^5$$$ but later, we decreased it to pass $$$O(n^2)$$$ dp solutions. Hence $$$O(n^2)$$$ polynomial multiplication also passed in given TL.

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

https://ideone.com/InFQ4d this is my submission for problem c city divisions. My approach is of O(n^6) by using dp can anyone please help me understand what am i doing wrong ?

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

Can anyone share their solution for city division using entirely iterative dp?

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

Any idea when will the official ICPC rounds will take place in India, this time it has been a long delay and when will the registrations start?

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

    Official announcement is out now! Link — https://www.amrita.edu/icpc21

    Amrita will host the 2020 Regional contest that was cancelled because of the pandemic, in May 2021. Both the Preliminary Round & Regional Round will be held online on CODEDRILLS platform.

    Preliminary Round: May 16; 2.5 hours duration. Registration to start on March 1 on Baylor System and ends on April 30. There is no Registration fee to participating in the Preliminary Online Round.

    Regional Round: May 30; 5 hours duration. Teams will be promoted after the Preliminary Online Round.

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

      Well, this is a great news to me.

      But, Do I have to be happy about it or not : Both the Preliminary Round & Regional Round will be held " online " on CODEDRILLS platform.

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

        That was just the initial announcement. They may or may not keep it onsite depending on the pandemic situation. Let us hope for the best.

        → Reply