Corona Effect

4 years ago, # ^ |

-43

How many people scored 100/100?

→ Reply

aditya_sheth

4 years ago, # ^ |

More than 500 as of now.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

-127

Can anyone provide code for last two XD. I need it urgently.

Please Downvote it if you would proivde the code.

→ Reply

dunjen_master

4 years ago, # ^ |

+15

my solution

→ Reply

4 years ago, # ^ |

+26

Code 1:

Code 2:

I did my part and downvoted.

→ Reply

4 years ago, # ^ |

-56

Provide a working code if you have

→ Reply

4 years ago, # ^ |

+24

It worked for me ¯_(ツ)_/¯

→ Reply

4 years ago, # ^ |

+13

Especially the second one.

It's short and nice.

→ Reply

zjj1149

4 years ago, # ^ |

-18

I feel the third is hardest, I use dp and get TLE for test 2

→ Reply

4 years ago, # ^ |

in 3rd, u need beinary search. check whether we can make x as our answer. we can make x as our answer only when sum of all (a[i+1] — a[i]) / x , for i = 1 , n — 1 is <= k.

→ Reply

bryceShakeair

4 years ago, # ^ |

s there any category , you would put this problem to ?

→ Reply

Ausmosian

4 years ago, # ^ |

It can also be done by simple greedy, just pick the largest gap, decrease the gap, repeat for k times. O(klogn).

→ Reply

socho

4 years ago, # ^ |

Hey!

I'm not sure that this always works, for example, given a case where the optimal solution involves splitting up some difficulty gap twice (one input gap into thirds), but this solution would first split it into halves and split one half into two quarters.

Here's a case:

N = 2
K = 2
M = [1, 19]

Here, the optimal solution would be to use two splits between 1 and 19, making [1, 7, 13, 19] so the answer is 6. However repeatedly picking the largest gap and splitting it into half, would give you:

[1, 19] => split into [1, 10, 19] for the first step,

Now the largest gap is [1, 10] (or [10, 19]), which you could split into [1, 5, 10]. This approach gives 9 as the answer (because [10, 19] still hasn't been split), but 6 is possible, as we showed above.

Thanks!

→ Reply

Ausmosian

4 years ago, # ^ |

No, I meant equally distribute the gap, like fo the first time you visit this gap {1,19} divide it in two parts (thus {1,10,19}) now when you visit the same gap again split it into 3 parts(thus {1,7,13,19}), and so on k times. I implemented it like @Spheniscine 's comment down below.

→ Reply

--oldaccount--

4 years ago, # ^ |

+18

2nd was def tougher than 1200

→ Reply

Bhj2001

4 years ago, # |

+63

Speedforces

→ Reply

4 years ago, # ^ |

-53

send your code with speed right now.

→ Reply

Bhj2001

4 years ago, # ^ |

+21

I used _dobby_'s code

→ Reply

4 years ago, # ^ |

I really hope you changed the code, I don't want to get caught in plagiarism.

XDD

→ Reply

4 years ago, # ^ |

Speedstart to be precise.

→ Reply

rr459595

4 years ago, # |

Why priorityqueue based greedy solution giving WA on large test case of problem 3?

→ Reply

4 years ago, # ^ |

If you are just taking biggest gap and dividing it into two, that won't work. Consider the case:

1
2 2
1 10

The optimal solution is 1 4 7 10 with a penalty of 3, but the divide-by-two solution would produce something like 1 5 7 10 with a penalty of 4.

→ Reply

4 years ago, # ^ |

I too wrote the solution using priority queue and got 3 WA. Later used binary search.

→ Reply

4 years ago, # ^ |

+10

I actually used priority queue, but rather than storing only the gap, I store both the initial gap and the number of insertions, and greedily add insertions to the entries with the biggest current gap, i.e. $$$\left\lceil \dfrac {gap_0} {insertions + 1} \right\rceil $$$

→ Reply

mdazmat9

4 years ago, # ^ |

yeah i did the same ,Having original value is important

→ Reply

ritik_patel05

4 years ago, # ^ |

Wow, that's smart way.

→ Reply

4 years ago, # ^ |

Can you kindly post your solution?

→ Reply

4 years ago, # ^ |

https://pastebin.com/mqtmKYpd (Kotlin)

It's slightly different from how I described it, as I store the divisor ($$$s = insertions + 1$$$) instead of the number of insertions directly

→ Reply

fraj

4 years ago, # ^ |

Is there a mathematical formula/concept behind that expression? I fail to see why that works.

→ Reply

4 years ago, # ^ |

← Rev. 3 →

Each entry represents the gap between a pair of consecutive numbers in the input (so $$$gap_0 = M_{i+1} - M_{i}$$$ for the $$$i$$$th entry). $$$insertions$$$ are the number of new exercises you plan to put within that gap.

So say you plan to put $$$3$$$ insertions between $$$2$$$ and $$$11$$$. It can be seen that it's optimal to space them out as evenly as possible (e.g. 2 4 6 8 11), and the largest gap remaining in that segment is $$$\left\lceil \dfrac {11-2} {3 + 1} \right\rceil = 3$$$.

→ Reply

rr459595

4 years ago, # ^ |

Ahh, Thanks.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

I solved it using the priority queue.

My code.

→ Reply

rr459595

4 years ago, # ^ |

Ok,thanks.

→ Reply

tmwilliamlin168

4 years ago, # |

+77

Got rly lucky and got first :) Screencast: https://youtu.be/uGrBHohIgQY

