atcoder_official's blog

By atcoder_official, history, 12 months ago, In English

We will hold HHKB Programming Contest 2023(AtCoder Beginner Contest 327).

We are looking forward to your participation!

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

| Write comment?
»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Hello.I wish luck to everyone in this contest!

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

AtCoder isn't working? It shows 403 on my browser. Is it my problem?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is working,but the problems are to difficult!

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i do a,b,c but d to g is too hard

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        Actually d is very simple.

        But g is also too hard for me.

        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          $$$G$$$ is hard for many GMs as well.

          well, don't discuss anything before this contest ends!

          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Hey, This is my first contest. Where can i find the answers after the contest is finished? I heard atcoder contests are suitable for beginners. But, this is too overwhelming!!

            • »
              »
              »
              »
              »
              »
              »
              12 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Wait for the end of the contest!

              When the contest ends a button for editorial appears at each problem page.

          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            How u solved E?

            • »
              »
              »
              »
              »
              »
              »
              12 months ago, # ^ |
              Rev. 2   Vote: I like it +1 Vote: I do not like it

              with dp!

              If you observe in the given equation only the numerator for the first term makes any sense (changes for different sizes of subsequence).

              So we can find the maximum value of a subsequence of length K (for K = 1 to N)

              we will use this dp value as a numerator of the first term and the rest can be substituted easily and we can find the maximum ans over all subsequences of different lengths!

              My submissions

        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          E is even more simpler than D

          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            But I spent 5 mins on D, and 50 mins on E qwq

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is problem E a dp Problem ?

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why finding cycle in D doesnt work? it failed on 3 test cases

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    becoz its bipartite graph problem

    • »
      »
      »
      12 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      i implement detection of cycle graph as well , i got 24 tests AC and only 3 WA.

      can you give a counter example where detection of cycle graph is not working ?

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        cycle will not work if you have cycle of odd length

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Just check for bipartiteness for the nodes given in the sequences for each component also make a check for S[i] == T[i] as that also leads to a no answer. Nothing more required.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    In D, you have to tell if the graph formed by the edges $$$(X_{A_i}, X_{B_j})$$$ is bipartite or not. Note that, even cycles are also bipartite graphs.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    were you finding cycles of all lengths or only odd lengths ?

  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    it works for even cycles (and not for odd ones) so just because a cycle exists doesn't mean the ans should be no

»
12 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I think F is a famous problem in Luogu named "Stars in the Window".

Problem's link:https://www.luogu.com.cn/problem/P1502.

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve E?

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does my D-question program have a test point wrong? I treat a[i] and b[i] as two nodes of a graph to determine whether they are bipartite graphs. https://atcoder.jp/contests/abc327/submissions/47266143

»
12 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Why does this give wrong answer on 3 cases? submission

»
12 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Lesson learnt. On AtCoder, I can try unordered_map when map causes TLE. I didn't do so so far because on Codeforces, unordered_map is subjected to hacking. On AtCoder, there is no such concern.

My TLE solution on E with map: submission

My AC solution on E with unordered_map: submission

I ended up replacing the map by vector during contest though.

»
12 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

G need 30 rows, but A117279 only provides 25 rows....

»
12 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Same :(

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In task E, can someone explain why picking maximum K elements for each k greedily doesn't work ????

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Order of the performance numbers matters. It is a penalty when the performance numbers show a downwards trend.

»
12 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

In G — Many Good Tuple Problems Editorial(English Version)

g(n,m):= (the number of simple connected graphs with n vertices and m edges, where each vertex is painted either white or black, and no edge connects vertices with the same color).

should be

h(n,m):= (the number of simple connected graphs with n vertices and m edges, where each vertex is painted either white or black, and no edge connects vertices with the same color).

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And I think that the calculation formula for $$$f(n, m)$$$ should be

    $$$f(n,m) = \dfrac{h(n,m)}{2} + \sum\limits_{1 \le i < n}\sum\limits_{0 \le j \le m}\dbinom{n-1}{i-1}\dfrac{h(i, j)}{2}f(n -i, m - j)$$$
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      I think you are right cause C(n-1,i-1) are not symmetric about n. Maybe just a typo.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also 'b(M,k) equals M! times the Stirling number of the second kind, S(M,k)' should be k! times S(M,k) right?

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can some one point out what is wrong in my code . It's failing on 4 test cases.Your text to link here...

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E's solution is dp, right guys?

»
12 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

HELP, Anyone can explain the F solution? Editorials become somewhat complex to understand. Just explain the part, what you are storing, updating, query..... in the data structure, and why.