Invitation to CodeChef June Long Challenge 2020

,
21

People cheating in codechef, nothing new. :rofl: :rofl:

3 Likes
22

So did u solve the challenge question with ML

23

BIn bulay apan birthday me free ka peet aate hai ye to fir bhi long challenge hai!!! kyu @saurabhshadow :rofl: :rofl: :rofl: :rofl: :rofl:

2 Likes
24

Not at all. I can’t do anyting about this type of problem. :rofl: :rofl: :rofl:

25

What type can be solved with ML

1 Like
26

Please discuss these things after the contest. :slightly_smiling_face:

2 Likes
27

Hello @admin

I just want to report a guy @mehul_0007 who asked about underlying concept about an ongoing problem from the long challenge

https://privnote.com/yMCbmCsI#tvu8955zw

Please look into this

28

Just send a simple email to help@codechef.com.

32

when will the ladoos be credited? I have finished in top 10 indians under division two for the first time…so i don’t know how much time it takes…pardon

33

Only Top 3 Challenge Scorers in DIV2 get laddus.

34

Argh! Damn it :sob: I was fourth.

1 Like
35

If you actually apply filter for country-India and for Challenge Scores, you’d see that you are 3rd(or 2nd because Indian Winner is excluded…not sure though). Hence, you’d get Laddus. Congratulations! :partying_face:

1 Like
36

Can you please share your approach for the challenge problem?

37

I guess my solution is one of the simplest solutions, I did not use the probabilities give at all!

Submisson
So the main idea is to find the sum of each row (indirectly) and passing it to a rowsolve function.

I started solving rows from bottom up, and each row from left to right. The idea was to binary search half row sum and recursively solve the two split halves. If you see my code you’ll find that I use slightly different logic to solve rows 31-60 and rows 1-30, hence you’ll see two functions bottom() and top(). For the indirect query for a row, it’s better if you see my code rather than me explaining it.

Now coming to the row solver, what I need is the sum of elements in the first half of the row. Now that every row below it is filled, I can just query a whole block from r to 60, and subtract the value of A[i][j] for other rows! (Again I did some optimization for top half and bottom half, but the main idea is querying a bigger block with elements that are already computed and subtracting them out)

Another optimization that I did was, to query a small portion (let’s say bottom left), let’s denote this piece by u.

  • u: r 1 60 c

Now I query 3, different blocks x, y, z as follows:

x: 1 1 (r-1) 60
y: 1 (c+1) 60 60
z: 1 (c+1) (r-1) 60

Now, u = \text{FULL}-x-y+z
I did this for smaller blocks of u, and memorized the query made for x and y.

Tip: Not sure if this is a tip, but I did optimizations one by one and submitted the code. It’s easier to debug this way. Debugging the code with all the optimisations is a nightmare!

P.S: I’m not very good at explaining logic, so sorry if it was confusing :stuck_out_tongue:.

[UPD]: My original idea was to linear search for the row sums. I then optimized it to binary search, but the score did not reduce much. So I never had the motivation to do the same for the top half :3. So there is no top() function, just a bottom() for row 31-60, and the rows 1-30 is a regular linear search.

2 Likes
38

Almost same approach but I can’t find much optimisations so ended up with just 22
Though I could have reduced approx 120 extra queries… but I gave up too earlier

1 Like