April Long - Behind the scenes

1

This month the problemset was a bit easier than usual, so I decided to make scorable the same 10 problems for both div1 and div2. That also makes it easier for recruiters to compare the performance of div2 coders with respect to div1.

The testing phase was very smooth, @theoneyouwant and @aryanc403 found bugs in some of the problems and suggested some subtasks. Maybe to reduce the work load, we should always have two testers for long contests?

BOLT, SSCRIPT, SOCKS1: In the last long contests, there was always one okayish problem that I also included in div2, however this time I found the three problems very trivial.

SDICE: The arrangement of dice and their orientation is very intuitive, it requires a bit of casework.

KAVGMAT: During the review, Um_nik found the linear solution. However it is very hard to distinguish the logarithmic factor, so we just allowed N^2 log N solutions.

MEXSTR: I feel it is easier than KAVGMAT. Can you solve the version with substrings instead of subsequences? It seems some contestants solved that version during the contest.

BOOLGAME: The contestants found a much easier solution than the intended one. Probably we’ll get a harder version in a future contest!

TREEPERM: The initial proposal asked only to find any solution. I suggested many variants, the author was able to solve the counting one.

CHAOSEMP: @jay_1048576 always invents nice interactive problems! It seems he gets most of his ideas from games, this one is based on the 2003 video game Project IGI 2.

PAIRFLIP: During the review I found the problem interesting, the covering with paths of length 2 arises naturally from a problem of operations on matrices. Um_nik disagreed though, it turns out the covering problem is well known, and there are some timus and atcoder problems that require similar ideas. I suggested including different costs per operation, but we couldn’t solve it. It is hard even in the case with only two different costs, one for rows and another for columns.

STRPOW: If you see a problem by @samarth2017, then it is about fft and polynomials :slight_smile: Um_nik found a more optimized solution that allowed us to increase the constraints.

SHRINES: The majority strategy is in the folklore of graph theory, and is a very natural idea when trying to find the median sets and centroids on trees. The dual of the given graph is median and the same strategy works. I think the solution is a bit guessable, I expected much more ACs. Initially I planned to directly give the dual, however while generating tests I liked the algorithm that finds faces by keeping the paths of open regions.

WTRSORT: It is based on the android game Water Sort. I had the feeling it could be converted in a Chemistry problem by including information about possible reactions and densities of the reagents. At the end we just added operations to increase the height of tubes and reverse the order of reagents.

25 Likes
2
3

Recruiters won’t recruit from div3??

4

Probably yes :slightly_smiling_face:

1 Like
5

solve my query
why do i get wa using kmp
https://www.codechef.com/viewsolution/44462797

6

question CodeChef: Practical coding for everyone

7

@prash_pra2 Recruiters wont recruit cheater anyways, so TATA BYE BYE :wave:

2 Likes
8

I too figured out the linear time solution for KAVMAT. i also had the simplest algorithm of precalculating and then finding the best upper left vertex for a given lower right vertex such that average in region would be greater than equals to K using binary search. But then i went on with linear time complexity solution using 2 pointers. I didn’t knew nnlog(n) was allowed

coming to water sort i did play that game but in the one i downloaded had aim to separate all colors in just one test tube. Was looking for heuristics to solve the problem but then gave up.
maybe next time

9

Your str is not bouned on the right by “\0” so after k * it may contain garbage values that’s why.

try putting str[k]=’\0’; after memset(str,’*’,k); and it might work.

11

partially ac for 30 point but bro i did not understood what to said i know every string get with null char. at last .so putting only after the memset it worked i did not understood
can u please give me example if it getting out bound it run time error.

12

oh wait it worked but putting str[k]=’\0’ before memset
after memset partially ac i did not understood

13

check this before memset CodeChef: Practical coding for everyone
after memset CodeChef: Practical coding for everyone
explain it bro. it’s happening becuz of memset

14

It will be great if you just answer my question. If you think that someone is a cheater then just report that to codechef. I think the will take care of that.

15

Bro try debugging your code.

in the partial answer u uncommented s[n] = ‘\0’ at line 117

16

bro i have commented s[n]=‘\0’ but still it partially putting str[k]=‘\0’ after the memset
check CodeChef: Practical coding for everyone

17

also i did not understood why did it get ac putting before memset

18

It’s seem like you are new to competitive coding.

here’s why
u basically made an array of st which basically means u reserve some space to be filled by characters

u fill from index 0 to k-1 by ‘*’ and fill the kth index by ‘\0’
so either you do it before memset or after memset the result will be same. kth index will be ‘\0’

Also the question doesn’t require KMP (KMP is used in other places where pattern matching is quite complex).

In the current question you can simply run a loop and figure out the answer. Try Watching some video editorials to see how else you could have solved this problem

19

bro i got this (i thought null char. already put by complier as i never did before)
but result r not same putting before and after it as u can see your self

20

@akshay_012 glad u got it

1 Like
21

but bro tell me this one
result r not same putting before and after it as u can see your self