Блог пользователя Vichitr

Автор Vichitr, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +50
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -42 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    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!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Reminder: Contest starts in around 30 minutes!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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) .

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you please share your brute force sol link too.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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?

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +19 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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.