Vichitr's blog

By Vichitr, 7 weeks ago, In English

Hello Codeforces!
CodeDrills will be hosting its first team contest CodeDrills Beta Contest #3 on Sunday, 7th March, 2021 9:00 PM — 10:30 PM IST. There will be 4 or 5 problems to be solved in 1.5 hours.

Contest Details

Registration
You will need to create a team on the contest page in order to participate. Team size can be upto 3. While creating the team, add the registered emails of other users to invite them to join your team. They will get an invite email, ask them to accept. For more details on team registration, refer this guide.

I hope you will enjoy solving the problems.
Hope to see you participating!!!

Thanks everyone for participating. Editorials are out for all the problems. Solutions wont be visible if you are not logged in.

Congratulations to the winners!
1. Unbreakable — Nishant nishant403 Shah, Taranpreet Discombobulated Singh
2. Onyan — Nishank IceKnight1093 Suresh
3. TodoMihnator — Alexandru atodo Todoran

Note:
For practice, users are not able to submit the solutions on contest page, we will fix it.
All problems after the contest will be added to competitive section — https://codedrills.io/competitive. So you can still submit from here.
Attaching all problem links for practice -
1. https://codedrills.io/problems/new-virus-spread
2. https://codedrills.io/problems/stack-of-boxes
3. https://codedrills.io/problems/relics-collection
4. https://codedrills.io/problems/phone-and-chargers
5. https://codedrills.io/problems/expected-empty-chess-squares

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

»
6 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Reminder to register for the contest! You wont be able to register after the contest starts hence please register before 9 PM IST.

»
6 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Reminder: Contest starts in 30 minutes.

»
6 weeks ago, # |
  Vote: I like it +50 Vote: I do not like it

How to solve "Expected Empty Chess Squares" problem?

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hi, this was just an extension of this problem — https://cses.fi/problemset/task/1726/ There was some issue with test data. I have fixed test data for now. Expected a matrix expo to pass. Our TL was too tight. I have increased it for now to pass matrix expo solutions.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      What is the logic behind this?

      if(K > 331){ 
          if(K & 1) { 
              K = 331; 
          } else { 
              K = 330; 
          } 
      }
      
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Simulation! Author tried simulating with increasing $$$k$$$ values for same $$$n$$$ and found out that, after a bound, expected value doesn't change.

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

          Hi, Can you allow other participants to submit the code just for practice?

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

            Problems are now public. You can submit your solution on contest page. If that's not working then search the problem under competitive section and you should be able to submit your solution.

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Can you please release the editorials or make the submissions public?

»
6 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

In Expected Empty chess squares, would O((N*N)^3logK) pass TL ?

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone share their code for "Relics Collection" ?

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    It's DP

    For each idx, you can jump from a[idx] to anywhere between a[idx+k] which is max 50 interation.

    and let dp[i][k] = minimum time if u start at i and have k jumps left

    overall solution works in $$$O(N*K*K)$$$

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

      Yes, I did the same but got a WA so just wanted to stress-test my solution against an AC code, would you mind sharing it?

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Sure, but it looks like i am unable to see my solution for some reason.. :(

        i can't even see scoreboard.

        Talking about the experience

        1. i think the judge was a bit slow, even with such low participation. The website looked stable tho.

        2. I was unable to view my teammate code

        3. There was no sample output for Phone and Chargers

        4. If possible label problems with index based on difficulty.

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

        Hi fireblaze777, editorial have the setter iterative $$$O(n*k*k)$$$ solution. And in tester solutions, i have added my 3 solutions, $$$O(n*k*k)$$$ both iterative & recursive dp. Also $$$O(n*n*k)$$$ recursive dp. We intended to pass only $$$O(n*k*k)$$$.

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

          But editorial is not visible yet.

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

          Thanks for replying but for some reason I'm not able to access the editorial as of now.

          Spoiler
          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
            Rev. 2   Vote: I like it +3 Vote: I do not like it

            Oh seems weird! I've added the solution without solution tag. Now it should be visible at the end of editorial.

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

      But we always start from $$$(0,0)$$$, so how is this DP state correct?

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

        add (0,0) to the list of coordinates in front

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

          That means, our answer is dp[0][k]?

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

            answer is minimum cost to reach till end, if you doing it with recursion the recursive function itself will return the answer.

            so it will $$$min(dp[0][0],dp[0][1],.......dp[0][k])$$$ where you are jumping from $$$0$$$-th position to somewhere with some $$$x(<=k)$$$ skips.

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

              But, if our state is minimum time required if we start from $$$i^{th}$$$ position with $$$k$$$ skips left, the answer has to be $$$dp[0][k]$$$.

              I tried the same and got Correct Answer later.

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

                then in that case you must be updating dp values with the previous one, isn't it?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

We have rejudged "Expected Empty Chess Squares" problem as it had some test issues and 1 wrong submission has now got accepted. Apologies for the mistake.

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

how to solve Phone and Chargers ?