| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
Hi guys,
Just a quick question, as I am quite puzzled about the verdict difference.
Those two codes are identical, but it passes in G++17 and fails in G++14.
Locally, those two seem to both produce -2 as an answer for the first test case for both G++14 and G++17.
I am guessing I made a trivial mistake somewhere.
Could you guys enlighten me with why it passes on one but not the other? I am guessing it could be due to using unsupported/undefined behavior in G++14.
Thanks a lot!
Yongwhan
Hi guys!
I am soliciting an opinion on a practice strategy for a low-purple who are aspiring to become a mid-orange. I am pretty sure this kind of questions is very frequent and common among competitive programmer but I would like to just confirm your opinion to be sure. I read "A Way to Practice Competitive Programming" by Masataka Yoneda among other things. So, I know one way of getting there. But, I would like to know if there is a better recipe before I commit to doing something naive.
To get to orange from purple, is it SUFFICIENT to practice problems in rating ranging from 1900 to 2300?
My practice strategy has been focusing on all the problems that are below 1900 mostly, hoping to become a purple through solving problems fast. However, I have a feeling that I would hit a wall pretty quickly if I continue this recipe since the problems in division 1 are much harder.
Now that I finally became purple (after solving some thousands of problems in Codeforces and other platforms), I would like to know if my naive strategy of solving all problems in a particular rating range is enough to get me to the next rating color (from purple to orange, from orange to red, and so on).
I think this question is especially relevant to those who worked hard to get to orange from purple because, if it did not take a long time to get to orange color, I assume that you had a prior exposure to competitive programming in some other shape or form.
Those who had to train hard to earn the color change from purple to orange, what worked especially well for you guys?
I am looking for a genuine advice for me to get to the next level.
Thanks!
To endure COVID-19, I plan to post daily virtual contests using Codeforces problems in vjudge.
The links to the planned contests in the future can be found here. See you on the leaderboard!
As we have schedule for TopCoder Open and Google Code Jam/Kickstart this year, I am curious to know when we will know about the schedule for the 2020 Facebook Hacker Cup? Could someone with more information enlighten the Codeforces community about it? I would like to mentally prepare myself for the competition since it is already February! Thanks!
I would like to know if there is any way we can get the rating/difficulty of the problems using Codeforces API? Obviously we can use user status to get to the problems a particular user solved. But I would like that to the difficulty of each problem so that I can actually produce a histogram.
I think the API has not been updated since the new edition of rating/difficulty in problemset. It would be awesome if you can point me to the right direction!
I am confused by this problem: 429A - Xor-tree
As far as I understand, in the sample test, after applying operation on node 4, we have:
0 0 1 0 0 0 1 1 1 0
Now, if we apply operation on node 7, we get the original sequence back; that is:
1 0 1 1 0 1 0 1 0 1
So, the upshot is if we apply operations on the nodes that are even distance apart, they completely cancel each other out, leading to only four distinct states.
I am now convinced that I am thinking about the problem in a wrong way. Is it perhaps that the initial node that you are applying the operation to does not flip its state? (I read the problem statement multiple times but it is not written that way)
Could anyone point out what I am missing from the problem statement? Judging from so many AC's I am sure I am missing something but at the moment I stay puzzled. I read the editorial but still could not make sense out of the problem.
Thanks!
I did not spend too much time on thinking about the execution time since the 6-minute is usually much more than the required in the usual online contest (e.g., 2 seconds for CodeForces for instance). So, for each problem, I took whichever way leading me to code reliably.
Also, for each problem, I did lots of stress testing since I screwed up few contests (e.g., the large input in the previous Google Code Jam) before by not fully testing my codes with respect to the full constraint given by the problem. For A and C, I generated the edge cases manually and compared the computed answers from the brute force approaches and made sure they match. For B and D, I generated the theoretical worst case to make sure they are handled properly using my codes.
Thankfully, I hit few segmentation fault problems 4-5 hours into the contest, from which I tried few approaches to increase the stack size; manipulating the size limit in #include<sys/resource.h> did the trick for me. I was so glad that I did the stress testing because if I did not there was no way that I would have spotted this issue before the submission.
As usual, just in case I found a bug in my implementations though, I waited until 5-6 hours before the submission deadline to start submitting the code; I think it is roughly the optimal time frame, since I would like to chew on the problems a bit more yet I would like to avoid a technical mishap where the URL goes down due to a crazy submission rate in the last minute.
Though I thought I did everything right, during this round, I hit an interesting problem in downloading the inputs for B and D, perhaps because I was not using my own computer (a cluster computer was being used); I am so thankful that it was resolved by contacting the contest coordinator through the feedback.
I checked my solutions with my friends', Petr's, and ahmed_aly's; thankfully, I got a match. Then I tested my codes in the Gym; after removing the system calls, I got a few TLE in D because the original limit was set too tight to 15 seconds; I changed calculating in long long to int and used few other tricks to bring down the time to where it is now: roughly 8 seconds.
This problem can be treated by pre-calculating the primacity using the sieve, followed by the usual trick of the cumulative sum, which was my original approach; the cumulative sum approach works since 2 ≤ A ≤ B ≤ 107 and it would be useful when T is large (say T ≤ 107 queries are asked). However, since T is so small, it suffices to calculate the number in a brute-force way, and the latter was probably the intended solution.
By the way, since the product of first 9 primes is already 223092870 > 107, when k > 8, the required answer is 0; this is precisely the idea I used to compute for the pre-calculated table.
Few ways to make the problem harder would be either making 107 as 1018 (to disable pre-calculating for the table) or making T as large as 108 (basically a constant time per query).
This problem is a classical question on a trie; I used a fairly standard implementation that I frequently tested in various online judges, adopted from a coding contest bible by JongMan; by the way, it is a great book and you should definitely check that out. I certainly learned and am learning tons from the 2-volume set. I challenge you to find a contest material that is better than that in a book-format.
There is a plenty of room for an optimization especially since the alphabet is limited to only a, ..., z (i.e., only using an array; this is certainly an approach took by some folks), but I used my tested approach to be safe and save some debugging time, especially since the execution time was not too critical.
The system call is disabled in CodeForces Gym. So I had to submit a code without it. It worked out just fine since the default stack size was set sufficiently large.
This problem is a standard dynamic programming problem. Given 0 ≤ m < n ≤ 2000, it is sufficient to compute the table explicitly and a lot of contestants did it this way. However, I took the top-down approach, since we may not necessarily hit all the pre-computed values for each valid pairs (n, m) since T is, again, too small.
The key insight is perhaps the following: if we denote the desired quantity using stressfree(n, m) and stressful(n, m) then they both satisfy the recursion of the form f(n, m) = f(n - 1, m) + f(n, m - 1), with some boundary conditions. The base condition is that when either n or m is 0, the required answer is 1 and for the stress-free it is 0 when n ≤ m while for the stressful, precisely the reverse holds, n > m. It turns out we can combine these ideas together and get the answers using just one table, but for the clarity of the implementation, I made a separate function and a table for each.
In my original implementation I cleared out the table each time a pair of inputs is received, but there is no reason to do this. Notice from below that the execution time is improved by a factor of ≈ 4, but again, the execution time is not what I sought after :)
Of course, one thing to take care of is the mod since the number gets too large for some pair (n, m). This can be approached in a standard way by taking a mod in each summation step.
Although I have not tested, I am sure the same approach would work fine even when the bound is a bit larger (say 20000) or T is larger. I am curious to derive the explicit formula for the two quantities for any pairing (n, m), which can surely be done by, at least, a generating function; I originally thought about the problem using this pathway, but gave up on it since the boundary condition was tricky and the dynamic programming was more than sufficient (and easy enough to code).
Addendum: It turns out the problem is related to the Bertrand's ballot theorem/monotonic path and/or Catalan numbers. Check either the Wikipedia entry here or discussion below for more details. This is the approach I was trying first (using the generating function and etc.) but quickly resorted to the standard way since there was no real reason to think too hard about it unless I already knew the identity; now I do :)
This is yet another standard dynamic programming problem, this time on a graph. The problem statement forces us to a directed acyclic graph; it is directed since it is a managerial relationship and acyclic since two employees are never responsible for each other. Also, since each node has a unique manager and the CEO has no manager, this would force us to a tree with a root at the CEO node.
For each node, we have to save the children in the adjacency list; the matrix is not feasible since N can be as large as 200K. The list would be certainly fine since we are given a tree. Once we have that, to do the DP, only thing we need to take care of is the recurrence relation.
Given that a current node uses a gift x, what is possible for the child? The only restriction is that if gift y is used for the child, y ≠ x. Respecting this, we would like to find the minimum. Of course in the leaf node, we would choose either 1 or 2, depending on whether its parent has already used 1 or not. So, we are led essentially to the following recurrent relation on a node in a tree:
where dp[cur][x] is the minimum attained where the current node is using a gift x. So, at the end, all we need to output is dp[1][0] where 1 denotes the root node and 0 is the sentinel value not used in the computation. The only real issue now is to think about the bound on x, which turned out to be quite trickier than I originally imagined.
I originally thought that the bound has to be 3, but during the stress testing I realized that on some random instances I can get it as large as 5. Then I started comparing the result of 3, 4, 5, 10, 15, 20, and 50. While I compare those results, I tried to come up with the bound on it explicitly. Then, the crude bound I got was log2(n), which led me to believe that the bound of 20 was enough. I thought about it a little more and in the morning I improved the bound to log3(n), which led me to believe that the maximum x would be 11 when N = 200000.
Just in case I did not carry out the estimation right, I fixed my bound to 15, from 20; I did not go all the way to 11, since I did not want to cut it too close. I could not find a test case that actually used anything beyond 7 during my random search and thought it was safe enough; I figured I would check whether the answer would change if I used different bound for the provided input and surely enough no change was detected from fixing the bound to 20 or 50, from 15. So I decided to submit the version that used 15 at the end.
After the contest ended, I had a conversation with Ralph, who led me to believe that the right sequence is perhaps the order-consecutive partition, yet to be fully verified; from anyone who can prove this rigorously, I would love to get to know your insight! (See more details here) :)
To summarize the topics covered in this contest, they were, in short:
I started entering more online contests and take some online judges (like Timus, SGU, CodeForces Problemset) seriously. Foremost, I would like to thank paladin8 who is patiently coaching me through this entire process. I think it is working out pretty well and I will continuously put some efforts to improve! I now also have a table that keeps track of daily solved problems, coding tricks, and etc.
My current goal is to solve at least 3-5 problems/day from the Timus online judge with a goal of surpassing 500 problems by the mid-year; since I have ~260 problems down, I only have about a half way to go! If there is anyone who would like to join my pursuit to solve the problems in the Timus OJ, please let me know via a private message; I am sure I would get more motivated by a small group going through it together :P
I am hoping this entry would help at least some people out there :)
Any feedback would be much appreciated!!
I would like to know if there is a similar database (like the one here: http://apps.topcoder.com/wiki/display/tc/Algorithm+Data+Feeds) available for CF and GCJ.
I know that there is data available (in the form of sqlite3) for GCJ, maintained in http://go-hero.net/jam/, but I think it would be very useful if there is any in the form of XML or the like. If any of you know, please let me know!
