CodeDrills Beta Contest #3 [Team Contest] Announcement

№	Пользователь	Рейтинг
1	ecnerwala	3650
2	Benq	3582
3	Geothermal	3570
3	orzdevinwang	3570
5	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3532
8	Radewoosh	3522
9	Um_nik	3483
10	jiangly	3468

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	146
8	orz	146
10	pajenegod	145

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

Contest Link — https://codedrills.io/contests/beta-contest-3
Date & Time — 7 Mar 2021, Sunday, 21:00 IST
Duration — 1.5 Hours
Will follow standard ICPC scoring system (20 minutes penalty and 1 point per problem)

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 taran_1407 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

Комментарии (31)

Написать комментарий?

Vichitr

3 года назад, # |

+19

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

→ Ответить

Reminder: Contest starts in 30 minutes.

Test2311

+50

How to solve "Expected Empty Chess Squares" problem?

3 года назад, # ^ |

← Rev. 2 →

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.

phenomenal_alan

+13

What is the logic behind this?

if(K > 331){ 
    if(K & 1) { 
        K = 331; 
    } else { 
        K = 330; 
    } 
}

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

Into_Your_Arms

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

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.

Makise_Kurisu

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

RonSkk23

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

Can someone share their code for "Relics Collection" ?

Candidate_Master_2021

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

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?

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

i think the judge was a bit slow, even with such low participation. The website looked stable tho.
I was unable to view my teammate code
There was no sample output for Phone and Chargers
If possible label problems with index based on difficulty.

Hi Makise_Kurisu, 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)$$$.

vishaaaal

But editorial is not visible yet.

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

Spoiler

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

Now it's accessible, thanks!!

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

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

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

H4ckOm

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.

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.

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

Yes.

Balajiganapathi

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.

ethicalfacts

how to solve Phone and Chargers ?

can anyone share there code

AC_CODE

#include "bits/stdc++.h"
using namespace std ;
const int mxN=1e5+2 ;
int n,m,x,ans=0,mo[mxN],ch[mxN] ;;
vector<int>adj[mxN] ;
bool vis[mxN] ;
unordered_map<int,int>A,B  ;
void dfs(int v){
  vis[v]=1 ;
  A[mo[v]]++,B[ch[v]]++ ;
  for(int x:adj[v])
    if(!vis[x])
      dfs(x) ;
}
int main(){
  cin >>n>>m >> x  ;
  for(int i=0;i<n;i++)
    cin >> mo[i] >> ch[i] ;
  for(int i=0,a,b;i<m;i++){
    cin >> a >> b ;
    adj[a].push_back(b) ;
    adj[b].push_back(a) ;
  }
  for(int i=0;i<n;i++){
    if(!vis[i]){
      dfs(i) ;
      for(auto x:A){
        if(x.second<=B[x.first])
          continue  ;
        ans+=x.second-B[x.first] ;
      }
      A.clear(),B.clear() ;
    }
  }
  cout<<ans;
}

Code is quite self-explanatory, though feel free to ping me if you don't get anything.

deepa_panwar

Please check the editorial at https://codedrills.io/contests/beta-contest-3/problems/phone-and-chargers. If any quieris feel free to ask on https://discuss.codedrills.io/t/codedrills-beta-contest-3-team-contest-announcement/50/4

Блог пользователя Vichitr