reyaan44's blog

Invitation to Codechef Starters 65 (InfInITy 2k22)
By reyaan44, 17 months ago, In English

Hello Codeforces !!

We invite you to participate in CodeChef’s Starters 65 (InfInITy 2k22), this Wednesday, 16th November. This contest is organized by InfInITy 2k22, IIIT Pune.

Time: 8 PM — 11:00 PM IST

The contest is Rated till 6 Stars on Codechef.

Joining us on the problem setting panel are:

CASH PRIZES :

  • Top 3 performers (Div 1) will be awarded cash prize of INR 10000, 7000 & 3000 respectively. Top performer of Div2 will be awarded INR 2000.
  • Top 2 Indian participants will be rewarded INR 4000 & 2000 respectively(for Div1 participants).
  • Prizes worth INR 7000 specially for IIIT Pune students.

Contest Link : Starters 65 (InfInITy 2k22)
Contest Timing : 20:00 to 23:00 IST
Registration For Prizes : Infinity Website or Google Form

  • The web development team Rushikesh rushitote Tote, Shashwat dumbpotato21 Khanna for building an awesome website for the contest.

  • Kunal notthatkunal Meena for amazing posters.

  • BiT Legion for making this contest possible.

For any queries contact: [email protected]

Past problem sets for the event: 2021, 2020, 2019

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest.

The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

We hope you will enjoy solving the problems. Please give your feedback on the problem set in the comments below, after the contest. Good Luck!

UPD :

Congratulations to the winners.

Global Div1 :

  1. Geothermal

  2. liympanda

  3. gyh20

India Div1 :

  1. yash_daga

  2. EnEm

UPD : Cash Prize Distribution Mails were sent to the international winners on 28th Jan, and a reminder mail was sent on 11th Feb. We request you to reply to it as soon as possible so we can start with the distribution process.

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

»
17 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Very Excited

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

Great! Looking forward to participate in it!

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

surely participate in this, but I really need a T-shirt of Bit-Legion :(

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

Let's see how the contest would be !!! ( I feel it would be good )

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

It was a great experience at ICPC there, can't wait to participate in this contest

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

Remainder: Contest starts in less than 60 minutes.

Problems are worth trying. Do participate!

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

Props to the person behind the stories in each problem. Especially gormint aunty

→ Reply
»
17 months ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

How to solve Lazy Ancestors?

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

Any hint on Gormint Aunty ?

Till the end, I was only able to observe that optimal length should be $$$\lceil\frac{n}{\lceil\frac{n}{k}\rceil - 1}\rceil$$$ when $$$k \neq 1$$$, though I don't know if it's correct or not

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

    Count max number of $$$1's$$$ you can place in the array. After placing the first $$$1$$$, it will take up $$$2*k-1$$$ slots, after then greedily filling $$$1$$$ to any of the ends will take up $$$k$$$ slots. Using this observation you can easily count the max number of $$$1's$$$ you can place in the array. Let this be $$$cnt$$$
    So, the optimal length for repeating the subarray should be $$$max(ceil(\frac{n}{cnt}),k)$$$.

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

    No greedy solution came to my mind. So I binary searched the answer and something similar to dp to find whether we can get the array by using a block of size in between [k,mid]. If we can move on to values less than equal to mid-1 otherwise go to values higher than mid+1. My solution

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

Lazy Ancestors is just a slightly simplified version of 1749F - Distance to the Path.

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

How to solve problem Haha?

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

    Handle n <= 6 by hand. We can use a brute force to observe that the maximum degree for n >= 7 is 4. The construction depends on n mod 4, but in all cases we can take the degree sequence to be some permutation of (1 2 3 4) repeated until we have n vertices. This degree sequence is valid because no prime number is a multiple of four. To realize this degree sequence, within each group of four vertices, we add the edges 1-4, 2-4, 2-3, 3-4. Then, we need one more edge incident to each of 3 and 4, so we connect each 3 to the next block’s 4. This also ensure that the graph will be connected.

    This construction works as stated when n is divisible by 4. Otherwise, we can modify it slightly, e.g when n is 3 mod 4 the last block will contain only a 1, 2, and a 3, and we can reduce to two vertices requiring one edge each by adding edges 1-2 and 2-3.

    As a more general note, I found it extremely helpful to write a brute force to generate the degree sequences. Doing so made it extremely easy to find that the answer is always 4 for sufficiently large n, and examining patterns in the output led me to the degree sequences in my eventual constructions. The only part I had to do by hand is the actual construction of a connected graph with the desired degree sequence, which is not especially difficult due to the periodicity of the sequences.

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

      Thanks. I thought the answers is relatively small (maybe 3, 4, 5). But I failed to find a clique of size 4 to prove that only four is enough. Maybe my sleepiness kept me from noticing the clique 1, 3, 6, 8. :))))

      I will try to implement brute force to observe the answer next time :)))

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

Any updates regarding the prizes?

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

    Hey, we'll be reaching out soon to the winners(1-2 weeks for Indian winners, 4-5 weeks for international winners) to get their details and transfer the prize money

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

I haven't received any notification about the prizes.

Any updates on that?

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

    Hey, we have reached out to the Indian winners, and we will be reaching out to International winners in a couple of days.

    → Reply