Google Kickstart Round D , Discussion

general
1

Contest : Kick Start - Google’s Coding Competitions

Sol1: XGBZIo - Online C++0x Compiler & Debugging Tool - Ideone.com (AC full)

sol2: wOQYTD - Online C++0x Compiler & Debugging Tool - Ideone.com(AC partial)

sol3:o0u2Wu - Online C++0x Compiler & Debugging Tool - Ideone.com(AC partial)

sol4:9ukSui - Online C++0x Compiler & Debugging Tool - Ideone.com(AC partial)

Discuss all related to this round here .

1 Like
2

People have become really smart these days, I was literally staring at my screen for the first 2 hours. Implementing B was such a pain, any neat implementation for B?

2 Likes
3

oh really brother me too , even C is easier than B for me , first test case

and guess what i submit D before A , B and C :rofl: , I m in top 25 people who submit D earliest

2 Likes
4

lots of edge cases :frowning:

5

rest of them were pretty doable, in fact I got the logic for B within 5-10 mins, but it’s implementation was just too annoying

6

yeah I saw that, it was because of you that I went for D before full C. Thanks XD…

1 Like
7

I faced Memory Limit Exceed(MLE) in problem 2 second test-set(Cutting Intervals).Can anyone tell where can I optimize space?

My code:

#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <list>
#include <deque>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iterator>
using namespace std;

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); 
    cout.tie(NULL);
    long long int t,n,i,a,b,cnt,c,j,ans;
    cin>>t;
    string s;
    for(long long int y=1;y<=t;y++)
    {
        cout<<"Case #"<<y<<": ";
        cin>>n>>c;
        j=0;
        long long check=n;
        ans=0;
        multiset<pair<int,long long int> ,greater<pair<int,long long int>> > v;
        unordered_map<long long int,int>occ;
        while(n--)
        {
            cin>>a>>b;
            for(i=a+1;i<b;i++)
            {
                occ[i]++;
            }
            j++;
        }
        for(auto w:occ)
        {
            v.insert({w.second,w.first});
        }
        for(auto r:v)
        {
            if(c<=0)
            break;
            ans+=occ[r.second];
            c--;
        }
        cout<<ans+check<<"\n";
        occ.clear();
    }
    return 0;
}
8

Maybe this a neat one

2 Likes
9

Thanks!

1 Like
10

Explain logic too

11

Maybe this is neat too -

Code 
'''Author- Akshit Monga'''
from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
    stdout.write("Case #" + str(_ + 1) + ": ")
    hash={}
    n,c=map(int,input().split())
    for i in range(n):
        a,b=map(int,input().split())
        hash[a+1]=hash.get(a+1,0)+1
        hash[b]=hash.get(b,0)-1
    all=sorted(hash)
    l=len(hash)
    pts={}
    start=0
    for i in range(l-1):
        a=all[i]
        b=all[i+1]
        start+=hash[a]
        pts[start]=pts.get(start,0)+b-a
    ans=0
    for i in sorted(pts,reverse=True):
        a=pts[i]
        ans+=i*min(a,c)
        c-=min(a,c)
    print(ans+n)
1 Like
12

In vector we are storing that for each sub-interval what is the no. of given interval passing through it , then we are just using those sub-intervals which pass through maximum no. of interval , Is it ok , or you need more detailed one ?

13

Very neat! I don’t even remember what crap have I written here

1 Like
14

See this

15

so what we have to do is, we have to find the frequency of the first c highest occurring elements in the ranges provided and add them to the number of intervals given?

16

can you please explain this