atcoder_official's blog

AtCoder Beginner Contest 319 Announcement
By atcoder_official, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 319.

The point values will be 100-200-300-400-450-550-575.

Until ABC 318, we used 8 problems per contest because there were many difficult tasks we wanted to use in ABCs. Since we have used most of them, from this ABC, we will use 7 problems per contest.

The difficulty of problems A-F will not be changed. The range of difficulty of new problem Gs will be wider, some of them can be as easy as current problem Gs, while others can be as hard as current problem Exs. Please check the point values of each contest for more accurate estimation of difficulties.

We are looking forward to your participation!

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

Comments Comments (80)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it +93 Vote: I do not like it

Number of Tasks: 8

from this ABC, we will use 7 problems per contest.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

It says there will be 7 problem in ABC, but in this blog, it says Number of Tasks: 8.

So WHY?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it -9 Vote: I do not like it

    Until ABC 318, we used 8 problems per contest because there were many difficult tasks we wanted to use in ABCs. Since we have used most of them, from this ABC, we will use 7 problems per contest.

    It means ABC319 will be 7 problem.

    → Reply
»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

Number of Tasks:8

So where is the 8th problem???

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

This game only has 7 tasks, I don't know if this means the overall difficulty has increased

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    The post said:

    The difficulty of problems A-F will not be changed. The range of difficulty of new problem Gs will be wider, some of them can be as easy as current problem Gs, while others can be as hard as current problem Exs.

    → Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I hope it can be simpler this time.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +41 Vote: I do not like it

What the hell is problem statement of C?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

The atcoder crashed...

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

dude can you explain qC

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

I don't have any ideas about C-False Hope.

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    You can consider all permutations of the order Takahashi sees the grids, check if it satisfies the condition easily. I agree the statement is not so clear, and that reading is the hardest part in solving the problem xd.

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    How we're calculating the probability tough!

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      wdym? isn't the probability equal to "total number of permutations that satisfy condition"/(1*2...*9) ?

      → Reply
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

The difficulty of problems A-F will not be changed

But I think it's harder than usual

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

C has the worst problem statement I've ever seen.

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it -33 Vote: I do not like it

.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Literal False hope

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

After reading C:


wth-is-c

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

The Problem statement and explanation for C is too bad

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Task C was really a disaster.

Never seen such a bad description of a problem ,Even the Explanation of test cases are not clear.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

