Hello Codeforces !!

**Aparoksha** is back with the second edition of the flagship-event **CodeRed**.

Last year's CodeRed 2018 was a great success with over 900 teams registering for it.

If you have the appetite for algorithmic problem solving, then don't miss it out!

It will be a 4.5 hour long **team event** with a maximum size of the team being **3 members**.**The participants need not be from the same college/institution/organization.**

The preliminary round will be held on **Codechef**, and the onsite round will be held during Aparoksha.

The total prize money is worth **INR 125,000 (Including goodies for all teams selected for onsite round, travel expenses* and cash prizes worth INR 50,000)**.

The **best 40 teams** will make it to the onsite round.

Also, top **3** teams in the **online round** will get **INR 4500, 2500 and 1500** respectively, along with Codechef Laddus.

All teams making it to the onsite round will get CodeRed T-shirts.

Contest link is here — CodeRed 2019.

The problem set comprises **7 problems** of varying difficulty level.

So be ready to have a nail-biting experience on March 2, 2019 at 21:00 IST.

The problems have been set and tested by Shivam Garg (shivamg_isc), Ankit Rao (hybrid), Sahil Prakash (prakashs99), Vaibhav Srivastava (dworst077), Saurabh Kumar (shauryakr) and Mohammad Aquib (aquib786).

Special Thanks to Teja (tejavojjala) and Sacheendra (sacheendra9044) for their valuable input.

Facebook Page — CodeRed Facebook Page

Some of our previous contests —CodeRed 2018, Alkhwarizm 2017 and HumbleFool Cup 2016.

See you in the **ENDGAME** :D !!

**Upd 1:-** Contest is about to begin in almost 1 hour. Best of luck :)**Upd 2:-** The contest is over, and was a great success with a mammoth 1271 teams registering for the contest.

Thanks for the overwhelming response. :D

Congratulations to the top 5 winners :D

- farhodkerimtemurbek — Kerim.K, Farhod_Farmon
- 1e9+7 Bugs Per Second — Ashishgup, Slow_But_Determined, vntshh
- PaduKeDeewane — hitman623, enigma27, _shanky
- Ryuzaki — Hiren.Vaghela, Learner99
- fast_coders — acraider, nitixkrai, fsociety00

Top 3 teams will get cash prizes of INR 4500, 2500 and 1500 respectively, along with Codechef Laddus. :)

Feedback of the contest in the comments will be highly appreciated :D

The detailed editorials will be posted on Monday.

For now, I am posting the hints.

**CR191**

**CR192**

**CR193**

**CR194**

**CR195**

**CR196**

**Upd 3:-** The Editorials for the problems are here. We will add for the remaining 2 problems in few hours.

Please update the editorial soon after the contest...

Is it necessary for participants to be in same college/institution?

yes, the participants must be from the same college/institution/organisation. The contest is open for both professionals as well as students.

I talked to the organisers just now. The participants

now do not needto be from the same institution/organisation. :)How to solve the "We are in the endgame" problem? My initial thoughts were to find the graph corresponding to transitions between consecutive 4 letter sequence and then delete the forbidden vertices. Then, the number of walks of length n correspond to (n-4)th power of adjacency matrix. After deleting the vertices, the number was 136. The complexity was

O(n^{3}log(10^{18}) * 100000) which would have TLEd?You thought it correct. The initial solution will be a 64*64 matrix stating the transition from one 4 letter state to another. Unfortunately This will obviously lead to TLE.

One of the possible ways was to solve the linear equations that are formed from some of the initial solutions by means of Gauss Elimination. This will fetch you a matrix of size 3*3.

Isn't the initial matrix to be formed is of size 4

^{4}× 4^{4}or I am missing something?The initial matrix size can be reduced to 4

^{3}* 4^{3}.So let's say you have a three letter state (

i,j,k), and you want to go to another three letter state (l,m,n).For that you can run a nested loop of 64*64, and need to ensure that

j= =landk= =m, and then ensure the 4 characters than form now (i,j,k,n) should follow all the constraints/conditions that follow.Hope that answers your question

In the problem CR195 how is the answer 136 in case n = 4? We wrote bruteforce and got answer as 120. Can you please explain?

You get answer as 120 if you also remove sequences like (UDLR), which should not have been removed as explicitly mentioned in the question :P

(Made the same mistake for around half an hour, and realized once they updated their testcases)

RIP I read it now! There should have been an announcement atleast if the problem statement was updated and new test case was added!

Problem statement was hardly updated with one more example of RDLU. We just added one extra case in sample for n=4. And unfortunately even the Announcement Section is not working today :/ I can't comment anything there regarding the further info or anything.

