atcoder_official's blog

AtCoder Beginner Contest 319 Announcement
By atcoder_official, history, 3 weeks 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

»
3 weeks ago, # |
  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 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it +11 Vote: I do not like it

    Number of Tasks: 8

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

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

Something is wrong!

8 problems, but 100-200-300-400-450-550-575.

Emm...

Are you sure if it is a mistake?

→ Reply
»
3 weeks ago, # |
  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 weeks ago, # ^ |
      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 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Number of Tasks:8

So where is the 8th problem???

→ Reply
»
3 weeks ago, # |
  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 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Look at the score should not?

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I will do three questions.

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

I hope it can be simpler this time.

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

it's better than a well-known problem in ex.

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

But only I can't connect to AtCoder?

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

What the hell is problem statement of C?

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

    Same problem, if the cells are given completely random then, total possibilities will be 9! and disappointments would be a small fraction. If someone understood or solved it correctly, please write in this thread.

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

B is so hard.

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

The atcoder crashed...

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

dude can you explain qC

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

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

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    This question is very vague.

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How we're calculating the probability tough!

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        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 weeks ago, # |
  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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    Agree.The description of the title of this question is terrible.I don't know the origin of 2/3 at all!

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

Literal False hope

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

After reading C:


wth-is-c

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

The Problem statement and explanation for C is too bad

→ Reply
»
3 weeks ago, # |
  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 weeks ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    I think the explanation is quite clear but the problem is too hard for C.

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

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

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

    how F please

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

      you can do bitmask dp (bitmask denotes consumed medicines), notice that it's always optimal to defeat any enemy as soon as you can defeat it

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Thank you very much! I didn't see the medicine constraint during the contest :(

        → Reply
  • »
    »
    3 weeks ago, # ^ |
      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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How did you do E?

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
        ← 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 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Could you provide with a proof for this?

          → Reply
          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
            ← 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 weeks ago, # ^ |
            ← 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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Hint 1
        Hint 2
        → Reply
»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Can anybody explain C ?

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

    just find all valid orders by brute forcing over all permutations of length 9

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

      Doing just as you suggested but getting WA on sample testcase #2. Any idea what is wrong with my code?

      #include <bits/stdc++.h>

using namespace std;
using i64 = long long int;

void testcase() {
  vector<vector<int>> a(3, vector<int>(3));
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
      cin >> a[i][j];

  vector<int> p(9);
  iota(p.begin(), p.end(), 0);

  int total = 0, favourable = 0;

  do {
    bool ok = 0;
    vector<vector<int>> rows(3);
    vector<vector<int>> columns(3);
    vector<vector<int>> diagonals(2);

    for (int i = 0; i < 9; i++) {
      int x = p[i] / 3, y = p[i] % 3;
      rows[x].emplace_back(a[x][y]);
    }

    for (int i = 0; i < 9; i++) {
      int x = p[i] / 3, y = p[i] % 3;
      columns[y].emplace_back(a[x][y]);
    }

    for (int i = 0; i < 9; i++) {
      int x = p[i] / 3, y = p[i] % 3;
      if ((x == 0 && y == 0) || (x == 1 && y == 1) || (x == 2 && y == 2))
        diagonals[0].emplace_back(a[x][y]);
      else if ((x == 0 && y == 2) || (x == 1 && y == 1) || (x == 2 && y == 0))
        diagonals[1].emplace_back(a[x][y]);
    }

    for (int i = 0; i < 3; i++)
      if (rows[i][0] == rows[i][1] && rows[i][1] != rows[i][2])
        ok = 1;

    for (int i = 0; i < 3; i++)
      if (columns[i][0] == columns[i][1] && columns[i][1] != columns[i][2])
        ok = 1;

    for (int i = 0; i < 2; i++)
      if (diagonals[i][0] == diagonals[i][1] &&
          diagonals[i][1] != diagonals[i][2])
        ok = 1;

    total++;
    favourable += 1 - ok;
  } while (next_permutation(p.begin(), p.end()));

  double ans = 1.0 * favourable / total;
  cout << setprecision(10) << ans << "\n";
}

