June lunch time discussion

See mine :rofl: :rofl:

1 Like

Does bruteforce solution works for question 3 in div2?

I am sure I could have just guessed that… : P
But I dont know why It works.

1 Like

also introducing an adhoc problem in division 1 makes no fucking sense :dizzy_face:

2 Likes

Totaly agree

Hey here’s my solution:

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <bitset>
#include <iomanip>
#include <assert.h>
#include <numeric>
using namespace std;
using ll = long long;
#define endl '\n'
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) 
{
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define FAST_IO ios::sync_with_stdio(0); std::cin.tie(0);
#define bp(x) __builtin_popcount(x)
#define zf(x) __builtin_clz(x)
#define zl(x) __builtin_ctz(x)
#define par(x) __bultin_parity(x)
#define all(x) (x).begin(), (x).end()
/* **************************************************************************************** */

void test_case()
{
	FAST_IO
    ll n, k, x = 0;
    cin >> n >> k;
    vector <ll> a(n);
    for(ll &x : a) cin >> x;
    vector <ll> m(34);
    
    for(ll x : a)
    {
        for(int i = 33; i >= 0; --i)
        {
            if(x & (1LL << i))
                m[i]++;
        }
    }

    for(int i = 0; i < m.size(); i ++)
    {
        m[i] = (1LL << i) * m[i];
    }

    while(k--)
    {
        ll mi = 0;
        for(int i = 1; i < m.size(); i ++)
        {
            if(m[i] > m[mi])
            {
                mi = i;
            }
        }
        m[mi] = -1;
        x |= (1LL << mi);
    }

    cout << x << endl;
	return ;
}
int main()
{
	FAST_IO
    int t;
    cin >> t;
    while(t--)
        test_case();
	return 0;
}

Find set bits and then greedily choose the bit which gives you maximum value untill k is exhausted.

Is hating codechef become a trend ? : P
I think problems were not that bad.

4 Likes

I checked your solution and failed to find any difference between yours and mine. Could you please point it out? won’t take long coz approach is same.
https://www.codechef.com/viewsolution/34807341

Ya and time by time situations are getting worse everyday , now I seriously have left any hopes in Codechef contests.

Can u explain this part

it’s basically multiplying the frequency in m[i] by the power of 2. that is, pow(2,i)*m[i]
this way we calculate the contribution of that set bit to the final sum.

1 Like

Let’s say you want to compute value 2nd bit (which will give you value 2^2 = 4 ) will give if you select it . Now let’s say k numbers in the array had 2nd bit set (i.e equal to 1). So Selecting 2nd bit will give you value = k * (2 ^ 2).

Similarly I compute value of each bit by multiplying it’s frequency and it’s value.

I hope you understood.

1 Like

Never mind, got it. “1” and “1LL”. FML

For Increasing Decreasing question
My Python Code

def fun():
    n=int(input())
    l=[int(i) for i in input().split()]
    l=sorted(l)
    d={i:l.count(i) for i in l}
    for x in d:
        if(d[x]>=3):
            print("NO")
            return 0
    if(d[l[-1]]>1):
        print("NO")
        return 0
    else:
        #l=sorted(l)
        print("YES")
        l1=[l[i] for i in range(0,n,2)]
        l2=[l[i] for i in range(1,n,2)][::-1]
        #l2=n//2
        print(*l1,*l2)

for _ in range(int(input())):
    fun()
        
    

My CPP Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define inf 10e7
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define print(a,n) for(ll i=0;i<n;i++){cout<<a[i]<<" ";}cout<<"\n";
#define init0(a,n) for(ll i=0;i<n;i++){a[i]=0;}


void solve(){
   ll n;
   cin>>n;
   ll a[n];
   ll cnt[200001];
   init0(cnt,2e5+1);
   for(ll i=0;i<n;i++){
      cin>>a[i];
      cnt[a[i]]+=1;
   }
   for(ll i=0;i<200001;i++){
      if(cnt[i]>2){
         cout<<"NO\n";
         return;
      }
   }
   sort(a,a+n);
   if(cnt[a[n-1]]>1){
      cout<<"NO\n";
      return;
   }
   cout<<"YES\n";
   vector<ll> v1,v2;
   for(ll i=0;i<n;i+=2){
      v1.push_back(a[i]);
   }
   for(ll i=1;i<n;i+=2){
      v2.push_back(a[i]);
   }
   for(ll i=0;i<v1.size();i++){
      cout<<v1[i]<<" ";
   }
   for(ll i=v2.size()-1;i>=0;i--){
      cout<<v2[i]<<" ";
   }
   cout<<"\n";

  
   




}


int main()
{
    fastio
    ll t;
    t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
    

}

I got Partial with Python and Full with CPP, I had to waste time writing same code in diff language even though logic is same, it’s demotivating for Python Coders.

thanks buddy

I think u r using 1<<i instead of 1LL<< i

Can somebody please help
Thanks!

@vipulks Can you please share your submission?

I don’t think quality of problems is so poor , of course there are so many great problems(most of long challenges). Sometimes it may happen that the problems haven’t reached their difficulty level or strict time limit .Its hard luck.

1 Like

Here you go.