We invite you to participate in CodeChef’s Starters 93, this Wednesday, 7th June, rated for all coders.

Time: 8:00 PM — 10:00 PM IST

Note that the duration is 2 hours. Read about the recent CodeChef changes here.

Joining us on the problem setting panel are:

Setters: Kanhaiya notsoloud1 Mohan, Likhon5, Saksham sakshamm123 Mahajan, Shivansh ShivanshJ Jaiswal, Andrei Sho Alexandru, Divyesh divyesh_11 Jivani, Mostafa Beevo Alaa, Tushar CODE_LOVER4655 Singhal

Testers: Nishank IceKnight1093 Suresh

Video Editorialists: Madhav jhamadhav Jha, Suraj jhasuraj01 Jha, Jwala jwalapc, Adhish ak2006 Kancharla, Pravin pravin_as Shankhapal

Text Editorialists: Nishank IceKnight1093 Suresh

Statement Verifier: Kanhaiya notsoloud1 Mohan

Contest Admin: Jatin rivalq Garg

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.

We’re hiring! If you’d like to **intern** at CodeChef as a **Learning Content Creator**, click here.

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.

Are you ready to dance to the rhythm of Ariana Grande's songs while coding? We sure are! Join us for an unparalleled contest experience. And before you go, drop your favorite Ariana Grande song in the comments. Let's see which tune gets the most love!

orz

gk orz

rivalq saar ORZ

Ariana Grande? I listen to Blinding lights (by TheWeeknd) more while coding.

can you stay up all night? (giggity)

depends

My favourite song is "Break up with your girlfriend" as this song motivated me to breakup with my anime waifu and touch grass

Reminder: Contest starts in 3 hours.

"Positions"

"7 Rings" is the best song by Ariana Grande. Try proving me wrong!

ikr

In problem "GREEDY" can be replace the same character with different brackets if they are separated? i.e. can "bab" be replaced by "())" ?

Test case for BreakFree seems wrong. https://www.codechef.com/START93D/problems/REMOSET

Yeah the logic getting Wrong in java but the same logic got accepted in python, why this shit is happening rivalq?

That shit is happening because you are not taking care of overflows in Java. You can read the editorial to see how it should be done.

Is that a cool tairitsu pfp?

Are you gonna put only 3 easy problems in div3 section??

How to solve NASA

number of palindromic numbers below 2e15 are 427

so precalculate all those number and iterate in array and see how we can form those numbers

Bruh

but checking xor for all i and j pairs in 10^5 length array would be fine ? I precomputed palindrome numbers , stuck on xor part

Here is my AC solution( link)

Why is Kosaraju TLE'ing on SORTP9

Were you storing all the edges?

(ノಥ,_｣ಥ)ノ彡┻━┻

Sorry sirs :(

I don't think checking for SCCs is required at all. A simple DFS should be fine.

Let $$$v_x$$$ be the node representing the value $$$x$$$, and $$$i$$$ be the node for index $$$i$$$ ($$$1 \leq i \leq N$$$).

Observe that if an edge $$$v_a \rightarrow v_b$$$ exists, then $$$b$$$ is a submask of $$$a$$$, which means $$$\neg a$$$ is a submask of $$$\neg b$$$. So the edge $$$v_{\neg b} \rightarrow v_{\neg a}$$$ also exists.

For simplicity, consider the path from node $$$i$$$ to $$$j$$$ that passes only through some value nodes:

It's easy to see that a path from $$$j$$$ to $$$i$$$ is guaranteed to exist:

Or instead: proof by AC :)

In Thank U, Next, why is distance the number of

nodesand not the number ofedgesin the path?What is the logic for Thank U, Next

something like a multisource Dijkstra, idk what else to call it

Then how will know that which mail carrier node is closest to the specific node ??

using a distance array and updating it with maximum possible available nodes

multi source bfs read this topic .u will be able to do it very easily .can be extended by multi source dijktra to solve the problem very standardly

BFS. Put every node x[i] in a p_queue acc to their d[i] and do bfs if d[i] become 1 for any node remove it from queue. Once your queue become empty check every node is visited or not

You take the initial k vertices put them into a heap kind of thing, sorted by their ranges, extract the vertex with the largest range, delete it from the heap, update the max range of every other vertex reachable from the extracted vertex, (val-1, if val is the range of the extracted vertex), also add into the heap new vertices which have not yet been deleted from the heap with their respective ranges, do it until the heap is not empty. Now, if every vertex has at least once been extracted, HURRAY!

NASA can be just solved by this lmao:

Spoilersorry i am noob but why did you stop at 32823 but not continued from 32923 let suppose

see the constraints of elements of the array, they are till 2^15

32923 crossed our given range (2^15). xor operation can not produce more value than input.

xor operation can not produce more value than inputThis is not quite correct. For example $$$1 \oplus 2 = 3$$$, which is larger than $$$1$$$ or $$$2$$$. The xor operation cannot make higher bits $$$1$$$ than the highest bits of the input values. Mathematically stated:

If $$$0 \le a,b < 2^n$$$ for some $$$n\in \mathbb{N}$$$, then $$$0 \le a \oplus b < 2^n$$$.

sorry for that.. i actually mean the same.. as input < 2^15 then sum of 2^0 t0 2^14 is 2^15-1 as u said. Thanks for find my mistakes

Pretty similar to the solution given above , but it threw tle . why ? https://www.codechef.com/viewsolution/97897769

How to solve Greedy ?

Using DP.

Notice that the string can be split into maximal segments of consecutive characters. In each such segment, all characters must be equal to each other, but characters for all segments can be chosen independently of each other.

Now, consider some bracket sequence. Convert this into a sequence of integers:

`(`

gets replaced by $$$1$$$,`)`

gets replaced by $$$-1$$$. Now, the bracket sequence is an RBS iffSince all characters within a segment need to be equal, a segment of length $$$len$$$ will change the prefix sum by $$$+len$$$ or $$$-len$$$. $$$-len$$$ is not possible, if this would make the prefix sum negative.

Now, we create an array containing the lengths of all segmets of equal characters (in order). Now, we calculate all possible prefix sum values at the end of each segment using knapsack dp in $$$O(n\cdot \text{number of segments}) = O(n^2)$$$. If we can get a prefix sum equal to $$$0$$$ at the end, a solution exists. We can find this by doing backtracking on the dp array.

Why was this contest rated for 7-star coders, above other Starters? I felt the problems were quite easy for a "div 1" contest.

It is true that this contest was easier than some previous "Rated for All" Starters. But as mentioned here, we do expect it to be sometimes less challenging for the highest rated participants now. The range of "Rated for All" contests has increased, and so there will be some contests where IGMs solve all problems without too much sweat.

We just feel that there are enough users in the 7-star range as well, who find these challenging enough to have it be rated for all. For eg. in yesterday's contest, there were 25 7-star coders, and 8 of them solved all 7 problems. But 10 couldn't solve 1 problem and 7 couldn't AC 2 problems. Given that we definitely cannot have contests every month where the number of AKs is 1 or 2, we feel that having occasional easier Rated for All contests is a better compromise than having much fewer Rated for All contests.

Maybe from the next time, we'll also add something along the lines of "We expect it to challenge IGMs" or "We expect IGMs to AK the problem set" in the intro blog. Would that help?