kaolinite's blog

Invitation to Inscription 2022
By kaolinite, 19 months ago, In English

Codeforces!

Greetings from NITK. We will be hosting a CP contest, Inscription 2022 as part of our college's annual technical fest Engineer, on September 25th on CodeDrills. We have many more tech events, which you can check out over here.

Contest Details:

  • Contest Link — Inscription 2022
  • Date & Time — 25th September 2022, Sunday, 12:00 noon IST
  • Duration — 2 hours and 30 minutes
  • There will be 5-6 problems of varying difficulty.
  • Will follow ICPC like scoring system (10 minutes penalty and 1 point per problem)
  • Telegram group for clarifications: https://t.me/+SQPJYPL2XwE1OTM1

Registration for prizes:

  • Do register here BEFORE the contest begins.
  • Only Indian participants are eligible for prizes but everyone can participate.
  • 1st rank will receive INR 2000
  • 2nd rank will receive INR 1000
  • 3rd rank will receive INR 1000
  • 4th rank will receive INR 500
  • 5th rank will receive INR 500

Panel:

The problem setting panel are:

I would like to thank all of them for the round preparation. Along with them, I would also like to thank

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

UPD: We have increased the duration of the contest from 2 hrs to 2.5 hrs. We have also increased the cash prize :)

UPD2: The contest is over and thank you everyone for participating! Editorials will published in a few days but feel free to discuss here. Please do upsolve the problems and give your feedback. Final ranklist will be out after some checks and winners will be contacted separately.

Thank you again!

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

Comments Comments (10)
| Write comment?
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Reminder! The contest starts in 15 minutes. Please do register for the prizes.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just a doubt, are the samples for Make friends, not enemies correct (2nd output) correct ?

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem F ?

I had a solution in which we have to find an optimal partition of $$$N$$$ members in which the difference between sizes of friends and enemies is minimum, this can be done by $$$\mathcal{O}(n^2)$$$ knapsack dp, which will obviously TLE.

I think there is a square-root optimization to this, but I don't know it yet, can anyone share their solution to this ?

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    you can refer it here(3rd technique) https://codeforces.com/blog/entry/100910

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

    It is very simple with bitsets

    Sample code
    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot for pretty simple pseudo-code, it is easy to understand how knapsack works here!

      → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      f(i, n)
{
    if (go.get_root(i) == i)
    {
        go2 |= (go2 << go.comp_size(i));
    }
}

      What is the time complexity to calculate subset sum dp here ?

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

What was the intended solution for E: Long Range Query?

I did an implicit lazy segment tree which was a little too close to the memory limit.

https://codedrills.io/submissions/498331

→ Reply