→ Reply

4 years ago, # ^ |

u r legend.

→ Reply

SuperJ6

4 years ago, # ^ |

+28

How to get lucky as often as you and win everything?

→ Reply

duckladydinh

4 years ago, # ^ |

+23

seems like the thinking phrase was missing

→ Reply

torpedo11

4 years ago, # ^ |

+13

The only reason why I was able to solve the 4th question was that I had seen this video from your Youtube channel in which you applied dfs on the trie. It's a simple and easy concept but still was very helpful. Thanks!

→ Reply

strange_sherlock

4 years ago, # |

← Rev. 2 →

+167

The "Case #x: y" is the most bullshit thing I have ever seen in my life.

→ Reply

apoorva222g

4 years ago, # ^ |

Totally agree

→ Reply

4 years ago, # |

+18

11000 people gave this contest. Never ever in the history of kickstart. what make sudden rise.

→ Reply

4 years ago, # ^ |

2100 something people participated in last year November 2019. Such a huge increase in participation.

→ Reply

apoorva222g

4 years ago, # ^ |

Because here in India we are observing Janta curfew an unofficial type of lock down. So all interested Indians participated. even in other parts of the world every one of them are in their home

→ Reply

Finding_Infinity

4 years ago, # ^ |

← Rev. 2 →

-9

Corona Effect

→ Reply

4 years ago, # ^ |

+69

Maybe because everyone is at home.

→ Reply

4 years ago, # ^ |

how much u solved? how to solve D.

→ Reply

4 years ago, # ^ |

There is an analysis section, you can check editorial there too. By the way D can be solved using trie, Rolling Hash, or even with segment trees.

→ Reply

4 years ago, # ^ |

ok.

→ Reply

4 years ago, # ^ |

I solved it using Trie, felt most intuitive to me.

→ Reply

4 years ago, # ^ |

yes, i see.

→ Reply

dunjen_master

4 years ago, # ^ |

Since we need some information about prefixes and not any arbitrary range, using Trie is best and a lot easier.

→ Reply

Ausmosian

4 years ago, # ^ |

Any ideas why this brute force is even passing the larger test cases as well. I mean why am I getting both test cases passed without trie etc.

Spoiler

{

    int ans = 0;
    for (int l = 1; l <= max_len; l++) {
       map<string, int> freq;
       for (auto s : v) { //Iterate given strings
         string pref = s.substr(0, l);
         if (pref.length() < l) continue;
         freq[s.substr(0, l)]++;
       }
       for (auto cnt : freq) ans += (cnt.ss / k);
    }
    cout << "Case #" << tst << ": " << ans << endl;

}

→ Reply

ajit

4 years ago, # ^ |

How to solve D using segment trees?

→ Reply

4 years ago, # ^ |

See this.

→ Reply

apoorva222g

4 years ago, # ^ |

Corona

→ Reply

tanmay2625

4 years ago, # ^ |

+10

Besides Corona Effect, I think there's an another reason. The first problem in this Kickstart problem set was ridiculously easy so almost everyone attempted it. Otherwise, many candidates who can't come up with a remotely working solution for the first problem, simply leave the contest, without a single submission.

→ Reply

bully....maguire

4 years ago, # |

How to solve Plates (second problem) ?

→ Reply

4 years ago, # ^ |

go for knapsack type dp, pick j th plate from ith stack or leave it.

→ Reply

Ankit__

4 years ago, # ^ |

← Rev. 3 →