Am I the only one who thought E >>> (F and G)

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    how F please

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

    Probably because $$$G$$$ is a kinda-standard problem?

    But I think E is easier than F. $$$1\leq P_i\leq 8$$$ gives it away.

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      How did you do E?

      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
        ← Rev. 3  
        Vote: I like it +1 Vote: I do not like it

        Consider lcm(1 ... 8) = 840, so all the starting time that have the same value after mod 840 has the same min time to transport from station 1 to n. Just preprocess the min time of station transportation starting at time x(mod 840) and answer the questions after this.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          Could you provide with a proof for this?

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, hide # ^ |
            ← Rev. 2  
            Vote: I like it 0 Vote: I do not like it

            sort of obvious rly... I am really sorry, but I dont know how to put the explanation into mathematical terms :(

            but maybe you can figure out by examining all the time mod p[i] after visiting station i and you will see.

            → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, hide # ^ |
            ← Rev. 2  
            Vote: I like it 0 Vote: I do not like it

            Let's say you have $$$2$$$ buses having $$$p$$$ $$$=$$$ $$$[5, 6]$$$ and $$$t$$$ $$$=$$$ $$$[3, 4]$$$

            If you reach the first bus stand at $$$0$$$, you can take the first bus at $$$0$$$, reach the bus stop after $$$3$$$ units of time, start bus two at $$$6$$$, and reach the final bus stop at $$$10$$$.

            You can find the same for different values when you reach the first bus stop. It will be different for starting times (in this case) $$$6, 11, 16, ...$$$

            Now try to find the bus travel time if you reach the first bus stop at time equal to $$$lcm(5, 6) = 30$$$. You'll realize that the position of buses is exactly the same as it was at the time $$$= 0$$$. So the value is same and this pattern will continue.

            → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it
        Hint 1
        Hint 2
        → Reply
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Can anybody explain C ?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

how to solve D?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

First five problems without C, how awkward, and bad problem.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Laugh at A, get confused about B, and then give up understanding at C.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I request Atcoder to take some action against a mass group whose user name starts with "klu". These all students belong from a certain university and have clearly mass copied, this drastically pushed the ranks.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone explain the statement of C?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

In problem C,Takahashi can see numbers in each cell in 9! different ways and we have to calculate valid permutations.A valid permutation is one in which for each row,column and diagonal which consists of two same values and one different value,he must visit the cell with different value before atleast one of the other two cells with same value. After that , the implementation is pretty much brute force.

But the definition of valid permutation (not disappointed) was not clear at all atleast for me personally, it took me 40 min to understand what question is asking us to do and 7 odd minutes to implement it.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

G is even easier than F

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

I think this can be called a ABC319C disaster.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

What is C? Why is C?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Why there's no English Editorial?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

When will the English Editorial be released

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it -8 Vote: I do not like it

How to solve G? I used simple BFS with o(n^2*log(n)) solution using sets and got TLE.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is there any problem related to G? Very thanks!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone help me understand why my code for problem D doesn't pass all the tests? https://atcoder.jp/contests/abc319/submissions/45406059

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

C is the most shit problem

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I have a strange solution for F:

Enumerate over all possible visiting orders of vertices with $$$t_i=2$$$. For each permutation, consider the following greedy strategy:

  • Find a monster you can reach with the minimum strength. If you can't defeat it, take the reachable medicine with the highest priority (determined by the visiting order).

Repeat this step, until all monsters are cleared or there is no medicine available.

The overall time complexity is $$$\mathcal O(m!\times n\log n)$$$, where $$$m$$$ is the number of medicine vertices. So it can't fit in the time limit, but actually with some simple optimizations it ran in $$$800\mathrm{ms}$$$ (maybe can be hacked?).

However, I got WAx1 (submission). Did I make a mistake in the program or the idea is wrong?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Oh,I found another one.Using random_shuffle instead of next_permutation can get a higher probability to pass this task.I tried 3 times,and they all passed.

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Thanks. But my code tried all the permutations, without any randomization. I expected TLE, but why does it get WA? Could you please have a look at my code?

      → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Some optimizations:

      • use __gnu_pbds::priority_queue instead of std::priority_queue for a better constant factor
      • if $$$(\text{the current strength})\times (\text{the product of all the available }g_i)\ge (\text{maximum monster strength})$$$, then print Yes.
      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        I'am in China now,I can't download the testcase.But you can try it.And I found another thing:I'am wrong,I can reach the subtree of a medicine without taking it.But I passed!

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          Maybe the test cases are too weak?

          And the test cases for ABC319 are't published yet (in fact, the latest public test cases from AtCoder is that of ABC311).

          → Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anyone give proof for E, how time taken for t1 and t2 will be same if t1%840==t2%840

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    $$$lcm(1,2,3,4,5,6,7,8) = 840$$$

    So the state of the bus stops repeats after every $$$840$$$ unit of time.

    → Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +16 Vote: I do not like it

In the F，the data may be weak

5

1 1 1 1

2 2 0 5

3 1 1 1

4 1 15 1

My AC code can be hacked

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    My submission https://atcoder.jp/contests/abc319/submissions/45439007

    And the reason is that I don't consider the limit of ti=2 must take the medicine

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    it was originally came up with DJ2006 :-)

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it +11 Vote: I do not like it

      but it is not important. plz add this data into the problem, thx.

      → Reply
  • »
    »
    21 month(s) ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I was looking at the submission of hitonanode, which seemed to more or less implement the algorithm described in the second editorial, the correctness of which I had tried to understand and prove. Eventually, to my great surprise, I constructed the case

    6
1 2 0 3
1 2 0 2
2 1 3 3
2 1 15 1
3 1 2 2

    for which the answer should be Yes, on which the aforementioned submission outputs No.

    In my drawing of the corresponding tree below, the two multipliers are circled.

    As for why it's Yes:

    1 -> 2 -> 3 results in 1*3+3 = 6, then 6*2 = 12, 12+2 = 14, 15 cannot be defeated. However, if one does 1*2 + 2 = 4, then 4*3 = 12, then 12+3 = 15, then 15 can be defeated.

    Afterwards, I checked that the submissions of some other top contestants also output for this Yes.

    I had thought of private messaging hitonanode about this, but then, I felt a bit too shy to do so to such a highly rated coder for something as relatively unimportant as this. It is also not the first time I've seen solutions with more minor bugs AC. However, I do not think it is impossible that hitonanode or someone else could tell me thru what channel to submit an after contest case. Another thought is that maybe maspy, with whom I once had a minor exchange on GitHub, could point me to the right direction?

    → Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I'm really delighted to see that I forgot the $$$\pmod {998244353}$$$ in G. That's why I got WA.

→ Reply