It is up: http://apps.topcoder.com/wiki/display/tc/SRM+601
This was a very dry editorial to write. All problems were mathy ad hoc or complex yet sort of-obvious dps. It is very hard to explain that stuff.
My plan was to finish it yesterday, but I procrastinated. So the new plan was to finish it today, before the Codeforces match, but I couldn't do it. Now I have to spend the following 48 solving div1 hard. It is going to be an odd Christmas.
At least it wasn't catastrophically bad this time.
You have `n <= 50` bags. Bag `i` has apples[i] apples and oranges[i] oranges. The process to make a valid gift involves taking exactly X fruit (`X > 0`) from each bag (The number of apples and oranges you take from each bag must be exactly X). The number of apples and oranges determines the kind of gift you make. Count the total number of different kinds of gifts you can make, that is, the total number of distinct pairs `(A,O)` where `A` is the number of apples and `O` is the number of oranges.
The trick is to notice that the value of `X` you pick uniquely determines the sum `(A + O = nX)`, which means that it is impossible to get the same pair using two different values of `X` . The problem is now about counting the number of pairs for each `X`.
Given `X`, then the number of apples you get in total uniquely determines a pair `(O = A - nX)`, so we just need to count the total number of ways to pick `A` given `X`
The next important fact is to notice that the set of valid `A` values ought to be a interval. So if you know `a_0` and `a_1` are valid and `a_0 <= a_1` , then all `a_0 <= i <= a_1` must be valid too. Then you just need to find the minimum and maximum possible number of apples. The maximum can be found by picking the largest possible number of apples from each bag. The minimum number of apples can be found by picking the largest number of oranges from each bag. Once you get the minimum and maximum number of apples, just subtract them to count the total number of ways to pick it.
long getNumber(vector<int> apple, vector<int> orange)
{
int n = apple.size();
int m = 2000000;
for (int i = 0; i < n; i++) {
m = std::min(m, apple[i] + orange[i]);
}
long res = 0;
// For each valid X:
for (int X = 1; X <= m; X++) {
// If we take X, then there are nX in total.
// maximum:
int mx = 0;
for (int a: apple) {
mx += std::min(X, a);
}
// minimum:
int mn = 0;
for (int o: orange) {
mn += std::max<int>(0, X - o );
}
// total:
if (mx >= mn) {
res += mx - mn + 1;
}
}
return res;
}
I couldn't think of a solid solution. I did make the conclusion that you can first pick the first bit position at which the xors differ. Then the problem is about counting the number of ways to have xors: yyyyy1????? and yyyyy0?????. It seems this is the starting point of a solution, but no luck yet.
So far it seems like an ok match. Time to write the editorial. Got to rush because I don't want to be busy with it during Christmas. ... Or do I?
Some time ago I talked about how I made a script to be able to organize TopCoder problem source codes by automatically creating a folder for each contest. But some time after that I had to desist of using this folder organization, because TopCoder contests have different names during the match and when in the practice room ! (During the contest, it is Single Round Match XXX, the practice room is SRM XXX). So if I used Greed to organize my problems like that, I would have to always move my code from a folder to another after every match. And that's annoying.
After that, the hindrances of having all problem source codes in the same folder became more and more noticeable to me. However, I also reckoned that a folder per contest was not so great, either, too many folders. Both approaches return in the main folder having too many children. My dream solution was something of a hybrid. Separating SRMs in groups of 25 SRMs, TCO problems in one folder, TCHS folders in another, TCCC in another. And also a folder for the remaining contests. There are a few of odd contests that don't belong to those categories and we don't really need a whole category or folder for each of them.
The first step of making this work is to make the arena plugin do it. After some hacking and some convincing I managed to get the code to do exactly that into the current git version. It will be officially in whatever next release is (second beta? Official Greed 2.0? Who knows?. But you can just compile Greed from its github right now if you want this.
What I did was to create a complex helper Class to render Contest names using very special rules. Basically, you modify Greed.conf and add:
codeRoot = "${Contest;category(srm=25)}"
This instructs Greed to change the codeRoot folder to a special kind of name. By default, codeRoot is exactly equal to the contest name found out by Greed, but with this modification, it will be equal to "TCO" if the contest name contains "TCO" or "Topcoder open". Or if the contest name is "SRM XXX" or "Single Round Match XXX", the folder name will be "SRM a-b", where a-b is a interval that contains 25 SRMs. E.g. "SRM 400-424". Of course, if you change the srm=25 with srm=100, the number of SRMs per interval changes. Here you can find a detailed explanation of what ;category does.
The old problems were in a single topcoder folder containing them all. Now that greed uses the folder structure I wanted it to use, I still need to move previous problems to the correct folders.
The first issue was getting a problem's contest name automatically. I solved this little problem with the folder organizer script I posted a while back. Now all the problems are inside folders with names equal to topcoder contests. But I still needed to re-organize these folders...
So I made another script:
# Topcoder folder organizer
#
# err let us say it is released under the zlib/libpng license
# http://www.opensource.org/licenses/zlib-license
# (c) Victor Hugo Soliz Kuncar, 2011
#
#
import urllib, re, sys, os, time, string, glob
def fixContest(result):
separate = 25
if 'TCHS' in result:
result = 'TCHS'
elif 'TCCC' in result:
result = 'TCCC'
elif re.match( ".*(TCO|(top\s*coder\s*open)).*" , result, flags=re.IGNORECASE):
result = 'TCO'
elif re.match( ".*(SRM|single\s*round\s*match)\s*(\d+).*" , result, flags=re.IGNORECASE):
num = re.match( ".*(SRM|single\s*round\s*match)\s*(\d+).*" , result, flags=re.IGNORECASE).group(2)
#print '{%s}' % num4
num = int(num)
a = num - num % separate
b = a + separate - 1
result = 'SRM %d-%d'%(a,b)
else :
result = 'Other'
return result
def inFolder():
os.chdir("./")
for dirname, dirnames, filenames in os.walk('.'):
# print path to all filenames.
for filename in filenames:
if dirname != '.':
contest = './'+fixContest(dirname[2:])
if not os.isdir(contest):
os.mkdir( contest )
os.rename( os.path.join(dirname,filename), os.path.join( contest, filename) )
inFolder()
What the script does is take each folder in the current work directory ( ./ ) and for each folder, get the contest category (Same as ;category("srm=25") in Greed) (You can change the separate variable in the script from 25 to something else). And move the files inside the folder to the better category.
Thanks to the modifications of Greed and the two scripts, I have a neatly organized topcoder folder. Note that because of ;category, no matter if a contest is named "Single Round Match XXX" or "SRM XXX", the result is the same.
I always talk about the Greed plugin, it is just so customizable. It is hard to measure the power it has. From its simple default setup to what I am going to introduce you to in this post. In this post, we are going to make Greed create a Code::blocks work environment and call code::blocks automatically whenever you open a problem. I hope this example can be adapted also for other IDEs.
This post is about Greed 2.0, which is currently in beta. And not just beta Greed 2.0, but possibly the latest in git, I hope greed can have a jar release soon, but for now you'll need to get it from github and compile it. Basically you just download the contents of the repository and use ./gradlew fatjar to compile it and make a jar for you which will be saved in the build/libs folder
In a first step, let's learn all that is needed about the compiler and how to set it up. Open some problem in Greed. My favorite test subject is the problem TBlocks from the TCO13 championship round. After you open it in greed, assuming you are with default config, it will create 3 files in a specific folder in your Greed work folder.
In greed 2.0, the default behavior is to save example data in the .sample file. The .cpp file then has to read from this .sample file, and the .sample file has to be in the command's work folder when you run the compiled program. While the ability to save examples in a separate file is cool, I disagree with this as a default, I think it complicates things too much. It is possible to change this behavior, but for the matter of this tutorial it will be a good thing, because I am teaching you how to make it all work in your IDE.
Let's create a Code::blocks project that runs this stuff for us. Go to File/New project/ when asked for the kind of project, pick console application.
Tell it you want a C++ project. It will then ask you for a project title, folder, etc. For them use the name of the problem and the location in your Greed workspace. In following image, my Greed workspace is /home/vx/topcoder. We want the project file in the same folder as the source code and sample...
It will then ask you for what compiler to run. You should have already set up the correct compiler: (Hint: You'd like GCC 4.8.1 (Mingw in windows) to simulate TopCoder's server the best). If you ask me, you probably don't need a release configuration, as you only want to test code before sending to topcoder, leave it as debug.
Now we have some issues... First, it unilaterally decided that you want the main file to be called main.cpp. We would like it to be the same file as greed generated. Let's change it to TBlocks.cpp. Right click main.cpp and select remove file. Now right click the Project name and select Add files and add the TBlocks.cpp file generated by greed.
Another thing, you'd probably like c++11 support (and I hope you are using gcc 4.8.1) so go to Project/Build options... And tell it to use c++0x.
Actually, there is a plethora of options you'd like to set. To mimic topcoder the best, you'd like "Optimize even more (-O2)" and also I recommend to add "-Wreturn-type -Wcomment -Wunused-variable -Wunused-parameter -Wno-sign-compare" (without quotes) to the other options section.
After this, running the source code by pressing F9 will work just fine. Code::blocks will run the project in the directory we wanted.
Of course, doing this for every single problem is too much trouble, so we'll now use Greed's power to automatize it.
All about greed works using templates. What we'd like Greed to do is to create a project file automatically for each problem. Code::blocks project files are saved with cbp extension and are actually XML files. Let's save all work we put in Code::blocks (Make sure to save the project!) and open TBlocks.cbp:
<?xml version="1.0" encoding="UTF-8" standalone="yes" ?>
<CodeBlocks_project_file>
<FileVersion major="1" minor="6" />
<Project>
<Option title="TBlocks" />
<Option pch_mode="2" />
<Option compiler="gcc" />
<Build>
<Target title="Debug">
<Option output="bin/Debug/TBlocks" prefix_auto="1" extension_auto="1" />
<Option object_output="obj/Debug/" />
<Option type="1" />
<Option compiler="gcc" />
<Compiler>
<Add option="-O2" />
<Add option="-std=c++0x" />
<Add option="-g" />
<Add option="-Wreturn-type -Wcomment -Wunused-variable -Wunused-parameter -Wno-sign-compare" />
</Compiler>
</Target>
</Build>
<Compiler>
<Add option="-Wall" />
<Add option="-fexceptions" />
</Compiler>
<Unit filename="TBlocks.cpp" />
<Extensions>
<code_completion />
<debugger />
</Extensions>
</Project>
</CodeBlocks_project_file>
The rest is to create a Greed template to generate files like that. Let's first define the template in greed.conf. If you don't already have this file in your Greed workspace, create it.
greed {
shared {
templateDef {
codeblocks {
override = false
outputFile = "${Problem.Name}.cbp"
templateFile = "codeblocks.cbp.tmpl"
}
}
}
}
That is the basic stuff you need to add a new template to greed. The template will be called codeblocks. By default the file won't be overrided if it already exists. The template file will be codeblocks.cbp, located in your workspace folder. The file it generates will be called just like the problem name and be put in the code root folder (same folder as source and sample). What we'd like for this file is to be exactly like the one above, except to replace TBLocks with whatever problem name we need:
<?xml version="1.0" encoding="UTF-8" standalone="yes" ?>
<CodeBlocks_project_file>
<FileVersion major="1" minor="6" />
<Project>
<Option title="${Problem.Name}" />
<Option pch_mode="2" />
<Option compiler="gcc" />
<Build>
<Target title="Debug">
<Option output="bin/Debug/${Problem.Name}" prefix_auto="1" extension_auto="1" />
<Option object_output="obj/Debug/" />
<Option type="1" />
<Option compiler="gcc" />
<Compiler>
<Add option="-O2" />
<Add option="-std=c++0x" />
<Add option="-g" />
<Add option="-Wreturn-type -Wcomment -Wunused-variable -Wunused-parameter -Wno-sign-compare" />
</Compiler>
</Target>
</Build>
<Compiler>
<Add option="-Wall" />
<Add option="-fexceptions" />
</Compiler>
<Unit filename="${Problem.Name}.cpp" />
<Extensions>
<code_completion />
<debugger />
</Extensions>
</Project>
</CodeBlocks_project_file>
We would just like the template to be created whenever we open the problem. Since it is specific to c++ we will modify the c++ templates line.
greed {
language {
cpp {
templates = [ filetest, source, testcase, problem-desc, codeblocks ]
}
}
}
The templates line is usually [ filetest, source, testcase, problem-desc ], it is the list of templates to create automatically. By adding codeblocks, we tell greed to create the codeblocks template. In greed reload the configuration, if everything went right, open some other problem, like the 400 points problem in the same TCO finals match.
It should say: Generating template [codeblocks] -> TCO 2013 Finals/PackingSquares.cbp or something like that, depending on the folder.
Now open the newly-created PackingSquares.cbp in Code::blocks, it should have everything set up, including the new source file.
How about that, instead of just creating the project file and needing us to open it manually, Greed also ordered Code::blocks to open it when we open the problem? All is possible.
To the part where we added the codeblocks template, add this:
codeblocks {
override = false
outputFile = "${Problem.Name}.cbp"
templateFile = "codeblocks.cbp.tmpl"
afterFileGen {
execute = codeblocks
arguments = ["${GeneratedFilePath}"]
}
}
Now whenever the project file is regenerated (You may need to tell greed to regenerate code for problems you already opened) code::blocks will be opened...
The arguments part tells codeblocks what file to open. GeneratedFilePath is a special variable that returns the whole path to the file generated by the template.
Ok , we have a problem, if code::blocks was closed before opening the problem/regenerating the code then code::blocks will close immediately after opening. This is because Greed will run the new process without creating a thread. I will ask for an option to fix this in greed, but for now, we have a couple of workarounds, the first is to have code::blocks open while running the arena. The other is to create a script to run code::blocks in another thread for us. In *n*x* operating systems, save the following as threadcodeblocks.sh in greed's workspace folder, remember to set it as executable in permissions:
#!/bin/bash
codeblocks '$1' &
Change the execute = codeblocks line to execute = /path/to/greed/workspace/folder/threadcodeblocks.sh.
And done!
I hope it was useful. I think that every decent IDE out there saves project files as XML, there might be variations, but it is usually a text file, I hope.
So the double contest trouble last weekend ended and it was disastrous to me. But first , let me point you to the first 5/6 of the editorial at : http://apps.topcoder.com/wiki/display/tc/SRM+600
There were t-shirt prizes and I foolishly hoped to maybe get a t-shirt. I forgot how bad SRM 500 was on my luck.
I solved this one right-away. You need to pick the bit position that is non-zero in goal and that has the least valid cards. I needed some time to code it and then the strange self-doubt about "maybe something is wrong", also I really wanted to make sure to get that t-shirt. I reviewed the algorithm plenty of times and proved it to myself. So I submitted it. It wasn't a slow submission, but it wasn't particularly fast either, so I rushed to solve div1 600.
It was some time after the system tests that I learned my solution actually got challenged. I was very skeptical, because I was sure the algorithm is right. Well, the algorithm was right, but for some reason I initialized my result variable with 40. I am not sure exactly what happened. It could be I made a typo and typed 40 instead of 50. Or it could be I got the constraints confused and thought to type the maximum number of bits. I don't really remember.
There is a fun story about this challenge that ruined my dreams and rating. I already wrote about it, so here is a link.
I thought that my only hope for t-shirt was solving this problem. And for plenty of time in the match I thought I could do it. My first solution was actually quite close to correct. The only mistake I made was not to figure that you only need sets of palindrome rows/columns with exactly the required number of palindromes. You are not really going to care about the rows/columns so it doesn't really matter. You can actually read the first solution I tried, it is in the site statistics, it was `O(3^m)` because reasons.
When I finished coding it, I had two issues: a) It wasn't giving the right answers to example cases. b) It was taking too long (~4 more seconds than allowed) to solve the large example case. I made the mistake of thinking [Even if I fix this, it would be too slow]. It turns out that besides of bug fixes, the soution was correct. It just needed some pruning and to care only about sets with exactly the required number of palindromes. The new code was a dynamic programming that in reality did exactly the same as the old solution, I just didn't notice... New code was also wrong and somehow still slow. So the coding phase was a missed opportunity.
Anyway, this was a cool little evil implementation problem. I wish I solved it during the match.
It annoyed me that division 2 coders were getting t-shirts. It is a way to punish blue and yellow coders for not having low rating. I think that in matches with awards it would be preferable to have a single division (combined div1 and div2).
I wish this match didn't happen. So there was a new chance to get a t-shirt. But this time solving very hard problems. The match was advertised to have a normal SRM 1000 points problem. So I went to the match thinking of spending 4 hours on that problem and hopefully solving it. It was actually very obvious that far less than 40 coders were going to solve more than one problem in this match. When I learned the match actually had a challenge phase, I felt robbed. It was obvious that people were going to submit bogus solutions for some reason, allowing other people to get 50 points and probably joining the top 40.
Really, the TopCoder format is terrible for this kind of match. If the act of opening problems didn't penalize you, it would have been much better to open all problems before deciding which to solve. Instead, I had to rely on the point values assigned to the problems, which were terribly wrong. The 1000 points problem I spent 4 hours trying to solve was solved by no one.
It was a interesting problem. Come up with `n` distinct positive integers such that, for each `1 <= i <= n` , the sum of the `i` largest integers is less than or equal to `s_(i-1)`. Where `s_i <= 1000000000`. I spent a whole afternoon trying to find a secret. Trying to decode the safe that hides the solution to this problem. All with no luck.
So the t-shirts given to people that just got lucky (Many rooms didn't even have any submission at all, whilst some rooms were full of bogus solutions). It was a bit of a waste of t-shirts. I wish they would have included at least a div1 medium or easy problem so that there was a better tie-breaker than the challenge phase. IMHO, maybe not include a challenge phase at all.
Problems seemed good. I am just in a very bad performance streak. My decisions during contests are seeming to be very bad lately. Also, I seem to have completely lost the ability to correctly estimate whether a solution will run in time or not.
The way the SRM 600 celebration was made was very disappointing, giving prizes to div2 in SRM 600 or to people being very lucky in SRM 600.5. I would have preferred to have a single division in SRM 600 so that if div2 coders win a t-shirt it is by performing very well , or by being lucky. SRM 600.5 really didn't need a challenge phase...
Shortly after I discovered the Greed topcoder plugin, I spent some time customizing its templates and later did some really cool stuff by making a generic tester. It has been working great so far.
During the weekend a discussion erupted at the Greed github about making Greed support running test cases in different thread/process the main reason people like this feature is because if you make code that depends on global variables' values and requires them to be initialized with 00 bytes, then running all test cases as part of the same process causes errors. I never really cared much about this, because I wouldn't ever use globals like that :/. But during the weekend I figured I had good reason to use this sort of feature:
So that is when I started to experiment. The first thing I did was make Greed 2.0's default test template get this feature. I did some hacky stuff: Basically, the c++ program calls itself over and over again for each argument. But it works.
For my so-called "dualcolor" templates though, the requirements were higher because there is a lot more things to care about when printing results. The report at the end needs to know exactly what happened during the execution of test cases. Another issue is that I wouldn't be able to have access to the command line arguments in the tester file, unless I modified the tester call syntax (which would break old source files generated by old version of the template). So I had to do something else.
The eventual decision was to use fork and wait. fork() works great because it makes a copy of the current process. Wait is needed to wait for the process to end. The one problem about this is that it effectively makes the feature unable to work under windows (unless you use cygwin, I think). I make these templates for myself mostly and I don'tt have time to port to winapi. If you use windows and wanted this feature in my template I guess it sucks it when someone's software doesn't work fully on your OS of choice, eh?. Of course, maybe windows users still want the other cool features like the output colors and the easy-to-modify test cases, so when running in windows the whole thing is disabled. Metaprogramming to the rescue.
#if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__)
#define DISABLE_THREADS
#endif
#ifndef DISABLE_THREADS
#define DO_THREADS
#endif
#ifdef DO_THREADS
#include <unistd.h>
#include <sys/wait.h>
#include <sys/types.h>
#endif
The other negative side is that communicating with child process was sort of too complicated for me to implement without using an external file. So the tester now needs an external file to work. Currently it is located in /tmp/
Maybe some *n*x users have trouble getting this to work. Or maybe it is failing for some reason or making testing a specific problem difficult. Hence why if the DISABLE_THREADS thing is defined before including the tester.cpp file, the feature can be disabled.
The result is great. It can catch the usual issues (aborted due to some std:: exception, division by zero, segfault). To be consistent with the python version, letter E is used to signify test cases with runtime errors. Here is a sample:
Another feature that can be caught in the screenshot above is that the final results report in the bottom is now guaranteed to be one-line long. If the reported results is longer than that, it will be stripped. Of course, the line length can be configured in tester.cpp.
By popular (one person) demand. The mode that printed just and only the "final" report and nothing else is back. I don't like it because it doesn't work very well when you use printing for debugging. But I guess there are people who don't do that.
To choose output mode, find this line in template:
return Tester::runTests<${ClassName}>(
getTestCases<input, Tester::output<${Method.ReturnType}>>(), disabledTest,
${Problem.Score}, ${CreateTime}, CASE_TIME_OUT, Tester::FULL_REPORT
);
Change Tester::FULL_REPORT to one of these:
The official Greed version 2.0 is probably going to include these templates and just need a small configuration line to use them. Greed git already includes the older version.
TopCoder just updated default memory limit for new problems from 64MB to 256MB. More so, some problems might have different time/memory limit than default.
Very mixed feelings about this.
Time to update test script to use 256 MB, I guess.