can u provide your solution please??

→ Reply

Trgt_2021_explosion

4 years ago, # ^ |

Spoiler

…

                          int plates=p;
                     int[][] dp= new int[plates+1][n+1]; 
                     int[][] pre=new int[n][k+1]; // holds prefix sum of beauty
              // dp[i][j]- max beauty of picking i plates from 1st j stacks
	        	    
               for(int i=1;i<=n;i++){dp[1][i]=Math.max(dp[1][i-1],arr[i-1[0]);} 
       
	 for(int i=2;i<=plates;i++){
	      for(int j=1;j<=n;j++){
	           for(int cp=0;cp<=Math.min(k,i);cp++){    
                       // cp-no of current plates we are picking from jth stack
	        	dp[i][j]=Math.max(dp[i][j],pre[j-1][cp]+dp[i-cp][j-1]);
	           }
	      }
	   }
	        	   return dp[plates][n];

→ Reply

Ankit__

4 years ago, # ^ |

thank you :)

→ Reply

PRESS_F_2_PAY_RESPECT

4 years ago, # ^ |

Using dp.

→ Reply

MadhuramJ

4 years ago, # |

I really feel stupid not noticing the 4th problem and wasted 50 minutes rejoicing. Anyone else along with me?

→ Reply

tanmay2625

4 years ago, # ^ |

How is that even possible?

→ Reply

MadhuramJ

4 years ago, # ^ |

My page size was such that it did not fit the 4th one. And I did not notice there is an option for other problems. Yeah I feel silly.

→ Reply

hiiwave

4 years ago, # |

← Rev. 2 →

I used trie to solve the 4th problem. I personally felt that it's a feasible solution with good efficiency, though unfortunately I got WA in larger test. Is there anyone willing to take a quick look at here for me? I hope I could debug by myself, but I have no idea how to proceed since google is unwilling to release the test set even after the contest (sighed). Would be really appreciated if anyone can help :D

→ Reply

kumarpratyush4

4 years ago, # ^ |

did u take care of space?

→ Reply

hiiwave

4 years ago, # ^ |

← Rev. 2 →

I think the space should be fine. Also I got WA instead of MLE.

→ Reply

dannmmaster

4 years ago, # |

-6

How much pwople going to round B?

→ Reply

ritik_patel05

4 years ago, # ^ |

Everyone can participate in all of Kickstart's round. This is no elimination kind of contest.

→ Reply

dannmmaster

4 years ago, # ^ |

Oh, ok, thanks)

→ Reply

Trgt_2021_explosion

4 years ago, # |

← Rev. 2 →

what is wrong with my greedy approach for C

for every session to be added pick that consecutive (a,b) whose difference is maximum and add a seesion at (a+b)/2+(a+b)%2. and i did it using priority queue 1st test case passed but got WA on other.

Please help.

→ Reply

4 years ago, # ^ |

Testcase for which your code fails is

3 2

1 2 10

The answer is 3 (insert 5 and 7) ,but you would get 4

→ Reply

gaurav5

4 years ago, # |

-6

How to solve problem D using trie ?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

First insert each string in the trie ,then traverse the trie starting from the head node and count the frequency of each prefix in the trie.

The answer would be the sum of frequency/k for all the prefixes.

Code

→ Reply

4 years ago, # ^ |

← Rev. 3 →

Will it be the sum of frequency/k or sum of valid frequency(atleast k strings possesssing that prefix). Also, when adding the frequencies, ain't we adding up the undesired frequencies too?

for eg — rain, rainbow, rainy, rat, ra, with k=3 so r->5, ra->5, rai->3, rain->3, ra->2, rat->1, rainb->1, rainy->1...and others.

According to me, we should add (len. of "rain")*(freq. of "rain")/k into our final answer and subtract the this frequency from previous prefixes, ie — (freq. of "rai") -= freq. of "rain" and propagate this difference to the previous prefixes.

→ Reply

4 years ago, # ^ |

BTW, why did you use map and pushing the prefix count and later doing ans+=map[depth][i]/k instead of directly doing ans+=freq/k in the traverse() function?

→ Reply

4 years ago, # ^ |

Yes you are right it can be written that way as well.

PS- This code is what I wrote during the contest so it may not be as neat as it should be.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

I did it both ways(yours and my way) but still getting WA. I'm doing traverse thing in the fun() function.Can you check a bit this code?

→ Reply

4 years ago, # |

← Rev. 2 →

