Categories
Uncategorized

AtCoder from white to the god of Advanced Raiders

Foreword

Now the world’s largest program of Score website and AtCoder none other than the non-CodeForces, @ ezoixx130 CodeForces chiefs have been introduced in the last year (portal), so now we mainly talk about AtCoder.

Brief introduction

AtCoder algorithm is Japan’s largest athletic site, officially founded on June 20, 2012, by the operation and maintenance AtCoder Inc., its domain name https://atcoder.jp/. It provides programming online game, passing game submission, evaluation and other services online.

use

Home

1. The top menu bar functions:

Name

Features

Logo and Icon Home

Home

Game list

View user rankings

Select Language

Personal ID

View profile

Contest
Ranking
English

2. Left list:

  • Contest

Permanent Contests

This column is a list of ongoing game, which practise contest long-term, the main purpose of this game is familiar AtCoder evaluation system does not rank scoring. If you know nothing about evaluating the way AtCoder can practice in this game.

Upcoming Contests

Here you can view upcoming competitions and sign up.

Recent Contests

The recently concluded ten games, sorted by time. You are free to open any game, you do not need to sign up to the title.

  • Ranking

Chart is listed former active users ten. If a long time did not participate in AtCoder game, even if the Rating No changes, the account will be removed from the Rank chart.

3. The right of the list:

  • Information

AtCoder basic information, such as usage and Q & A.

    Bulletin Board

Typically, before the start of the race day, the site administrator will also publish a notice in the competition this bulletin boards and CodeForces blog to promote the game. This is AtCoder Grand Contest 028 located Codeforces publicity interface.

game

1. types of competition:
    AtCoder official competition is divided into the following three:

  • AtCoder Beginner Contest (ABC)

This is the most frequent and most simple entry game, held twice a month at least under normal circumstances. April 27, 2019 prior to (including), a total of four questions per game, while length of 100 minutes, out of 1000 points over 1199 players and Rating Rating excluding value. Since May 19, 2019 revision upgraded to six questions, the same length of time, out of 2100 points and the Rating value over 1999 players do not count Rating value. After the revision matches the quality and number of participants have a greater breakthroughs and improved. Since the entry title race is relatively simple, many participants choose to do the reverse problem. According to Luo Valley tournament title about the difficulty rating of red and blue theme – questions, this class tournament title with a strong educational value, it is recommended for beginners or participate in popular group of players to take part in this tournament in order to exercise the code proficiency.

  • AtCoder Regular Contest (ARC)

This is AtCoder regular season, total four topics, duration 100 minutes, out of range 2100 to 2700, over 2,799 Rating Rating value of excluding players. In particular, the present game is generally performed simultaneously with ABC, ABC C, D, two problems with this question before the same game, race problems and therefore usually numbered ARC C ~ F, ABC number A ~ D. Title medium difficulty, questions about race issues – purple yellow question in accordance with the Valley of Los difficulty rating. According to the official website of the AtCoder, this game should have more frequent than AGC, but in fact since ARC103 2018 Nian 9 May 29, then this game will not be held too.

  • AtCoder Grand Contest (AGC)

This is the best game AtCoder entitled to hire super players for all original. The contest problems have greater difficulty thinking normally. Usually held once a month, six topics, duration 110-150 minutes and is usually out of 5600. All players are counted Rating value.

2. Score mode

Generally, there is no part of the competition, the AC gets full score, otherwise it will be 5 minutes for each failed submission. The final ranking is counted in reverse order, and the same score is counted in ascending order in time. This is the most recent competition with partial parts.

At the same time every time the game will be divided according to a performance ranking results, performance scores and rankings positively correlated, Rating nothing to do with the individual, but by the absence Rating growth performance points decision.

3. Match Time

Normally, matches are held every Saturday or Sunday at 20 hours Beijing Time. Match time is much more friendly than CodeForces.

4. Competition interface

    Top menu bar:

Name

Features

Home game

Game title list

Q & A

Submit code

Game record and submit score

Real-time tournament rankings

Online IDE

After the match solution to a problem, an official solution to a problem AGC038 example

CodeForces game forum

Top
Tasks
Clarifications
Submit
Results
Standings
Custom Test
Editorial
Discuss

    Submit records

After submitting the code can be run in real time to see the results of each test point in Results> My Submissions> Detail, but does not display the contents of the test point.

After the game to see other people’s code is open and commit record.

  • Standings

Everyone can be displayed in the page rankings do question the state, in order to control the speed of their own problems, usually stronger heavyweights may AK ABC, 45 Fenzhong ARC, 70 Fenzhong AGC within 25 minutes.

    Note

