Invitation to CodeChef Starters 136 (Rated till 6-Stars)

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

We invite you to participate in CodeChef’s Starters136, this Wednesday, 29nd May, rated for till 6-Stars(i.e. for users with rating < 2500).

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

Joining us on the problem setting panel are:

Setters: Shreyan Dominater069 Ray, S. Manuj DarkSparkle Nanthan, thisIsMorningstar, BallBreaker.
Tester: Apoorv tyr0Whiz Kumar.
Text Editorialists:Nishank IceKnight1093 Suresh.
Statement Verifier: Kanhaiya notsoloud1 Mohan.
Contest Admin : Shreyan Dominater069 Ray.

Div1 will have 6 problems. Div2, Div3, Div4 will have 7 problems.

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 only to Pro users.

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. Hope to see you participating.

Good Luck!

UPD : Sorry for the issue in XORNE0.

Top 5 :

Comments (25)

Write comment?

MonoLith

7 months ago, # |

I have submitted a problem idea around 20 days ago how long does it take get a response of rejection or selection of idea

→ Reply

619

-11

Dominater round

_Gawd_

what's the solution for rectangle game

Pirate_King

7 months ago, # ^ |

its a simple nim game with 4 piles

puffinmuffin

Can anyone tell me , why this code is getting TLE? for problem code : LEXMAX

My code

#include<bits/stdc++.h>
using namespace std;

#define int long long


signed main() {
 ios::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 int tt;
 cin >> tt;
 while(tt--) {
  int n;
  cin >> n;
  vector<int>a(n);
  for(auto &i : a) cin >> i;
  sort(a.rbegin(),a.rend());
  vector<int>removed(n,0);
  vector<int>ans;
  int mx = a[0];
  set<int>s;
  for(auto &i : a) {
    s.insert(i);
  }
  while(1) {
    if(ans.size() == n) {
        break;
    }
    if(!ans.empty() && ans.back() == 0) {
        break;
    }
    if(s.find(mx) != s.end()) {
        for(int j = 0 ; j < n ; j++) {
            if(!removed[j] && a[j] == mx) {
                ans.push_back(mx);
                removed[j] = 1;
            }
        }
        s.erase(mx);
    } else {
        int mx = 0;
        int val = 0;
        int id = 0;
        for(int j = 0 ; j < n ; j++) {
            if(!removed[j]) {
                int can = (a[j] & ans.back());
                if(can > mx) {
                    mx = can;
                    val = a[j];
                    id = j;
                }
            }
        }
        removed[id] = 1;
        ans.push_back(mx);
    }
  }
  while(ans.size() < n) {
    ans.push_back(0);
  }
  for(auto &x : ans) cout << x << ' ';
  cout << '\n';
 }
}

alpha1215

← Rev. 2 →

you have to remove all the elements simultaneously that gives max B[i]
suppose B[i — 1] = 5 and max possible B[i] is 5 then you have to remove 3 and 1 in one go
there can be multiple distinct elements which lead to max B[i]

Wow , Thanks :) FML , feels badge

AC CODE

#include<bits/stdc++.h>
using namespace std;



signed main() {
 ios::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 int tt;
 cin >> tt;
 while(tt--) {
  int n;
  cin >> n;
  vector<int>a(n);
  for(auto &i : a) cin >> i;
  sort(a.rbegin(),a.rend());
  vector<int>ans;
  multiset<int>s;
  for(auto &x : a) s.insert(x);
  ans.push_back(a[0]);
  s.erase(s.find(a[0]));
  while(1) {
    if(ans.size() == n) {
        break;
    }
    int val = ans.back();
    if(val == 0) {
        break;
    }
    vector<int>rem;
    /*changed
    for(auto &u : s) {
        if((u & (val)) == val) {
            rem.push_back(u);
        }
    }
    */
    for(auto &u : rem) {
        ans.push_back(val);
        s.erase(s.find(u));
    }
    if(ans.size() == n) {
        break;
    }
    int now = ans.back();
    int mx = 0;
    val = 0;
    for(auto &u : s) {
        int can = (now & (u));
        if(can >= mx) {
            mx = can;
            val = u;
        }
    }
    ans.push_back(mx);
    s.erase(s.find(val));
  }
  while(ans.size() < n) ans.push_back(0);
  for(auto &x : ans) cout << x << ' ';
  cout << '\n';
 }
}

sevlll777

GAMERECT is very similar to this problem 104666D - Crimson Sexy Jalapeños

aryanc403

+15

My post contest discussion stream discussing all the problems

bruce_x001

Problem B video Editorial : (Sum of Modes) YOUTUBE VIDEO LINK --Click Here

Six_Seconds

Thanks for the Editorial. Clearly got the idea.

Thanks ! Glad to hear this.

Bosscoder

Problem C LEXMAX

I got a WA on (third test) task 2 using tries for finding most compatible remaining element 2nd index onwards

https://www.codechef.com/viewsolution/1062347572

Can anyone point a test where it fails ( Codechef premium allows that ) ? Thanks

test case

1 
7
39 3 37 30 4 37 26

correct output

39 37 37 4 4 0 0

your output

39 37 37 4 0 0 0

you can learn about stress testing here

bananasaur

Here's a failing case: 1 7 11. Your solution gives output 11 1 1 while the actual answer is 11 3 1.

The place where the solution goes wrong is in the query function: when curBit is 0, it preferentially traverses to the left child. However, elements of the right child should also be checked.

I'd also attempted using tries initially, but ended up with a simpler approach. Submission

Right right got it, Let me check yours

nice explanation, got ac. But isn't this n^2.log(n)

https://www.codechef.com/viewsolution/1062350047

TyroWhizz

The value of AND changes at most 30 times, so complexity is 30 * N * logN

puspendra_09

Hey sorry to ping you , can you please look at my submission link . My basic idea , sort on the basis of the bit which are not zero.

Tried a couple of small cases, not sure why it fails

Thanks for your time. don't know maybe some tricky corner case

granadierfc

In the rect game problem , It is interpreted as a nim game. Can someone clarify the following doubt "Say I have 2 piles and two players are playing game of nim on it. Now if the first player has a winning strategy on both then as per theorem we know 1st player loses. But say 1st player plays a move such that after his move the state of both piles remains same i.e. both piles still remain in winning state and player 1 might win this way."

MickeyIsAwesome

Is Problem SUMKMAX that easy? How did so many people in Div-2 and Div-3 solve this problem as compared to LEXMAX, which I thought was fairly easy. In Div-1, LEXMAX was solved by almost 3 times more contestants, but in Div-2/3 it is the opposite? Can't understand.

SUMKMAX has a one liner solution using some weird factorials, Not tough to guess that solution was floating in cheating groups.

sahilanand

Thank you so much for this amazing contest! I became 4* coder in this contest!!

Dominater069's blog