Corona Effect

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

-43

How many people scored 100/100?

→ Ответить

aditya_sheth

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

More than 500 as of now.

→ Ответить

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

← Rev. 2 →

-127

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

Please Downvote it if you would proivde the code.

→ Ответить

dunjen_master

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

+15

my solution

→ Ответить

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

+26

Code 1:

Code 2:

I did my part and downvoted.

→ Ответить

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

-56

Provide a working code if you have

→ Ответить

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

+24

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

→ Ответить

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

+13

Especially the second one.

It's short and nice.

→ Ответить

zjj1149

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

-18

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

→ Ответить

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

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.

→ Ответить

bryceShakeair

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

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

→ Ответить

Ausmosian

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

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

→ Ответить

socho

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

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!

→ Ответить

Ausmosian

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

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.

→ Ответить

--oldaccount--

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

+18

2nd was def tougher than 1200

→ Ответить

Bhj2001

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

+63

Speedforces

→ Ответить

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

-53

send your code with speed right now.

→ Ответить

Bhj2001

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

+21

I used _dobby_'s code

→ Ответить

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

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

XDD

→ Ответить

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

Speedstart to be precise.

→ Ответить

rr459595

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

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

→ Ответить

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

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.

→ Ответить

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

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

→ Ответить

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

+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 $$$

→ Ответить

mdazmat9

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

yeah i did the same ,Having original value is important

→ Ответить

ritik_patel05

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

Wow, that's smart way.

→ Ответить

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

Can you kindly post your solution?

→ Ответить

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

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

→ Ответить

fraj

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

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

→ Ответить

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

← 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$$$.

→ Ответить

rr459595

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

Ahh, Thanks.

→ Ответить

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

← Rev. 2 →

I solved it using the priority queue.

My code.

→ Ответить

rr459595

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

Ok,thanks.

→ Ответить

tmwilliamlin168

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

+77

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

→ Ответить

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

u r legend.

→ Ответить

SuperJ6

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

+28

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

→ Ответить

duckladydinh

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

+23

seems like the thinking phrase was missing

→ Ответить

torpedo11

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

+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!

→ Ответить

strange_sherlock

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

← Rev. 2 →

+167

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

→ Ответить

apoorva222g

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

Totally agree

→ Ответить

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

+18

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

→ Ответить

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

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

→ Ответить

apoorva222g

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

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

→ Ответить

Finding_Infinity

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

← Rev. 2 →

-9

Corona Effect

→ Ответить

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

+69

Maybe because everyone is at home.

→ Ответить

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

how much u solved? how to solve D.

→ Ответить

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

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.

→ Ответить

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

ok.

→ Ответить

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

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

→ Ответить

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

yes, i see.

→ Ответить

dunjen_master

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

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

→ Ответить

Ausmosian

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

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;

}

→ Ответить

ajit

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

How to solve D using segment trees?

→ Ответить

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

See this.

→ Ответить

apoorva222g

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

Corona

→ Ответить

tanmay2625

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

+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.

→ Ответить

bully....maguire

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

How to solve Plates (second problem) ?

→ Ответить

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

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

→ Ответить

Ankit__

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

← Rev. 3 →

can u provide your solution please??

→ Ответить

Trgt_2021_explosion

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

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];

→ Ответить

Ankit__

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

thank you :)

→ Ответить

PRESS_F_2_PAY_RESPECT

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

Using dp.

→ Ответить

MadhuramJ

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

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

→ Ответить

tanmay2625

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

How is that even possible?

→ Ответить

MadhuramJ

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

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.

→ Ответить

hiiwave

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

← 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

→ Ответить

kumarpratyush4

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

did u take care of space?

→ Ответить

hiiwave

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

← Rev. 2 →

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

→ Ответить

dannmmaster

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

-6

How much pwople going to round B?

→ Ответить

ritik_patel05

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

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

→ Ответить

dannmmaster

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

Oh, ok, thanks)

→ Ответить

Trgt_2021_explosion

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

← 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.

→ Ответить

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

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

→ Ответить

gaurav5

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

-6

How to solve problem D using trie ?

→ Ответить

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

← 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

→ Ответить

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

← 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.

→ Ответить

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

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?

→ Ответить

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

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.

→ Ответить

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

← 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?

→ Ответить

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

← Rev. 2 →

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

→ Ответить

bryceShakeair

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

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

→ Ответить

Polar_

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

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 ?

→ Ответить

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

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).

→ Ответить

Polar_

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

Thank You so much for the test case .

→ Ответить

gupta_samarth

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

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

→ Ответить

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

+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).

→ Ответить

gupta_samarth

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

Thanks a lot.

→ Ответить

akashpatel20

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

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)

→ Ответить

Rahul

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

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

→ Ответить

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

← Rev. 3 →

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

→ Ответить

Rahul

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

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

→ Ответить

himkha_100

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

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

→ Ответить

akashpatel20

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

Thank you so much.

→ Ответить

sedefcho

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

← 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?

→ Ответить

rmn

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

FYI 10^5 != 10000

→ Ответить

-deleted-

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

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 :)

→ Ответить

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

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 :_)

→ Ответить

swapnil159

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

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

→ Ответить

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

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

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

→ Ответить

SuperJ6

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

+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.

→ Ответить

Ashish

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

+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 :-/

→ Ответить