1.AtCoder no community functions, that is, in the absence of the race, the discussion is not made for help, but you can ask in the game interface corresponding CodeForces propaganda, there is no one answer that is another matter.

2.AtCoder evaluation machine may be different from other OJ evaluation machine, the line feed operation is not performed after the output of your program ( ‘\ n’ or endl) may cause Wrong Answer. For newer title, this Bug has been fixed, but still this occurs when submitting a more distant subject. Valley in Los therefore many users often burst zero on pay issues, please pay attention. How long Luo Valley is not updated AtCoder exam, ah submit records show:? Wrap AC does not wrap WA

5. Competition alternate URL

AtCoder game not only take place in the main station, also in the race the secondary station, account number, submit records, rankings are synchronized. If the master is slow to load or display an error, then we can go to the sub-station to participate in the race.

The secondary stations may match the URL matches the name of configuration, e.g. AGC038 match sub station https://agc038.contest.atcoder.jp, the main station https://atcoder.jp/contests/agc038.

Rating System

Rating of different levels corresponding to different color ID, color and normal ID have eight kinds of two special colors. CoderForces with different systems, Atcoder initial value 0 Rating.

1. Normal color

colour

Rating range

gray

brown

green

blue

Light purple

yellow

Orange

red

0~399
400~799
800~1199
1200~1599
1600~1999
2000~2399
2400~2899
2900+

2. Special color

Did not participate in any competition ID will appear black, as a site administrator account purple.

3.Rating interface display

Personal information

1.My Profile

View personal information, including site-wide ranking, Rating change records, records and other data entries.

2.General Settings

You can change the nickname, binding Twitter account and CF account, set nationality, date of birth, place of work and other personal information. Special attention, the user name used to log in only once allowed to change, but the nickname is displayed when the game allows you to modify several times.

3.Change Photo

Modify personal avatar.

4.Change Password

change the password.

5.Manage Fav

In others personal page can click on the five-pointed star were concerned about the operation, the focus can be viewed here. Note synchronized local and cloud data manually.

6.Sign Out

sign out.

Language switch

Why say something to focus on language website AtCoder it?

Unlike other sites, AtCoder English and Japanese interface function is not exactly the same, that is, switch the language will lead to functional changes. Here is the Japanese page, and this page English Home page picture above screenshot at the same time, we can see that the left side of the game in progress in more than two, more than a game in the upcoming game, while bulletin boards the content richer, these are for the Japanese player’s game and ad hoc announcements page can not be viewed in English, but in Japanese page, we also can participate.

script

A well-known site is always ultimately a variety of helper scripts, and now we highlight some of the more convenient Tampermonkey script AtCoder use.

what? Not used Tampermonkey? In the center of the search and browser extension installed, open the site you want to search greasyfork.org installation script is ready for use.

1.ac-predictor

After installing the script, can be found at the right of the interface more than a sidebar to the left stretched the button, click to use its features.

  • Estimator

The points can be calculated Rating performance value, according to Rating want to reach the desired performance value calculation points.

  • Predictor

In the contest page point to open the sidebar will appear Predictor, can enter the ranking of the match performance points and Rating calculated value.

    Rank rich interface

All participants of performance points and expected values ​​are displayed in the Rating Standing interface.

2.AtCoder Submission Status

A clear view of the results and the number of answers submitted test data AtCoder.

3.AtCoderDarkTheme

Night mode provides an interface to AtCoder. Very unfortunately, until now, there has not been any human Atcoder write plug-in CSS style, so now only use night mode JavaScript scripting achieve.

4.AtCoderUserSearchForm

Add user search button on the top bar, find the user is very convenient.

Selection of examples

AtCoder Beginner Contest 112 C – Pyramid

Title Description

In ancient \ (Snuke \) in the Kingdom, there is a used to strengthen \ (AtCoder \ \ Inc. \) president \ (Takahashi \) the authority of the pyramid.

Coordinates of the center of the pyramid is \ ((Cx, Cy) \), a height \ (H \). Height around the coordinate point \ ((X, Y) \) of \ (max (H- | X-Cx | – | Y-Cy |, 0) \).

Aoki explorers conducted a survey to determine the center coordinates and the height of the pyramid. As a result, he received the following information:

\ (Cx \), \ (Cy \) is \ (0 \) to \ (100 \) integer between (including), \ (H \) is not less than \ (1 \) integer.
    In addition, he won \ (N \) messages. The first \ (i \) message is: “point \ ((xi, yi) \) height is \ (hi \).”
    This is sufficient to identify the coordinates of the center and the pyramid height. These values ​​are found by the above tips.

Sample input and output

Input # 1

4
2 3 5
2 1 5
1 2 5
3 2 5

Output # 1

