Biteration #3 Contest Discussion

24

that’s really a nice approach thanks:)

25

Thanks for sharing the approach .

26

for D try dijkstra algorithm.

27

Can you give hint on how to make graph?

28

In case if anyone is interested… Codechef Biteration #3 (unrated) (All solved) - YouTube (My screen recording during the contest)

6 Likes
29

Can anyone please find error in my approach
https://www.codechef.com/viewsolution/34739668
@mkitkat

30

Here is my well commented code for [Problem E] (CodeChef: Practical coding for everyone).I wasn’t sure if it could pass the time limit since constrains were 2000 and I expected its complexity to be O(N^3) but avoiding unnecessary iteration makes it pass.

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int INF=1e18+47;


//find sum of prefix
vector<int> prefix;
int sum(int l,int r){
    return prefix[r]-prefix[l-1];
}


//the given function for a continuous range boils down to finding diffrence of lasT (len/2) elements of that range
//and first len/2 elements of that range 
//NOTE: ceil doesn't affect anything because in case of odd length if we add an element in the left range and right range it'll just cancel out
//and the question also says to neglect middle element in case the len of continuous taken segment is odd
int ans_for_segment(int ending_at,int len){
    int starting_at=ending_at-len+1;
    int l=ceil(1.0*len/2);
    // cout<<"("<<ending_at-l+1<<","<<ending_at<<") - ("<<starting_at<<","<<starting_at+l-1<<")\n";
    return sum(ending_at-l+1,ending_at)-sum(starting_at,starting_at+l-1);
}

int32_t main(){
    FAST
    int t;cin>>t;
    while(t--){
        prefix.clear();
        int n,k;cin>>n>>k;
        vector<int> a(n+1);
        for(int i=1;i<=n;i++)cin>>a[i];
        prefix.push_back(0);
        for(int i=1;i<=n;i++) prefix.push_back(prefix.back()+a[i]);              
        
        //all the values are initiallf INF
        vector<vector<int>> dp(k,vector<int>(n+1,INF));  //dp[i][j] in minimum cost for settling first j gifts in first i boxes;
        // NOTE: INDEXING OF BOXES IS FROM 0 to k-1 
        
        //initializing base dp
        for(int j=1;j<=n;j++){
            dp[0][j]=ans_for_segment(j,j); //Here j is length of continuous segment taken as well, because nothing is used previously
        }

        //iterating over boxes
        for(int i=1;i<k;i++){
            //iterating over number of gifts taken upto this box including this box
            //here i+1 is used because previous boxes must accomodate i gifts atleast 1 gift each
            for(int j=i+1;j<=n;j++){
                //we iterate over all possible lengths of continuous segment that can be taken in current box to have j taken gifts in ith box
                for(int len=1;len<=j-i;len++){
                    // cout<<"dp["<<i<<"]["<<j<<"]="<<(dp[i-1][j-len]==INF?"INF":to_string(dp[i-1][j-len]))<<"+"<<ans_for_segment(j,len)<<"\n";
                    dp[i][j]=min(dp[i][j],dp[i-1][j-len]+ans_for_segment(j,len));
                }
            }
        }

        // for(int i=0;i<k;i++) {for(int j=0;j<=n;j++)cout<<(dp[i][j]==INF?"INF":to_string(dp[i][j]))<<" ";cout<<"\n";}
        cout<<dp[k-1][n]<<"\n";
    }
    return 0;
}
1 Like
31

Please somebody explain problem Smallest String.

32

Was this contest rated?

33

Your logic in the code is correct
It will run on all the test case

I guess time limit is exceeding in your code,
just try to reduce looping the code,

34

case : (L>1)
eg. 2 navy
bring n to last : avyn
bring v to last : aynv
bring y to last : anvy
observe that in the final answer all alphabet are in order as in a-z sequence
ALGO
count the occurence of all alphabet in the given string
output all the alphabet(as many times as they occur in the string) in sequence a-z

35

No bro

1 Like
36

Easy to understand code :
link to my solution B:
https://www.codechef.com/viewsolution/34735682
link to my solution C:
https://www.codechef.com/viewsolution/34743006
link to my solution D:
https://www.codechef.com/viewsolution/34742383

if any doubt in my code you can ask me :smiley:

37

for case L==1?

38

Can you please look at my solution for D and tell where is the error , CodeChef: Practical coding for everyone

39

@ayush_nishad

40

as in your code
adj[i].push_back({i+1,x});
you should also make an edge fro i+1 to i as it is undirected.
and there iin no need of adj[n-1].push_back({P[n-1]-1,C[n-1]});
as we dont need to go to other node from last node.

41

cyclically permute the string
e.g. L=1 apac(string)
Now start cyclic shift paca
acap
capa
answer is the lexicographically smallest string i.e. acap

bonus Observation : answer is always that string in which the 1st character is the smallest char(that appears first in sequence a-z) in the whole string

so we are left with only 2 strings :-
acap, apac (since ‘a’ is char in the string which appears first in sequence a-z)

Now we can compare these 2 strings to get desired answer

for more clarity please consider looking this solution, it has comments as well