https://ideone.com/yrPw7e

Consider this DP solution as a brute way of finding the answers. a,b,c and d denote the last 4 elements chosen in the string.

Easier way to write that DP: http://p.ip.fi/qEQV

The way you write solution i am starting loving you...<3

fangirl++

you stole my upvotes:(

https://www.codechef.com/CORD2019/problems/CR197 = https://codeforces.com/contest/913/problem/C (saw someone's solution and got to know this :( )

Ah, that explains my deja vu.

Yeah we got to know this in the middle of the contest regarding the blunder done by one of our setters. However, it was already too late. :(

We are considering what to do regarding this particular problem.

I personally think, this shouldn't affect anything related to onsite, as many teams solved CR197.

But the key to get top 40 was to solve at least 4 problems (4th one being, CR191 which was solved only by 36 teams). So the teams qualified to onsite have no advantage because of the 3rd one being copied.

In fact, my team had no idea about the same as well. I hope the organizers will take this into consideration :)

Couldn't figure out anything for 3.5 hours despite having solved the 4th problem. I was amazed by so many correct submissions for this problem. Finally I decided to google search and found this problem which was exactly similar. I copy pasted the author's solution of this problem and it gave WA. Then I realized that the statement

`1 << i`

must be changed to`1ll << i`

and I submitted that and it got ACd. That was really disappointing.Surprising, I didn't know this problem before. But I was able to prove it was greedy and went ahead with implementation and got it accepted. But really disappointing to see it was a copied one :/

What is the intended solution for CR192?

The hints have been posted above.

Please make the problems available for practice.

The problems are visible now.

A very good contest, really enjoyed solving the problems.

Thanks a lot for your feedback :)

My logic for problem CR191( I can do this ALL DAY) was similar as given in the hints. Can anyone explain what is wrong in this solution?

My solution link is : Link.

Thanks in advance :)

The correct answer is 1 , but your solution gives 2.

Amazing contest with over 1200 teams participating...!!

A well balanced contest...

Kudos to the problem setters..!!

How to solve CR197?

It can be solved being greedy in choosing the stones first you eliminate the stones which are "too costly " according to their power. For that lets say you are seeing stone i, and say you're testing whether stone j is too costly, where j > i, we can see if cost(j) >= cost(i) *(2^(j — i)), then stone j should never be used. After we have got all the costly stones out of the way, we just iterate from the last stone and pick up as many we can(if x power is needed, we pick x/power(i) instances of this stone i). now the remaining power = x%power(i). Keep doing that we get our answer.

Hello! I have tried to solve this problem using the above approach that you have mentioned but I am getting wrong answer(WA). Can you please tell me that where am I going wrong?

Code Link : https://www.codechef.com/viewsolution/23670421

any good tutorial on digit dp online ? can anyone share it ,

This worked for me.

Actually I didn't know what was digit dp, with my basic knowledge of dp and bit of a thinking, I derived the states and transitions within the contest time limit, and it got accepted.

So I think if you give it a little thought in the angle of dp, you don't need a tutorial for the same and next time it can become pretty intuitive as well.

not to forget the adrenaline rush of getting it accepted in last 23 seconds <3

Yeah of course!!! <3

Editorial?

They are posted here.

I think you should link the editorial to the problem statement. They will be easy to find in this way for anyone trying to solve the problem later.

When will we get list of the shortlisted teams?

Got it :)Are you coming?

How to solve problem — "whatever it takes!" (onsite round) .

It can be solved using

Matrix Exponentiation.If the array is $$$A[1], A[2],..... A[N]$$$.

Let's say the Matrix for the recurrence be $$$M$$$.

$$$F(Val) = M^{Val-1}$$$

For all subarrays ending at index $$$i-1$$$, the sums shall be —

$$$Sum_1 = A[1]+A[2]+.....A[i-1]$$$.

$$$Sum_2 = A[2]+..........A[i-1]$$$.

....

....

$$$Sum_{i-2} = A[i-2]+A[i-1] $$$

$$$Sum_{i-1} = A[i-1]$$$

So, the matrix from all subarrays ending at index $$$i-1$$$ is

$$$Answ_{i-1} = M^{A[1]+A[2]+.....A[i-1]-1} + M^{A[2]+..........A[i-1]-1} + .... M^{A[i-1]-1}$$$

Now, matrix from all subarrays ending at index $$$i$$$ is

$$$Answ_{i} = M^{A[1]+A[2]+.....A[i]-1} + M^{A[2]+..........A[i]-1} + .... M^{A[i]-1}$$$ .

Now, $$$Answ_{i} = (Answ_{i-1} * M + I) * M^{A[i]-1} $$$

Thanks ,got it .