2 2 6

Sample interpretation

In this case, center coordinates and height may be identified as \ ((2, 2) \) and \ (6 \).

Input # 2

2
0 0 100
1 1 98

Output # 2

0 0 100

Sample interpretation

In this case, center coordinates and height may be identified as \ ((0,0) \) and \ (100 \).
    Note, known \ (Cx \) and \ (Cy \) is an \ integer between \ (100 \) (0 \).

Input # 3

3
99 1 191
100 1 192
99 0 192

Output # 3

100 0 193

Data scope and limitations

  • \(0≤N≤100\)
  • \(0≤x_i,y_i≤100\)
  • \(0≤h_i≤10^9\)
  • The coordinate input will not be repeated;

    Center coordinates and height can be uniquely determined.

Thinking

By observing the subject, intuition tells us direct solution is not so easy, so we change the ways of thinking, that is to enumerate all the possible answers to determine whether the meaning of the questions.

Enumeration \ (Cx \) and \ (Cy \), determined by known point height \ (H \), determines whether the conditions are all known to meet the requirements. Time complexity \ (Θ (n ^ 2) \).

Code

#include
#include
#include
using namespace std;
int n,F,x[101],y[101],h[101];
inline bool check(int X,int Y,int H){
    for(register int i=1;i<=n;i++)if((((H-abs(X-x[i])-abs(Y-y[i]))<0)?0:H-abs(X-x[i])-abs(Y-y[i]))!=h[i])return false;
    return true;
}
int main() {
    scanf("%d",&n);
    for(register int i=1; i<=n; i++) {
        scanf("%d%d%d",&x[i],&y[i],&h[i]);
        if(h[i]!=0)F=i;
    }
    for(register int i=0; i<=100; i++) {
        for(register int j=0; j<=100; j++) {
            if(check(i,j,abs(i-x[F])+abs(j-y[F])+h[F])){
                cout<

AtCoder Regular Contest 103 E - Tr/ee

Title Description

You will get a length \ (n-\) a \ (01 \) string \ (s \). Determining whether or not there is a task meeting the following conditions containing \ (n-\) tree vertices.

1. Vertex number is (1,2,... , n).

2. Side number is (1,2,... , n-1), and edges (i) connect points (ui) and points (vi).

3. If \ section \ (i \) (s \) is the character \ (1 \), then the size may be obtained as \ (I \) by deleting an edge from the tree of connected components.

4. If \ section \ (i \) (s \) is the character \ (0 \), can not be deleted from any one side of the tree is obtained by connecting the component size \ (I \) a.

If there is a tree, a tree is constructed such. Otherwise the output \ (--1 \). If the data of multiple solutions, any one can be output.

Sample input and output

Input # 1

1110

Output # 1

1 2
2 3
3 4

Input # 2

1010

Output # 2

1 2
1 3
1 4

Input # 3

1111

Output # 3

-1

Data scope and limitations

  • \(2≤n≤10^5\)

Thinking

Obviously, if and only if the following three conditions solvable:

  • \ (S_1 = 1 \) (obtained can delete any leaf node containing only \ (\ point communication component 1));

  • \ (S_n = 0 \) (delete any edge is obtained containing only the largest \ (n-1 \) points connected component);

  • \ (S_i = s_ {n-i} \) (complementary two connected components).

Then, we can discover through drawing, tree diagram connected to several chrysanthemum form of what we want answers, this tree is also known as caterpillar (Caterpillar Tree).

Provided string \ (S \) in \ Number (1 \) of \ (k \), configured \ (1 \) length of \ (K \) array \ (X \) satisfies \ (s_ { x_i} = 1 \), then we ask the caterpillar to satisfy the following properties.

  • Caterpillars length of \ (k + 1 \), i.e., the diameter of the tree \ (k + 1 \);

  • Body of caterpillar \ (i (2≤i≤k) \) has a long point \ (x_i-x_ {i-1} -1 \) foot.

Code

#include
#include
using namespace std;
string s;
int cnt=1,root,lst;
int main(){
    cin>>s;
    if(s[0]=='0'||s[s.length()-1]=='1'){
        puts("-1");
        return 0;
    }
    for(register int i=0;i<(s.length()>>1);i++){
        if(s[i]!=s[s.length()-i-2]){
            puts("-1");
            return 0;
        }
    }
    for(register int i=0;i

By these two questions we can roughly understand the title match AtCoder not too profound examination of the algorithm, but the bigger test of thinking difficult topic. If there is at least an element of the above interest you, then it quickly registered a AtCoder account, open your AK journey!

Sahua end, thank you!

If there are errors or omissions in the text please point out as soon as possible, thank you!

Leave a Reply