No.87 Advent Calendar Problem

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 159
作問者 : yuki2006

お気に入りにしたユーザー Tweet ProblemId : 218 / 自分の提出

Various Things About yukicoder (+ a Problem)

    この記事はCompetitive Programming Advent Calendar 2014の12/7の記事として書かれた記事であり、問題でもあります。
    問題文はページ下部にありますが、問題文の情報だけでは解けないかも知れませんのでご注意ください。

Note:
This is a long diary-style post. Much of it is my personal thinking, with little technical or algorithmic content.
The admin has a low rating, so none of this is likely to be very convincing. I even wonder whether I should be writing an Advent Calendar post at all. In other words, this is for myself.
Although this is the Competitive Programming Advent Calendar, this post has less competitive programming content than the others,
and some of you may feel you gained nothing from reading it, so I am offering a problem as thanks for stopping by.

After reading this post, some of you may think, "Isn't that why the admin's rating is low?" or "Is that really good competitive programming practice?", and you are probably right.
Of course, none of this is meant as criticism of the services mentioned in the post.

Announcement) On Sunday, December 7, starting at 19:00, we will hold yukicoder open 2014, with about 10 problems ranging from easy to hard, so please join if you have time.

How yukicoder Came to Be: The Study Group

• The problems themselves are good algorithm practice, so that part was fine.
• Creating a TopCoder account is a high hurdle. (Maybe it is easier now?
• Installing the Arena is a high hurdle. (It got along especially badly with Java on Mac
• Installing plugins is also a high hurdle.
• Few languages are supported. (Some people wrote in Ruby and so could not get through the judge)
• Learning how submission and system tests work also takes a lot of effort.
• Having the problem statements in English is also a high hurdle.

Honestly, for an English-language service this is pretty much unavoidable.

After a while I learned about AtCoder, and the study group moved over to AtCoder as well.

• Having the problem statements in Japanese really is nice
• Support for many languages is also nice　
• Creating an account, submitting, and using the judge are easy to learn

These were quite good, and I think participants enjoyed it more than before.
We used AtCoder for some time, and I think I introduced quite a few people to it.

To prepare for each study group, I would pick problems from AtCoder's past contests that seemed to suit the participants at that time and assign them at the session.

After a while, as the organizer, I began to find some things a bit of a hassle.
(I hope you can guess what from the features and operations implemented in yukicoder.)

Partway through, I also began giving my own problems at the study group, since we did not need to use a judge anyway.
The study group mainly does code review, and we have all sorts of discussions about everyone's code.
This is one of the reasons I decided to make yukicoder.

How yukicoder Came to Be: The Blomaga Era

In fact, this problem is based on a true story: on the way home from that study group, I blundered and missed my stop on a limited express train, then caught up at a station further along by Shinkansen.

At first there was no judge at all, and the style was to answer a single case using ideone.
It was modeled on "nmCoder", which you probably all know.
(In fact, I had taken part in it a few times myself.

Incidentally, as far as my streaming went, I had spent a while doing a stream working through "Learn You a Haskell for Great Good!", that project had ended, and I was wandering around wondering what to do next.
For the first few rounds, I posted problems but nobody solved them, which felt rather lonely...

I continued in this style for a while,
and later on various people started sending me problems, which kept things going. When submitted code gave the right answer for "the given case" but was wrong for another case, we pointed out each other's mistakes as a "challenge".
(This leads to the policy below.

After about 20 rounds this way,
the judge system project started from the thought, "With only one test case, we really can't tell whether a solution is correct."

Then, after much trial and error, the judge system came into being.
At first the site was rough, but it has since been reborn twice, becoming the current site.

yukicoder's Policy

Those who have participated so far probably know this, but if you are thinking of joining, please read this first.

This comes from running things since the Blomaga era,
and from thinking about what I would want as practice for competitive programming from the viewpoint of a Div2-level participant.
(Of course, this is my personal impression. Skilled and top-ranked people will surely see it differently.)

• Run for educational purposes rather than as a fair, highly competitive contest
• Aim to be a place for sharing knowledge
• Even with some mistakes and omissions, level up by pointing them out to one another
• About test cases
• About intended solutions (my personal view)
• Summary

Run for Educational Purposes Rather Than as a Fair, Highly Competitive Contest

yukicoder calls itself not a competitive programming site but a competitive programming practice site.
By practice I mean that, instead of designing problems and systems that set proper times and avoid unfairness, as AtCoder does,
our policy is that even problems and operations that would be criticized in a real competition are fine as long as people feel afterward that "I learned something."

As for problems,
we will post typical problems, problems that seem to have appeared before, math problems, and straightforward implementation problems alike.

In particular, people who have only recently started competitive programming actually have few chances to encounter typical or previously seen problems, so I want to post them as much as possible.

My feeling is that anything is fine unless it is a problem that is nothing but heavy implementation with little to gain (a heavy-implementation problem).

Aim to Be a Place for Sharing Knowledge

This is just my own view, but
in competitive programming, so-called typical problems, algorithms such as "DP" and "maximum flow", libraries such as BIT,
and even things like "depth-first search" that are hard for newcomers are all, to a greater or lesser extent, games of knowledge and advance preparation.

Given that, I want to reduce cases of "I couldn't solve it because I didn't know that" or "I couldn't solve it because I didn't have that."

Not only algorithms, but also general programming techniques and knowledge such as "writing it this way is easier" and "in this language you can write it like this": I want this to be a practice ground for sharing them "while having fun."

What I am aiming for may be closer to
sharing programming techniques than sharing algorithmic knowledge.

Beyond programming, it would be nice to also share surrounding knowledge, such as the MathJax (TeX) notation used in problem setting.
For example,
$2015 \le N \le 10000000000=10^{10} $ is

Even with Some Mistakes and Omissions, Level Up by Pointing Them Out to One Another

I myself make quite a few careless mistakes.
Often I do not even notice that I have made a mistake, and sometimes I only realize it when someone points it out specifically.
(Please do point them out as much as you can...)

The basic idea is that I do what I can, have whatever slips through pointed out, be grateful for that, and apply it next time to gradually improve my skills.

Conversely, being able to point out mistakes is also a skill, so assuming there will be some mistakes, I would like to offer some kind of incentive for pointing them out.

About Test Cases

Test cases are created when a problem is posted.
Ideally they would cover every possible case, but in reality that is difficult. Or rather, nearly impossible.
So there end up being only a few dozen cases, and I think there will be code that should not pass but still gets $AC$.

In such cases the test cases are certainly weak, and this should be avoided as far as possible.

I think one should learn how to make strong test cases,
and strong test cases are of course better. (Anywhere other than yukicoder should do so)

What I have been thinking is that a judge for a practice site may be "a reasonable number of test cases" + "reviews from strong people".
(I am relying on others here, sorry. Those who can make strong test cases will of course see it differently.)

Personally, I think it is better for practice if, even though something was $AC$ at first, someone later points out that it was actually $WA$. (In a proper contest that would of course be a problem, and strong people may see it differently)

The test cases themselves may contain mistakes, so even if you first got WA/TLE/RE, once something is pointed out and identified, we will fix or add cases and rejudge as appropriate.
This may cause some inconvenience to those who submitted. We ask for your understanding.

About Intended Solutions (My Personal View)

This continues from the previous section.

To put it in an extreme way that relies on others,
I think it might be fine to take the view that "if nobody objects, we treat it as correct for now."
(Of course this is the extreme version, and in general it is probably a dangerous way of thinking.)

Even if the Writer has thought up an intended solution and test cases and believed them correct at the time, they collapse in the face of an accurate objection. If anything, if there is no objection then it is probably correct for now, and I think such a policy might be fine.

If someone notices and points something out, the Writer also gains something, such as "I overlooked it, but there was this case too" or "I learned this piece of knowledge", and I think that is a good thing.

As for those who want to try practicing problem setting,
even if the intended solution or other aspects of a posted problem turn out to be wrong, there will be people who still want to solve it,
and if someone points something out and it becomes a chance to learn what you had not noticed, I think that is good enough.

Summary

The policy is: let us point out and ask one another about mistakes in code, in algorithms, and in algorithmic approaches, treating it all as a form of practice.
To that end, I want to keep implementing things and features that motivate practice.

I think your skills will surely improve that way, so you can just be careful next time.
I hope you can make use of this for solving and setting problems on AtCoder and TopCoder.

As the operator, I want to provide a practice ground for problem setting and solving.

Of course, we cannot keep calling ourselves yurufuwa (easygoing) forever, so I ask for your forgiveness while we are still developing, and I want to gradually firm up our skills and systems.

In the distant future, I vaguely hope to make this a practice site for programming in general, not limited to competition.

yukicoder's System Architecture

• Backend web server Go (Revel framework/mark6)
• Frontend HTML/CSS/JavaScript (HTML uses Revel templates; no meta-languages are used.)
• Frontend libraries jQuery / Twitter Bootstrap / noty
• Judge server Docker / Python / shell scripts
• Database MySQL
• Database management software MySQLWorkBench
• Version control/backup tool Git
• Git hosting site BitBucket
• IDE IntelliJ IDEA + Go plugin
• Syntax highlighters highlightjs/ACE Editor
• WebFont M⁺ OUTLINE FONTS

About Go

Actually, I had never touched it before.

All I knew was the talk about whether the successor to C++ would be D or Google's Go.
For web languages I had personally used (Java)/PHP/Python, but I really wanted static typing, so I took this opportunity to try it, and I came to like it quite a bit

As a language it is statically typed, but its philosophy seems to be not making you write anything unnecessary or inferable.
It supports multiple return values, so many functions return a normal value along with an error value, and unused variables or imports cause compile errors.

My impression from using it is that it is like Python with no exception mechanism (though it has panic), plus static typing and pointers.
Typing really is convenient when refactoring and when writing something quickly.

Revel Framework

I had never properly used so-called MVC frameworks such as CakePHP or Rails, but once I tried it, it was convenient.
I especially like the HTML templates, which are also a feature of Go, and being able to specify the Controller access targets in routes.

It is said to derive from the philosophy of Scala's Play framework, so those who have used Play may recognize it.
Go's standard features are powerful in themselves, so some may say no framework is needed.
By the way, I found a small bug in Revel, so yukicoder uses a version I patched myself.

The tags and attributes usable in yukicoder's HTML editor are whitelisted. That processing is handled using kroton's mark6.

jQuery/Twitter Bootstrap/noty

jQuery and Twitter Bootstrap are becoming essential libraries.
(Though some people seem to shy away from a site with an obvious stock Bootstrap look.

noty is the thing that appears at the top when you save and so on. yukicoder uses ver 2.2.9, but I hear it was recently updated to ver2.3.0.

About Docker

It is the container-based virtual environment that has recently become popular.
Judging is done inside it.

Go calls the judge server, Python generates shell scripts for the "compile and run commands", and execution is done inside Docker.
The judging itself is done in Python.
I chose Python because it is what I can write quickly.
Also, I do all sorts of tinkering for Java/Scala.
It is nice to be able to create a low-overhead virtual environment so easily.

About MySQL

MySQL is a famous RDBMS (Relational Database Management System). At first we used Sqlite, but we migrated to MySQL.
I manage it with MySQLWorkBench.

About Git

git, needless to say, is the popular VCS (Version Control System).
To deploy to the server, I push to bitbucket and pull on the server.
I also use it as a backup tool. Automatic commits and pushes with cron make a lot of things go smoothly.

IntelliJ IDEA

It is an IDE.
I use it for competitive programming too. Actually, I sometimes think Eclipse, though heavy, is better at taking care of the small details.
Being able to have a separate Window for each project may be nice.
The community version is free.

Syntax Highlighter

The syntax highlighter for program code is highlightjs.
Its selling point is automatic language detection, but its detection of python seems dubious.
I may soon migrate to ACE Editor, which is also used on the edit page.

WebFont

Discontinued as of May 2015.
There were troubles such as fonts being hard to read, not displaying, or displaying slowly, the cost of dealing with them was high, and displaying web fonts honestly did not improve the user experience much, so I decided to discontinue them.
(Also, the SourceForge domain where it was hosted went away)
Japanese web fonts still seem premature.

WebFont M⁺ OUTLINE FONTS
A WebFont that has become well known recently.
Loading Japanese WebFonts is especially slow, so I use lazy loading. Without it, particularly when viewed from Safari, no text at all was displayed for over 30 seconds.
Reference: A no-fail story of lazy-loading web fonts and social buttons to speed up websites (external site)

Distinctive Features of yukicoder

• Smart Submit: being able to submit with Ctrl+V is handy, isn't it.
• Shortcut keys: you can navigate between pages with just one key
• Editorial tab: you can write editorials, and I also want to gather links to editorial blogs
• In the future, I am considering various other new features, including special judges.

Acknowledgments

• Thank you to @9610n , who built the base of the current system and works behind the scenes on the operations side.
  
• Thank you to @naoki_kp, who participates almost every time and has ported past problems and tested the judge.
  
• Without this person, yukicoder might not exist.
  Thank you for so many problems, @enuemuenuemuenu.
• Thank you for many solutions, editorials, and pieces of advice, @laycrs.
  

This site also exists thanks to everyone who has contributed problems and everyone who has solved them.

And now, at last, here is the Advent Calendar problem you have all been waiting for.

Problem Statement

Among the years from $2015$ to $N$ (including both $2015$ and $N$),
find the number of times the date on which yukicoder no.1 was posted (stated in the article) falls on the same day of the week as in $2014$.

Use the same calendar as in the real world.

Leap years are determined by the usual method.
・A year divisible by $4$ is a leap year.
・However, a year divisible by $100$ is not a leap year.
・However, a year divisible by $400$ is a leap year.
Assume that the Gregorian calendar is still in use in the year $N$ AD.

$N$

2015

0

2038

3

3000

141

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。