Although, I did the 3rd question(Workout) using binary search, How to do it using priority_queue?

→ Reply

bryceShakeair

4 years ago, # ^ |

Is there any category , you would put this problem to ?

→ Reply

Polar_

4 years ago, # |

In problem D why does sorting and then grouping them into size of k and then finding longest common prefix for each group is not working . I wasted my 2 hours on this . Anybody help ?

→ Reply

4 years ago, # ^ |

Consider this test case

Bundle Size = 2
AB AC AC AD

By your logic, you will group (AB, AC) and (AC, AD) with sum 2. While the correct answer is 3 by grouping (AB, AD) and (AC, AC).

→ Reply

Polar_

4 years ago, # ^ |

Thank You so much for the test case .

→ Reply

gupta_samarth

4 years ago, # ^ |

I tried every cyclic shift after sorting. Is there a counter test for that too? Or my implementation was incorrect ( I got WA xD ) ?

→ Reply

4 years ago, # ^ |

+19

Consider this

Bundle Size = 2
AB AC AC AD AE AE

In any of your cyclic shifts, you will either have (AB AC) (AC AD) (AE AE) or (AC AC) (AD AE) (AE AB) with sum 4. While the correct answer is 5 by grouping (AB AD) (AC AC) (AE AE).

→ Reply

gupta_samarth

4 years ago, # ^ |

Thanks a lot.

→ Reply

akashpatel20

4 years ago, # |

Hi everyone,

For problem 4, I implemented using Trie and passed the small test but somehow I got MLE for the large test, I spent hours trying to find out. Thank you in advance.

My code:(https://ideone.com/s8IpR6)

→ Reply

Rahul

4 years ago, # ^ |

You need to free the dynamically allocated memory using delete after each test case.

→ Reply

4 years ago, # ^ |

← Rev. 3 →

Writing destructor also didn't worked for his code. There may be possibly infinite recusion or loop allocating memory indefinitely.

→ Reply

Rahul

4 years ago, # ^ |

You're right. The actual issue was in the function print1(), which was $$$\mathcal{O}(n^2)$$$ in time and memory because it passed the string as parameter. It now ACs even without freeing memory. https://ideone.com/4U0qVM

→ Reply

himkha_100

4 years ago, # ^ |

Why exactly does this work? Can you explain the intuition behind the approach?

→ Reply

akashpatel20

4 years ago, # ^ |

Thank you so much.

→ Reply

sedefcho

4 years ago, # |

← Rev. 2 →

-19

KickStart 2020, Round A. The limit for N of 10^5 in test set 2 which they specified in problem 1 ("Allocation") is incorrect. I am pretty sure they have a test case in test set 2 with more than 10000 houses.

Why? I was getting RE on test set 2 and I spent about 1 hour trying to find "the bug" in my program, and then finally as a last resort I decided to just extend the size of my arrays to 10^6. And the same code which I already had and which was giving me the RE, it suddenly worked fine (just with the array size changed).

Did anyone else notice this issue in test set 2?

→ Reply

rmn

4 years ago, # ^ |

FYI 10^5 != 10000

→ Reply

-deleted-

4 years ago, # |

The ranklist was filled with people who never solved more than 2-3 Problem, but guess what,today they solved a friggin trie problem...On a totally unrelated note someone sent me a picture of people discussing on whatsapp groups, but let's just ignore it :)

→ Reply

4 years ago, # ^ |

Yes, i agree. but how u know they r the same people who never solve > 3 problems. I understand there is a lot of cheating and many knows from where they r from. but what they will gain, they will get crushed if they called for interview. so chill :_)

→ Reply

swapnil159

4 years ago, # ^ |

They will get crushed no doubt, but someone might not get a call because of these people, considering google does not call everyone.

→ Reply

4 years ago, # ^ |

Yes.. u r right. Google should take it seriously.

darkshadows please convey it to google. It happened on large scale today.

→ Reply

SuperJ6

4 years ago, # ^ |

+24

Google only contacts the top <100 based on previous competitions, so I doubt you can cheat your way to that high because if you need to ask for sol you probably can't code fast enough and you'd have to copy paste from someone in the top 100, and the people that high in ranking do not want to cheat. So if you're worried about cheaters taking your interview, you nor them is probably getting an interview.

→ Reply

Ashish

4 years ago, # ^ |

+18

Are you sure about the <100 thing? I had a 2 digit rank last year but wasn't invited. I know a guy who had a 500+ rank but was invited for the interview :-/

→ Reply