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:

Setters: Reyaan reyaan44 Jagnani, Apoorv apoorv_me Kumar, Nishit nishit.sharma Sharma, Sahil still_me Tiwari, Daksh freaking_fab Nahar, Ashu ashu_2004 Mittal, Amaan amaan0016 Parvez, Arvind arvind26 Khandelwal.

Testers: Utkarsh Utkarsh.25dec Gupta, Takuki tabr Kurokawa

- Statement Verifier: Nishank IceKnight1093 Suresh
- Video Editorialists: Sundar K Letscode_sundar, Garvit garvitvirmani0 Virmani, Madhav jhamadhav Jha, Suraj jhasuraj01 Jha, Jwala jwalapc, Rohit ezo_tihor Oze, Adhish ak2006 Kancharla
- Text Editorialist: Nishank IceKnight1093 Suresh
- Contest Admins: Nishank IceKnight1093 Suresh, Satyam satyam343

**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 :

India Div1 :

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.

Very Excited

Great! Looking forward to participate in it!

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

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

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

Remainder: Contest starts in less than 60 minutes.

Problems are worth trying. Do participate!

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

How to solve Lazy Ancestors?

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

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

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

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

How to solve problem Haha?

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.

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

Any updates regarding the prizes?

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

Cool, Thanks for the reply.

I haven't received any notification about the prizes.

Any updates on that?

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