Codeforces will be possibly unavailable in the period between Sep. 19, 19:00 (UTC) and Sep. 19, 21:00 (UTC) because of maintenance. ×

### hmehta's blog

By hmehta, history, 3 months ago,

Topcoder SRM 807 is scheduled to start at 07:00 UTC-4 on June 9, 2021

Please Note: The round will consist of 5 problems with the difficulty level of Div II, and it will only be rated for Div II participants. (Members rated < 1200). Also, this round will not award points towards TCO21 Stage 4.

Registration is now open for the SRM in the Arena or Applet and closes at 06:55 UTC-4. The coding phase will start at 07:05 UTC-4, so make sure that you are all ready to go. Click here to what time it starts in your area

Please take a look at our How to Compete guide to understand Topcoder Algorithm rounds better.

Problem Writer: misof

Some Important Links:: Match Results (match results, rating changes, challenges, individual test case results), Problem Archive, Problem Writing, Algorithm Rankings, Editorials and Older Editorials(SRM 710 and before),

Best of luck!
- the Topcoder Team

• +12

 » 3 months ago, # |   +10 Starts in: Countdown
 » 3 months ago, # |   +60 Why isn't it called Rookie SRM? I'm always checking calendar for TC events and if I would not check this blog (which I did by coincidence), I would have no clue about the fact that it isn't normal SRM.
•  » » 3 months ago, # ^ |   0 I think it's normal SRM, they probably didn't have enough problems (or time) for Div 1.
•  » » 3 months ago, # ^ |   +13 I agree. The round should be named something else and Div 1 people should not be able to register. I will definitely get pissed off if I find this out in the arena.
•  » » » 3 months ago, # ^ |   +75 Apologies for the naming issue. This was originally intended to be a regular SRM, hence the name in the calendar. My work hardware died recently (always a joy) and as a consequence we weren't able to provide a full SRM prepared to the standard we want, so we went with a compromise that at least allows people to solve some problems — as opposed to cancelling the round completely. Given the situation, we didn't have any ideal way of communicating the change. We tried to do what we could (including this post by Harshit).Updating the round name in the public Google calendar is certainly something we should have done, and we'll try to keep it in mind for the future. (Of course, the primary goal is not to have things like this happen at all, but having a better plan for when they do is always a good idea.)Again, sorry to everyone who was affected by the change.
•  » » » » 3 months ago, # ^ |   +14 Thanks for being transparent on the situation. I do appreciate it a lot.
 » 3 months ago, # |   -26 opened 700, again a trivial problem,already have a solution in mind,misread it in a hurry,3 out of 4 test cases passed,went nuts tryna see wtf is wrong in code, 5 min before the end of contest just gave a shot to read problem statement again, realised we have to add zero when no digit present.. :')Lesson learned :)
•  » » 3 months ago, # ^ |   -8 imo, the problem statement would have been a lot harder if no zeroes were to be added. Being able to prefix zeroes essentially enabled us to cleanly iterate over all the digits and compute the permutation values for them, after all.
•  » » » 3 months ago, # ^ |   0 I don't think so,this is my code that I wrote for this problem Codevector>v(12, vector(11, 0)); reverse(A.begin(), A.end()); ll ans = 0; int pos = 0; for (auto x : A) { int tmp = x; vectordig; if (x == 0) { dig.push_back(x); } else { while (x > 0) { dig.push_back(x % 10); x /= 10; } } for (int i = 0; i < (int)dig.size(); ++i) { ans += (pos - v[i][dig[i]]); } for (int i = (int)dig.size(); i < 12; ++i) { ans += (v[i][10]); } x = tmp; int ct = 0; if (x == 0) { v[ct][0]++; v[ct][10]++; } else while (x > 0) { v[ct][x % 10]++; v[ct][10]++; ct++; x /= 10; } pos++; } 
 » 3 months ago, # |   0 So when is rating going to be updated?
•  » » 3 months ago, # ^ |   0 That will take a few hours, as Div I members are not to be rated. So a little manual effort on that.
 » 3 months ago, # |   0 Can someone explain the approach for the 1000 pt. problem (Flagpole)? I am pretty sure the O(sum * N) solution would TLE. Thanks.
•  » » 3 months ago, # ^ |   +1 Divide array in two arrays for maximum 20 numbers. Then create all combination of sums for two arrays and using Binary search find sum difference in 2nd array
•  » » » 3 months ago, # ^ |   0 Ok, so for every permutation of Array 1, all the permutations of Array 2 which when added to the current sum were producing legal values (values > LO and <= HI) were to be chosen, right? So the overall complexity would be O(2^20 * 2*LogN), which is totally manageable... (LogN if a set was used) Thanks.
•  » » » » 3 months ago, # ^ |   +1 Yes, you are right!
•  » » » » 3 months ago, # ^ |   0 subsets, not permutations
•  » » » » » 3 months ago, # ^ |   0 yes subsets
•  » » » » » 3 months ago, # ^ | ← Rev. 3 →   0 Yes, I probably should have used the term subset instead of permutation, but if you visualize the subset as containing a few elements (1 bits) and not containing the others (0 bits), then you can also think of every subset as a permutation of N bits.(In the same sense an 8 bit number can be said to possess 256 permutations)But yeah, here the term subset better describes the thing on which the operation is to be performed. EDIT: Thanks for the correction.
•  » » » » » » 3 months ago, # ^ |   +1 I wanted to point it out because 'subset sum' is a commonly used term. For example, you will get more results from googling 'subset sum' than from googling 'permutation sum'.Technically, in our context, a subset is not a permutation because different subsets may have different numbers of elements, whereas every permutation of a given bit string will have the same number of bits turned on.
•  » » » 3 months ago, # ^ |   0 btw, if someone doesn't know this idea, try searching for meet in the middle technique.
 » 7 weeks ago, # |   0 I can't figure out why my code for the last problem (Flagpole) is failing. It passes all the samples though. I'm just using standard meet in the middle. I'd appreciate if someone comes up with a counter case. CODE#include using namespace std; typedef long long ll; class Flagpole { public: ll build(vector, ll, ll); }; ll ans, mn, mx; map mp; ll pref[(int)1e6 + 5]; vector> v; void brute_left(int cur, int up, vector& segments, ll sum) { if (cur > up) { mp[sum]++; return; } brute_left(cur + 1, up, segments, sum); brute_left(cur + 1, up, segments, sum + segments[cur]); } void brute_right(int cur, int up, vector& segments, ll sum) { if (cur > up) { ll low = 1e10; ll high = -1e10; int l = 0, r = v.size() - 1; while (l <= r) { int m = (l + r) / 2; if ((sum + v[m].first) <= mn) { l = m + 1; } else if ((sum + v[m].first) > mx) { r = m - 1; } else { low = m; r = m - 1; } } l = 0, r = v.size() - 1; while (l <= r) { int m = (l + r) / 2; if ((sum + v[m].first) <= mn) { l = m + 1; } else if ((sum + v[m].first) > mx) { r = m - 1; } else { high = m; l = m + 1; } } if (low <= high) { ans += pref[high] - pref[low] + v[low].second; } return; } brute_right(cur + 1, up, segments, sum); brute_right(cur + 1, up, segments, sum + segments[cur]); } ll Flagpole::build(vector segments, ll LO, ll HI) { int N = segments.size(); mn = LO, mx = HI; brute_left(0, N / 2 - 1, segments, 0); for (auto it : mp) { v.push_back(it); } for (int i = 0; i < v.size(); i++) { pref[i + 1] = pref[i]; pref[i + 1] += v[i].second; } brute_right(N / 2, N - 1, segments, 0); return ans; }