Simply we should select maximum number and we should print:
value (number_of_value / n). If we select all (values) we can reach maximum possibility
code by Halit
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d", &n);
int arr[n+1];
for(int i = 1;i <= n;i++)
scanf("%d", arr + i);
map<int, int> h;
int maxim = -1;
for(int i = 1;i <= n;i++){
maxim = max(arr[i], maxim);
h[arr[i]]++;
}
printf("%d %.2f", maxim , (double)h[maxim]/n);
}
B-)Find the missed number(author Halit)
So, Simply we should assign leaf nodes to 2 and multiply it with other children, do it step by step, because leaf node should be minimum number that greater than 1.
code by AhmetKaan
//Bismillahirrahmanirrahim
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
#define se second
#define mp make_pair
#define int long long
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000000;
int n,m,b[li],a[li],k,flag,t,dp[li];
int cev;
string s;
vector<int> v[li];
inline int mul(int x,int y){
return (x%mod)*(y%mod)%mod;
}
inline void dfs(int node,int ata){
dp[node]=1;
for(int i=0;i<(int)v[node].size();i++){
int go=v[node][i];
if(go==ata)continue;
dfs(go,node);
dp[node]=mul(dp[node],dp[go]);
}
if(dp[node]==1)dp[node]=2;
}
main(void){
scanf("%lld",&n);
for(int i=1;i<n;i++){
int x,y;
scanf("%lld %lld",&x,&y);
v[x].pb(y);
}
dfs(1,0);
FOR printf("%lld ",dp[i]);
return 0;
}
C-)Help for Contest(author AhmetKaan)
In this problem you will erase some letters. So when you found a subsequence with lenght k you will erase it.You will do at most (string size) erasing. If you do the erasings in string string.erase is working too slow and you need to do with another way. I did it with set. set.erase is working at log2(n) so mine solution is O(N log(N)). I think that there is a solution which works in O(N)(with stack or another thing) but mine solution is working in O(N logN)
code by AhmetKaan
//Bismillahirrahmanirrahim
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 200005;
const lo mod = 1000000007;
int n,m,k,flag,t,d[li];
int cev;
set<int> st;
string s;
int main(void){
fio();
cin>>n>>k>>s;
for(int i=0;i<n;i++)st.insert(i);
int say=1;
d[0]=1;
auto it=st.begin();
it++;
for(;it!=st.end();it++){
int i=*it;
auto it1=it;
it1--;
int i1=*it1;
if(s[i]==s[i1])say++;
else say=1;
if(s[i]==s[i1])d[i]=d[i1]+1;
else d[i]=1;
if(d[i]>=k){
say=k;
auto it2=it;
it2++;
while(say>1){say--;it--;}
it1=it;
it=it2;
it++;
say=k;
if(it1!=st.begin())it--;
st.erase(it1,it2);
//~ cout<<*it<<endl;
while(say>0){
//~ it=st.find()
//~ cout<<*it<<endl;
d[i-k+1+say-1]=1;
say--;
}
n-=k;
i-=k;
it--;
}
}
int tut=0;
int at=0;
for(auto it=st.begin();it!=st.end();it++){
if(tut>=k)break;
tut++;
if(s[*it]==s[*st.begin()])at++;
}
if(at==k){
tut=0;
for(auto it=st.begin();it!=st.end();it++){
if(tut>=k)break;
tut++;
st.erase(it);
}
}
it=st.begin();
for(;it!=st.end();it++){
cout<<s[*it];
}
return 0;
}
D-) Smart Move(author farukkastamonuda)
D) Smart Move This question can solve with dynamic programming. Dp parameters are index of current item, remaining right, number of selected elements odd or even, number of selected elements modulo 3. Last two of them seen unnecessary, however these parameters help much in real solution. Naive Solution(O(N*K*K)) We can find the solution in O(N*K*K). For all k from k to 1 we calculate new dp array in O(N*K). If we use parameters as explain in top for all k we can find in O(N*K). We can solve like knapsack problem. Either we select this element or not. Original Solution(O(N*K*2*3)) As seen in the naive solution we are calculating same case lots of time. For reduce the time complexity firstly we can calculate the case which we have K right. Then we need to find the case which we have K-1 right. How we can pass it? In my solution I start my selected number as 0 and in the function if my selected number is much than k (if my selected number>k) I finish. With a smart move I start my selected number as 1 and I don’t change stopping condition(if my selected number>k) in recursion. For K-2 right, I start my selected number as 2 and it goes like this. So with this smart move we don’t calculate same case and we calculate maximum N*K case since complexity is O(N*K*2*3).
code by farukkastamonuda
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define inf 1000000000000000000
#define md 1000000007
#define pb push_back
#define li 2005
#define int long long
using namespace std;
int n,A[li],k,dp[li][li][3][2];
int dfs(int node,int hak,int flag1,int flag2){
int cev=-inf;
if(hak>k) return -inf;
if(node==n+1) return 0;
if(~dp[node][hak][flag1][flag2]) return dp[node][hak][flag1][flag2];
cev=max(cev,dfs(node+1,hak,flag1,flag2));
cev=max(cev,dfs(node+1,hak+1,(flag1+1)%3,(flag2+1)%2)+A[node]*((flag1+1)%3)*((flag2+1)%2==1?-1:1));
return dp[node][hak][flag1][flag2]=cev;
}
void solve(){
memset(dp,-1,sizeof(dp));
scanf("%lld %lld",&n,&k);
for(int i=1;i<=n;i++) scanf("%lld",&A[i]);
for(int i=k;i>=1;i--){
int cikar=k-i;
int ty=dfs(1,cikar,0,0);
printf("%lld ",ty);
}
printf("\n");
}
int32_t main(){
solve();
return 0;
}
E-) Infairness In Sugar Distribution(author farukkastamonuda)
Sorry for time limit mistakes but if we didn’t change the time limit then question would wasted. Thank you for participating. It can be seen that ans(i+1)>=ans(i) because max and min number in ans(i) also in ans(i+1) and thanks to growth of interval there can be any other min or max value since ans(i+1)>=ans(i). After this observation divide and conquer comes to mind. First send (1,n) interval to the divide and conquer. Then find the mid value of interval with naïve solution. Then divide the interval into two parts. (l,mid-1) and (mid+1,r). Max result of left part is result[mid] and min result of right part is result[mid]. But this is already O(logn*logn- >> divide and conquer part). So we need to find naive solution in O(n). In naive solution I traverse array one by one. Firstly look (1,k) then (2,k+1), (3,k+2)…. (n-k+1,n) But for each step I need to find result in O(1). Find maximum and minimum number in this interval in O(1). This can be done with sparse table. We firstly build sparse table in O(Nlogn) time and then calculate all queries in O(1). Solution has O(N*logN*log(10^9)) complexity. Because in divide and conquer we use 4 parameter(l,r,optl,optr). And interval length of (optl,optr) is 10^9.
code by farukkastamonuda
#include <bits/stdc++.h>
using namespace std;
#define mid (l+r)/2
#define mid2 (start+end)/2
#define inf 1000000000
#define li 37000
#define mp make_pair
#define fi first
#define se second
#define lo long long
int n,A[li],dp[li],say,vis[li],lookup[li][30],lookup2[li][30];
pair<int,int> tree[li*4];
void buildminSparseTable(int n)
{
for (int i = 1; i <= n; i++)
lookup[i][0] = A[i];
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 1; (i + (1 << j) - 1) <= n; i++)
{
if (lookup[i][j - 1] < lookup[i + (1 << (j - 1))][j - 1])
lookup[i][j] = lookup[i][j - 1];
else
lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1];
}
}
}
int querymin(int L, int R)
{
int j = (int)log2(R - L + 1);
if (lookup[L][j] <= lookup[R - (1 << j) + 1][j])
return lookup[L][j];
else
return lookup[R - (1 << j) + 1][j];
}
void buildmaxSparseTable(int n)
{
for (int i = 1; i <= n; i++)
lookup2[i][0] = A[i];
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 1; (i + (1 << j) - 1) <= n; i++)
{
if (lookup2[i][j - 1] > lookup2[i + (1 << (j - 1))][j - 1])
lookup2[i][j] = lookup2[i][j - 1];
else
lookup2[i][j] = lookup2[i + (1 << (j - 1))][j - 1];
}
}
}
int querymax(int L, int R)
{
int j = (int)log2(R - L + 1);
if (lookup2[L][j] >= lookup2[R - (1 << j) + 1][j])
return lookup2[L][j];
else
return lookup2[R - (1 << j) + 1][j];
}
int naive(int val){
say++;
int cev=0;
for(int i=val;i<=n;i++){
int basla=i-val+1;
cev=max(cev,querymax(basla,i)-querymin(basla,i));
}
return cev;
}
void solve(int l,int r,int optl,int optr){
if(l>r) return ;
if(optl==optr || vis[mid]==1){
if(vis[mid]==0)
dp[mid]=optl;
vis[mid]=1;
}
else {dp[mid]=naive(mid);vis[mid]=1;}
solve(l,mid-1,optl,dp[mid]),solve(mid+1,r,dp[mid],optr);
}
void general(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&A[i]);
buildmaxSparseTable(n);
buildminSparseTable(n);
solve(1,n,0,inf);
for(int i=1;i<=n;i++) printf("%d ",dp[i]);
printf("\n");
}
int main(){
general();
return 0;
}
I've hacked the official solution for E (in custom invocation at least, run in >15000ms) with the following test:
35000
1 2 3 ... 35000.
The runtime of the algorithm is actually O(n2) with bad constant, not O(n log n log MAX). And if you do not understand how the optimization in the official solution works, it can be easy to make this mistake.
Here is the solution for question C using stack with O(n) Time Complexity,
Good job. implementation with stack is easier than implementation with set. Thank you for your sharing.
Hi, for D i have a solution which runs in O(N*K) time and O(N+K) space
I compared my code with your solution and it runs in (66 ms / 1153 ms, 3700KB / 193000 KB). I enjoyed the problems, but it was hard for me to understand the statements.
Thank you! Statements are not clear enough.
Can someone explain the optimization part of problem D?? I came up with the n*k*k solution during the contest which is the same as editorial but could not optimize it and even after reading the editorial, I am not able to understand completely.
if(hak>k) return -inf; I didn't change this if. And with this: int cikar=k-i; int ty=dfs(1,cikar,0,0); Firstly cikar means that how many element you select until now. Firstly cikar=0 then for K-1 case you set cikar to 1 and since it means that you are seen like take 1 element and if(hak>k) return -inf means that you can select at most k-1 elements now and you don't fill the dp array try and try.
I use recursion dp in this question. When you use recursivic dp ans_k = f(1,0,0,0)
then if you dont clear the dp array and get the walue of f(1,1,0,0) then ans_k-1 = this
and you can do at most n*k*2*3 operation at most.
Okay so we just didn't have to clear the dp table each time. Thank you, it was indeed a smart move.
Stack Solution works in O(n) in problem C.