We invite you to participate in CodeChef’s Starters 85, this Wednesday, 12th April, rated till 6-stars Coders (ie. for users with rating < 2500). This contest is organized by Programming Club, DAIICT.
Time: 8:00 PM — 10:15 PM IST
Note that the duration is 2 hours 15 minutes. Read about the recent CodeChef changes here.
Joining us on the problem setting panel are:
Setters: Deep Deep_Kanani Kanani, Kashyap zxy0909 Panchani, Preet preet_25 Sheth, Kunj kunj_patel Patel, Jalp Jalppatel1428 Patel
Statement Verifier: Kanhaiya notsoloud1 Mohan
Video Editorialists: Sundar K Letscode_sundar, Madhav jhamadhav Jha, Suraj jhasuraj01 Jha, Jwala jwalapc, Rohit ezo_tihor Oze
Text Editorialists: Nishank IceKnight1093 Suresh
Contest Admins: Jatin rivalq Garg
Written editorials will be available for all on Discuss. Pro users can find the editorials directly on the problem pages after the contest.
The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Hope to see you participating. Good Luck!
Div 1 unofficial editorial
print N % 20. (With a string you can use up to the last 3 digits.)
The pattern is n//2*3 — n%2. In general second row bishops want 2 moves and first row bishops want 1 move, except when there is only one bishop on the "/" diagonal, or the (2,2) bishop.
Binary search for the answer. Standard dp lets you query the sum of a radius d box centered around (r, c), that also needs A[r][c] >= 1 for the mentor to stay there.
https://www.codechef.com/viewsolution/94358156
Precalc lpf (least prime factor) of all numbers <= 1e6. For each A[i], find all the primes that divide it and store in a map p -> A[i]. Now for each query, find all primes that divide it to get the lowest candidate. Store A in a multiset and remove that candidate (or the lowest).
https://www.codechef.com/viewsolution/94359936
We can represent the answer in terms of one sided half-blasts like : [0, 0, 1, 2, 3, 4, 0, 0, 0, 0].
Line sweep. The events are of the form "started" or "ended length=4" (following the example). Keep track of how many blasts are active (active += 1), what the running sum of the actives is (s += active), and what the running sums of s is (t += s). When you get an "ended length=r", then active -= 1, s -= r, t -= r*(r+1)/2. The answer at each step is ans[i] = t.
https://www.codechef.com/viewsolution/94359537
Let F(u) = sum_{v child of u} d(u, v). Represent binary numbers as an array<int, 32>. We can add binary numbers without carrying (eg. (1, 0, 1) + (1, 1, 0) = (2, 1, 1)) and evaluate them into base 10 later. This makes circular shifting and xor-ing easy, in particular calculating [(X xor shift(d1)) + (X xor shift(d2)) + ...] from [d1 + d2 + ...]. Now a standard dp gets you F(0).
Rerooting gets you the rest of the F's. When rerooting u to v, handwaving a bit but basically F(u) -= F(v), size[u] -= size[v], size[v] += size[u], F(v) += F(u) happens.
https://www.codechef.com/viewsolution/94360578
Your approach for $$$F$$$ is so cool :D
How are the number of submissions for the first 4 problems in Div 1 basically the same? The 3rd was way more difficult than the 1st! This happened even in the last contest.
Difficulty only affects number of solves past a certain point. For example, I'm guessing based on your rating that on Codeforces your solve rates for div. 2 B questions and div. 2 A questions is around the same (~ 100%), even though div. 2 B questions are typically harder. Similarly, I'm sure a div. 1 contestant on Codechef would agree the 3rd problem is harder than the 1st, it's just not hard enough for them to not to able to solve it.
I was upsolving the contest. And in div.2, I found problem E much easier than C and D. I think it's rated 2422 because less people tried it due of it's position. D seems to involve genuine thought, at least for me.
I can feel you, did first 3 in 10 minutes and 4th one took 1 hr :( though I got the logic but took a lot of time to implement.
I have done similar thing as described in the editorial but my solution is giving TLE on 2/11 testcases. GCD Queries
Any help is appreciated. Thank you
Update : I had made vector of multiset for storing all numbers that has prime factor "p" and defined the size of vector 1e6+5. Just changed the vector to map and it got accepted.
I also had 2/11 and others tle.
What I changed--> instead of iterating on all factors of my map and checking if my current answer had that as a factor, I just iterated over all factors of the answers itself and removed it from the map.
Solution
Feeling very bad that I missed it by an inch during the contest :(
I am doing that only, erasing all prime factor of my current answer. I am getting TLE on first 2 cases only.
I know my code is a bit messy. But if you could see once and let me know if am doing anything wrong.
Sad bro, I have nearly 1 hour to do this question, still cant figure out
Update : I had made vector of multiset for storing all numbers that has prime factor "p" and defined the size of vector 1e6+5. Just changed the vector to map and it got accepted.
your modified code
I changed you code for using map<long long ,multiset> and instead of vector and also :
facts.push_back(spf[xx]);
for this you could use a set as pushing say, 2 more than 1 times (any factor for that matter) is useless.
I think 300 query limit was tight in B_BRANCH