Marco_L_T's blog

By Marco_L_T, 6 years ago, In English

Hello, Codeforces!

I'm quite excited to invite you to participate in Codeforces Round #447 (Div.2 Only) which will be held on November 19 16:55 MSK.

All five problems are created by Zerui Cheng (Marco_L_T), Bingheng Jiang (NOIRP), Yiming Feng (whfym). And it's our first round on Codeforces. We want to show our great thanks to our school The High School Affiliated to Anhui Normal University and our coach Guoping Ye in competitive programming training.

And we also want to show our great appreciation to Mikhail Krivonosov (mike_live), Gleb Lobanov (Glebodin), Weihao Zhu (Tommyr7), Shiqing Lyu (cyand1317) for testing the problems, to Nikolay Kalinin (KAN) for coordination and to Mike Mirzayanov (MikeMirzayanov) for the fantastic Codeforces and Polygon platforms. The round can't be realized without their great help.

The contest will consist of 5 problems and you'll be given 2 hours to solve them. As usual, the scoring will be announced shortly before the start of the contest.

The contest is rated for Div. 2 contestants. And the same as before, Div. 1 contestants can take part out of competition.

Wish everyone high rating and bugless code!

See you on the leaderboard!

Clarification: In the mail, it reads that the duration is 2 hours and 30 minutes and it'll contain 6 problems. There's a mistake. The duration of the contest is 2 hours and there will be 5 problems.

UPD1: Scoring: 500-1000-1500-2000-2500

UPD2: The contest is finished! Have fun hacking!

UPD3: The system test is finished! Congrats to the winners!

And do you find something interesting in the statements,especailly for Chinese contestants?

Div.1 & Div.2:

  1. fateice_ak_ioi (solved all the problems and got 22 hacks)

  2. peace (solved all the problems and got 10 hacks)

  3. dreamoon_love_AA

  4. KrK (solved all the problems)

  5. Benq (solved all the problems)

Div.2:

  1. fateice_ak_ioi (solved all the problems and got 22 hacks)

  2. peace (solved all the problems and got 10 hacks)

  3. ec24 (made 16 hacks)

  4. daaaaaaaaaaaaaaaaaaa

  5. QYitong1

UPD4: Maybe you're complaining that there're too many hacks and the pretests are so weak,but it's our intention to do so. We regard hacks as a very important part and a feature of Codeforces.Do you agree?

UPD5: Editorial

Maybe B and C are a little harder than before,we'll be cautious about this next time.

Hope you have fun in solving the problems and hacking!

See you next time!

Full text and comments »

  • Vote: I like it
  • +280
  • Vote: I do not like it

By Marco_L_T, history, 7 years ago, In English

I wrote a solution to Problem G of Educational Round 27 and it passed all the tests.Later I found that I assumed that the graph contained at most 100000 cycles but it was wrong.So I generated a test case with more than 100000 cycles to hack my solution. However,it wasn't accepted by the hacking system because my test case is larger than 256KB. So could anyone help me with the issue? Thanks a lot!

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it

By Marco_L_T, history, 7 years ago, In English

I wrote the following code for Div.1 C in tonight's contest in practice,which is just a simple mountain-climbing like strategy.

My submission

It's obviously not the intended solution of the problem.However,it passed all the tests,which was to my surprise.So,can anyone please provide some data that can hack my submission?Thank you!

Full text and comments »

  • Vote: I like it
  • +36
  • Vote: I do not like it

By Marco_L_T, history, 7 years ago, In English

I noticed that there existed a method to solve Codeforces 827A/828C like this:Submission

It ran really fast that it became one of the quickest solutions to this problem.However,when I opened the code,I found it was just a naive implemention only with some optimizations.

But if I gave the following data:

N=1000,

all the 1000 queries have the same string with length 1000 and k=1000,

the following numbers are 1,1001,....,999001,1000000,

the sum of all ki is 10^6 and the sum of string length is 10^6,which satisfies the data range.

In this condition,the code will have up to 10^9 times of calculation and I don't think it can pass within 2 seconds.

So can anyone please if it's the expected solution to the problem? Thanks!

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it

By Marco_L_T, history, 7 years ago, In English

Reyna's submission of Problem A in today's contest got Wrong Answer verdict.As Reyna is very good at coding,I felt a little strange.However,when I looked at the detailed feedback,it showed that it couldn't find a file,which I never saw before.More strangely,I re-submitted Reyna's code and then got AC verdict.

Submission

So,could anyone tell me what the reason was or it was a bug in Codeforces? Thanks!

UPD: The issue is fixed now.

Full text and comments »

  • Vote: I like it
  • +57
  • Vote: I do not like it

By Marco_L_T, 7 years ago, In English

I've been working on a problem on graph,but can't come up with a solution of it.

Here is the problem.

John has N (N<=10000) dogs.Now they're going to cross a river.However,there's only a boat that can only carry one person and one dog each time.However,some of the dogs hate the others so much that they'll fight if John isn't around them. M (M<=25000) constraints describe the situation.Each is described as (x,y,z),which means the dogs with numbers x,y,z will fight with each other if John is away.But they won't fight if one of them is at the opposite bank with the other two.

Now you are asked to determine whether there is a way to send all the dogs to the other bank of the river without fighting.You don't need to print the detailed method,which means you just need to print "yes" or "no".Remember John must be on the boat and the boat can only carry one dog each time.

Input:

On the first line , two numbers N and M.

From the second to the (M+1)th line,each line has three numbers (x,y,z),which describe a constraint.

Output:

A single line,containing "yes" or "no"

Sample Input 1:

6 9

1 2 3

1 2 4

1 2 5

1 2 6

1 3 6

1 4 6

1 5 6

1 3 4

1 4 5

Sample Output 1:

yes

Sample Input 2:

6 10

1 2 3

1 2 4

1 2 5

1 2 6

1 3 6

1 4 6

1 5 6

1 3 4

1 3 5

1 4 5

Sample Output 2:

no

I translate the problem on my own.Sorry for my poor English.

Can anyone tell me the solution to the problem? Thanks a lot!

Full text and comments »

  • Vote: I like it
  • +19
  • Vote: I do not like it