shivamg_isc's blog

Invitation to CodeRed- 2019 by IIIT Allahabad
By shivamg_isc, history, 6 years ago, In English

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 (dbest077), 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

  1. farhodkerimtemurbek — Kerim.K, Farhod
  2. 1e9+7 Bugs Per Second — Ashishgup, Slow_But_Determined, vntshh
  3. PaduKeDeewane — hitman623, Enigma27, _shanky
  4. Ryuzaki — Hiren.Vaghela, Learner99
  5. 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.

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

Comments Comments (48)
| Write comment?
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

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

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

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

    I talked to the organisers just now. The participants now do not need to be from the same institution/organisation. :)

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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(n3log(1018) * 100000) which would have TLEd?

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

    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.

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

      Isn't the initial matrix to be formed is of size 44 × 44 or I am missing something?

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

        The initial matrix size can be reduced to 43 * 43.
        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 =  = l and k =  = 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

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

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?

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

    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)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +9 Vote: I do not like it

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

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

        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.

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

    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.

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

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

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

    Ah, that explains my deja vu.

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

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

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

    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.

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

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

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the intended solution for CR192?

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Please make the problems available for practice.

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

A very good contest, really enjoyed solving the problems.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it 
    1    
1   
7   
4   
4 8

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

    → Reply
»
6 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Amazing contest with over 1200 teams participating...!!
A well balanced contest...
Kudos to the problem setters..!!

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve CR197?

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

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    This worked for me.

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

    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.

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

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

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Editorial?

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

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

When will we get list of the shortlisted teams?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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} $$$

    → Reply