int main() {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif

  int T = 1;
  // cin >> T;
  for (int t = 1; t <= T; t++) {
    testcase();
  }

  return 0;
}
      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D?

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

    Binary Search

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

      In D, what if the order of the words didn't matter, so would that problem be solved by dp ? How would we implement the solution in that case ?

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

    D can be solved using binary search, choose l as 0 and r as 1e9.

    Then apply binary search, with capacity as (l+r)/2, for the given capacity check if we can fill all words in m or less lines.

    finally print value of left.

    Basically capacity represents the best values for columns against m rows.

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

      include

      include

      using namespace std;

      bool checkIfPossible(vector&a , long long mid , int m){

      int n = a.size();
long long int sum = 0;
int c = 1;

for(int i = 0;i<n;i++){
    sum = sum + a[i] + 1;
    if(sum-1 > mid){
       c += 1;
       sum = a[i]+1;
    }
}
return c <= m;

      }

      void solve(){ long long n , k; cin>>n>>k; vectora(n); for(int i = 0;i<n;i++){ cin>>a[i]; }

      long long low = 0;
long long  high =  1000303000000000 ;

while(low<=high)
{

    long long  mid = (low + high)/2;
    if(checkIfPossible(a , mid , k)){
       high = mid-1;
    }
    else{
       low = mid+1;
    }
}
cout<<low<<"\n";

      }

      int main() { #ifndef ONLINE_JUDGE freopen("./../input.txt","r",stdin); //file input.txt is opened in reading mode i.e "r" freopen("./../output.txt","w",stdout); //file output.txt is opened in writing mode i.e "w" #endif int t; // cin>>t; t = 1; while(t--){ solve(); } }

      For Question D . What is wrong with my solution ? What am i doing wrong ?

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

        what if single element value is greater than mid?

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

          Thank you .Yes , that was the mistake

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

            Hey can you repaste the correct code here please,considering the case: if (word_width > capacity) { return false; // Single word cannot fit within capacity }

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

              include

              include

              using namespace std;

              bool checkIfPossible(vector&a , long long mid , int m){

              int n = a.size();
long long int sum = 0;
int c = 1;

for(int i = 0;i<n;i++){
    if(a[i]>mid){
       return false;
    }
    sum = sum + a[i] + 1;
    if(sum-1 > mid){
       c += 1;
       sum = a[i]+1;
    }
}
return c <= m;

              }

              void solve(){ long long n , k; cin>>n>>k; vectora(n); for(int i = 0;i<n;i++){ cin>>a[i]; }

              long long low = 0;
long long  high =  10003030000000000 ;

while(low<=high)
{

    long long  mid = (low + high)/2;
    if(checkIfPossible(a , mid , k)){
       high = mid-1;
    }
    else{
       low = mid+1;
    }
}
cout<<low<<"\n";

              }

              int main() { #ifndef ONLINE_JUDGE freopen("./../input.txt","r",stdin); //file input.txt is opened in reading mode i.e "r" freopen("./../output.txt","w",stdout); //file output.txt is opened in writing mode i.e "w" #endif int t; // cin>>t; t = 1; while(t--){ solve(); } }

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

    Consider using a dichotomous answer for this question.

    Regarding the proof of monotonicity for this question: since the wider the width of the display, the more width can be displayed in a line, the fewer lines are needed for the display (the total number of words remains the same). So the width of the monitor and the number of lines needed to display it** have a monotonically decreasing relationship**, so you can use dichotomization.

    Dichotomize enumerates the width of the display $$$w$$$, and then calculates the minimum number of lines needed to display a word with a width of $$$w$$$, if the number of lines needed is less than or equal to $$$m$$$, then it meets the requirement, otherwise it doesn't meet the requirement.

    How is this calculated?

    If the width of the display $$$w$$$ is less than the maximum width of the word $$$mw$$$, it means that a word can not be put into the display, obviously does not meet the requirements.

    So that $$$sum $$$ that the current line has been used for how much width, $$$cnt $$$ that the current use of how many lines, an enumeration of the length of the word $$$ l_i $$$, if the current width plus a space and $$$l_i $$$ the length of more than $$$ w $$$ that the current line can not be put in the word, the need to open a new line, so that $$$cnt $$$ plus $$$ 1 $$$, and so that $$$sum $$$ equal to $$$ l_i $$$, otherwise $$$sum $$$ plus $$$ l_i $$$ and $$$ l_i $$$ and $$$ l_i $$$, otherwise $$$ sum $$$ plus $$$l_i$$$ and the length of a space.

    Time complexity: $$$O(\log n)$$$ for bisection, $$$O(n)$$$ for one calculation, $$$O(n \log n)$$$ for overall time complexity.

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

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

→ Reply
»
3 weeks ago, # |
  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 weeks ago, # |
  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 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Even with mass cheating, these losers could solve only the easiest three.

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

      Even i was able to solve only the easiest 3, it took me ages to realise solving c wasnt worth it, but i clearly dont deserve a rank of 6000 when it should be in range of 3000-4000

      → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    wtf why do those Indian cheaters start invading AtCoder too?

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

Can someone explain the statement of C?

→ Reply
»
3 weeks ago, # |
  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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same with me.The problem statement should be more clear.

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

    I considered the 9! factorials ways of choosing the grid cells. For every such order, I made a 3X3 grid from them, and then checked whether the permutation was valid by considering the 16 possible unique lines. But I'm getting a much lower answer for sample 1. Can you please take a look at what I'm doing wrong? submission

    → Reply
    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What do you mean you checked "whether the permutation was valid" ? Aren't all permutations valid ? They are just a way of picking up the picking up the elements from the grid. I think the real question is whether a permutation is "disappointing" for Takahashi.

      → Reply
      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, that's what I meant really, it's not valid, it's disappointing.

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

Yeah, C was a total buzz kill today. I wonder how much clearer was the Japanese description (for the Japanese speakers)...

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

G is even easier than F

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

can someone explain the solution for problem E?

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

I think this can be called a ABC319C disaster.

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

What is C? Why is C?

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

atcoder_official Editorials when?

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

Why there's no English Editorial?

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

can someone explain the sol of G? i'm thinking about bfs but i can't seem to optimized it.

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

When will the English Editorial be released

→ Reply
»
3 weeks ago, # |
← 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any problem related to G? Very thanks!

→ Reply
»
3 weeks ago, # |
  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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I modified your code a bit. The submission is here: https://atcoder.jp/contests/abc319/submissions/45437738

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

      Thanks! Can you help me understand why the modified code works and the original not? As far as I understand you increase the lower bound so there will be less checks during the binary search so it could improve the running time but it shouldn't effect the correctness of the program but for some reason it does.

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

C is the most shit problem

→ Reply
»
3 weeks ago, # |
  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 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I used the same solution as yours.I found I got 3 TLE.So I break when it will up to 2 seconds with No.Then I got 2 WA.So I change to output Yes or No randomly with the one-third probability outputs No,otherwise outputs Yes.Then I pass the task with judging 9 times in all.submission(After 7 times,Oh god,I found I had forgot to add srand(time(0)); at first!)

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      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 weeks ago, # ^ |
        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 weeks ago, # ^ |
        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 weeks ago, # ^ |
          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 weeks ago, # ^ |
            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 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I got the same WA x 1 (my submission) for problem F and I would be happy to know what's wrong with my solution.

    Are there any special cases or I misunderstood the statement of problem F?

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

      That's strange.My best friend WA on there too.Why doesn't Atcoder publish the testcases?

      → Reply
»
3 weeks ago, # |
  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 weeks ago, # ^ |
      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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can u please explain the approach..i am not able to understand why the state would repeat and why taking lcm is of any help

      Thank you!

      → Reply
»
3 weeks ago, # |
← 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 weeks ago, # |
  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
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I read the editorial for problem C and couldn't understand it. Why are only 8 ways being considered instead of 16 total ways to form a line? And editorial doesn't consider that the 3 cells can all be equal in which case we don't have to count. Granted that they can't be equal in a line in the given array, but when re-arranged, that very well can be the case.

I do not understand why my submission is wrong. Please help :pepecry:

→ Reply