Invitation to HackerEarth's June Easy '20

→ Обратите внимание

До соревнования
Codeforces Round 995 (Div. 3)
33:33:48
Зарегистрироваться »

→ Трансляции

Codeforces Round 995 Solution Discussion

aryanc403

До начала 35:53:47

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
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

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
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

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Invitation to HackerEarth's June Easy '20

Автор nikesh04, история, 5 лет назад, По-английски

Hello Everyone!

I would like to invite you to participate in HackerEarth's June Easy '20. It will be held on Saturday, June 06 at 12:00 — CDT.

I (nikesh04), vivaan_gupta, Finding_Infinity, spar5h, and Kritagya Agarwal are the setters of this round, and Arpa is the tester of the problems.

You will be given 6 algorithmic questions to solve in 3 hours. Partial scoring will be used (you get points for passing each test case). Although the contest is targeted towards beginners, we hope that everyone finds the tasks interesting. The contest is rated for all and the prizes will be awarded to the top 3 beginners (i.e. programmers with a rating of 1600 or less before the challenge starts):

First place: $75 Amazon gift card.

Second place: $50 Amazon gift card.

Third place: $25 Amazon gift card.

Good luck to everyone, and I hope you like the contest!

#hackerearth, june easy, 2020

nikesh04
5 лет назад
21

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

Показать архивные | Написать комментарий?

living_in_genjutsu

5 лет назад, # |

+15

contest is not loading 502 gateway error:(

→ Ответить

Chocobar

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

← Rev. 2 →

Hint for last problem ?probably greedy with taking mid does not work

→ Ответить

chandanagrawal23

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

← Rev. 2 →

Please share approach for "Arrays and Sum" , I solved 4 questions and this one partial .

→ Ответить

Too_stupid

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

I do not know how but subset-sum did the work for me. According to the constraints I should have got partial points.

→ Ответить

chandanagrawal23

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

Can u please share your code ... and it will be more helpful if anyone share most optimized approach for this question

→ Ответить

Too_stupid

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

Code

#include <bits/stdc++.h>
#define ll long long int
#define pll pair <ll,ll>
 
using namespace std;
 
inline bool cool(ll set[], ll n, ll sum) 
{
    bool subset[n + 1][sum + 1]; 
    for (ll i = 0; i <= n; i++) 
        subset[i][0] = true; 
    for (ll i = 1; i <= sum; i++) 
        subset[0][i] = false; 
    for (ll i = 1; i <= n; i++) 
    { 
        for (ll j = 1; j <= sum; j++) 
        { 
            if (j < set[i - 1]) 
                subset[i][j] = subset[i - 1][j]; 
            if (j >= set[i - 1]) 
                subset[i][j] = subset[i - 1][j] || subset[i - 1][j - set[i - 1]]; 
        } 
    }
    return subset[n][sum]; 
} 
int main()
{
    ll t;
    cin >> t;
    while(t--)
    {
        ll n;
        cin >> n;
        ll ar[n];
        for(ll i = 0; i < n; i++)
            cin >> ar[i];
        for(ll i = 0; i < n; i++)
        {
            ll fuck[n - 1];
            ll idx = 0;
            fill(fuck, fuck + n - 1, false);
            for(ll j = 0; j < n; j++)
            {
                if(i != j)
                {
                    fuck[idx] = ar[j];
                    idx++;
                }
            }
	    if(cool(fuck, n - 1, ar[i]))
                cout << 1 << " ";
            else
                cout << 0 << " ";
        }
        cout << endl;
    }
    return 0;
}

→ Ответить

aryanc403

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

My in contest soln was similar just that it used bitsets for a /32 constant factor.
I assumed it to be O(N*1000/32). After reading your comments I realized it was O(N*1000*1000/32).

→ Ответить

darkworld1

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

just do knapsack, and if u can make the sum looking more than 1 time than there is another subset that can make this sum. corner case is zero (ignore it).

→ Ответить

chandanagrawal23

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

What's your complexity N³ ?

→ Ответить

darkworld1

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

o(n^2)

→ Ответить

chandanagrawal23

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

Please share your code .

→ Ответить

darkworld1

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

← Rev. 2 →

void solve(){
   int n ; 
   cin >> n ; 
   vector < int > a(n) ;
   for( int i = 0 ; i < n ; i++) cin >> a[i] ;
   vector < vector < int > > dp(n,vector<int>(1001));
   dp[0][0] = 1 ;
   dp[0][a[0]] = 1 ;
   for( int i = 1 ; i < n ; i++){
       for( int j = 0 ; j < 1001 ; j++){
           dp[i][j] = dp[i-1][j] ;
           if(j>=a[i] && a[i]!=0){
               dp[i][j] += dp[i-1][j-a[i]];
               if(dp[i][j]>2) dp[i][j] = 2 ;
           }
       }
   }
   vector < int > ans(n);
   for( int i = 0 ; i < n ; i++){
       if(dp[n-1][a[i]]==2 || a[i]==0){
           cout << "1 " ;
       }
       else{
           cout << "0 ";
       }
   }
   cout << "\n";
}

→ Ответить

Eunoia__1729

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

← Rev. 2 →

You can store the number of ways to get a sum of x by in dp[x]. Thus, if the number of ways is greater than 1, then there exists a subset with equal sum. One implementation detail to take care of is to ignore 0 valued elements and set dp[0] to 1 initially as sum of empty set is 0.

Spoiler

#include <bits/stdc++.h>
#define rep(i,a,b) for (i=a;i<b;i++)
#define rep2(i,a,b) for (i=a;i>=b;i--)
#define endl '\n'
#define ll long long
#define vll vector < ll >
#define pb push_back
#define mk make_pair
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
using namespace std;
int main()
{
    ll t, n, m, q, maxx,  i, j, k, x, y, flag, sum, cnt, ans, minn, cur;
    cin>>t;
    while(t--)
    {
        cin>>n;
        vll v(n);
        vll res(n, 0);
        rep(i,0,n)
            cin>>v[i];
            
        vll dp(1001, 0);
        dp[0] = 1;
        rep(i,0, n)
        {
            if( v[i] == 0)
                continue;
            rep2(j,1000,v[i])
                if( dp[j - v[i]] > 0)
                    dp[j]++;  
        }
        dp[0] = INF;
        rep(i,0,n)
            cout<<( dp[v[i]] > 1) <<" ";
        cout<<endl;
    }
    return 0;
}

→ Ответить