chokudai's blog

HHKB Programming Contest 2022（AtCoder Beginner Contest 235） Announcement
By chokudai, history, 3 years ago, In English

We will hold HHKB Programming Contest 2022（AtCoder Beginner Contest 235）.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

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

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

Once again, why is problem H called Ex?

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

    Probably means extra, you dumbass.

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

      What's better?

      • A B C D E F G H
      • A B C D E F G Ex
      → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +15 Vote: I do not like it

    A friend (jokingly) told me it probably stood for, "Extra Garbage Data Structure"

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

      Problem Ex is not garbage imo, it's usually very educational. I learned a lot from problems Ex.

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

        That's fair! The problems do seem nice, if a bit beyond my abilities

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

    Extra
    Example
    Exercise
    External
    Extended
    Excellent
    Exhausting
    Extraordinary

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

How to solve E efficiently?

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

    Solve offline. Apply normal MST algo for graph with all m normal edges and q query edges combined. The difference is to not actually add the edge if its a query edge. Solution

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

    Store the edges given, in set with ind=-1
    Store the edges of queries, in set with index of query.
    Now apply Kruskal or Prim's and whenever you encounter a query edge check if this edge would have been added or not and store the answer for that index by using vector of strings.
    Finally print that vector.
    Submission

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

    Think of kruskal algorithm used to compute the MST of a graph:

    You sort edges by increasing order of weights and you use an edge if and only if it unites two nodes that are not already connected. So you can put all the edges in the same vector, sort them and keep uniting like if you were computing the MST of the graph.

    At any time when the current edge is a "query edge" you just check if it unites two nodes that are not already connected or not.

    See my code for more details: https://atcoder.jp/contests/abc235/submissions/28547346

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

    My solution:

    Build the MST of the original graph, then the answer for a query $$$(u, v, w)$$$ is Yes if and only if the maximum weight of an edge in the path from $$$u$$$ to $$$v$$$ on this MST is greater than $$$w$$$. So, now our problem has changed to: Given a tree and multiple queries $$$(u_i, v_i)$$$, report for each of them the maximum weight of an edge in the path from $$$u _i$$$ to $$$v_i$$$, which is easily solvable by Binary Lifting.

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

      This idea struck me at the very end, but couldn't implement it in time

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

What's the solution to problem F? I've come up with some sort of dp, and I guess it should work, but could someone point out the mistake?

The idea I used is that we can calculate the count of number such that first $$$i$$$ digits match and $$$(i+1)_{th}$$$ one is lower than the one in $$$N$$$. So I've precomputed the number of sequences of length $$$K$$$ for each set of digits using bitmask DP, as well as their sums and later use them in calculations. Here's the code and it's obviously got one issue which is discarding the elements with leading zeros. E. g. 01 is not a valid number for set of digits {0,1}. Can anyone help?

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

    I did some pretty similar DP.

    The states are: number of the digit, bitmask (to know which of the required digits have already been used) and a bool to know if my number if currently less or equal than n.

    Don't allow any leading zeroes (so in your base case don't use digit 0) and at any digit just add a new transition which is "creating" a newer digit already smaller than n:

    See my code for more details: https://atcoder.jp/contests/abc235/submissions/28560145

    Don't mind to tell me if anything is unclear :p

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

    My solution (although I couldn't submit it due to some bugs in my code) is the following:

    Let's say $$$sum(A)$$$ is the sum of all the elements in the set $$$A$$$. Let's also define $$$S_d$$$ as the set of numbers that don't have the digit $$$d$$$ on their decimal representation. Then, we're asked for $$$sum\left([1, n]- \displaystyle\bigcup_d{S_d}\right) = \frac{n(n+1)}{2} - sum\left(\displaystyle\bigcup_d{S_d}\right)$$$. The sum of that $$$union$$$ can be computed by inclusion-exclusion principle: We iterate through all the non-empty subsets of the given digits and for each of them, we can use digit-dp for computing the required sum.

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

Can D be solved with DP? If yes, can anyone share their code?

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

    +1

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

    D can be solved with something not that far from DP. Imagine a graph where each node is a number and you add an edge X->Y if you can reach number Y from number X. You start from number 1 and want the shortest path to get to node N. You have O(n) nodes and O(n) edges.

    Let me know if anything is not clear :)

    Here is my code: https://atcoder.jp/contests/abc235/submissions/28543245

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

    Yes, my very messy solution just uses recursive DP. With a little tweak to avoid infinite circular rotation (if we reach the same state, then bail out and return "infinity"): https://atcoder.jp/contests/abc235/submissions/28563863

    I initially tried to do rotations via integer arithmetic operations, but wasted a lot of time debugging it. Only at the last moment replaced this stuff with string manipulations and got an AC verdict. Premature optimization is the root of all evil...

    Edit: Now hacked by the "99_after_contest_00.txt" testcase :-)

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

Editorial of G:

"(plant 1 or more seedlings to the 1-st garden) and (plant 1 or more seedlings to the 1-st garden) and (plant 1 or more seedlings to the 1-st garden) …"

It this a typo, or what is the meaning of it?

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

Can someone help me with my code for E? It passes sample cases but gives WA verdict. I constructed the mst of the graph and for queries I did the following:

  • if u is ancestor of v, compare w with parent edge of v and the child edge of u that contains v.

  • if v is ancestor of u, same as above

  • compare w with parent edges of u and v.

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

    We could implement logic like "find max weight edge on path from u to v", and if that weight is bigger current query edge weight, then the query edge weight would have been used.

    But to find max weight edge on path from u to v in the MST, we need more that only compare the weight to the parent edge. It can be done in example with binary lifting.

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

      right. thanks.

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

      yeah I implemented it and honestly it was not fun to do.. In my defense it was my first time implementing LCA with binary lifting and I wrote one line incorrectly.

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

Please help me in finding the mistake in E..

Is my approach wrong? https://atcoder.jp/contests/abc235/submissions/28561004

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

Can someone please tell me why I am getting a runtime error on this solution for problem E? I made 6 tries during the contest but wasn't able to find my mistake.

https://atcoder.jp/contests/abc235/submissions/28555671

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

    Maybe it is actually a memory error, caused by using several gig for all the dsu.

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

Problem E and F are all classic.

Also E and Link (in chinese) are the same.

Sorry to my poor English.

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

    ABC is educational it is normal to have classic problems.

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

In Question D, I used recursion and it seemed to pass ALL test cases except one. Can anybody guess which test case it would be. Here is my code. Thanks for the help in advance.

Also, There is no TLE or MLE in that test case.

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

    Your solution gives 9. My solution gives 6.

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

My solution for problem E:

Build an MST of the original graph.

Remove all other edges.

Use LCA with doubling technique.

Record the maximum weight of edges on paths of length 1,2,4,8,.....

Process each query independently.

Test if the path on the tree from u to v contains an edge longer than w.

If so answer Yes.Otherwise,answer No.

Code

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

https://atcoder.jp/contests/abc235/submissions/28584413

Can anybody please help me in finding the mistake in my DP solution of problem D .It passed all the test cases except 99_after_contest_00.txt .Even if anyone is able to find that probable case please help me out.

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

    Looks like our solutions were hacked after the contest and mine fails it too (are problem setters reading comments here?). Now it would be indeed interesting to have a look at this 99_after_contest_00.txt testcase. I tried stress testing, but haven't found anything yet.

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

    Now I have some testcases: "2 11327" (expected 40, but got 41) and "2 62153" (expected 17, but got 18).

    The bug is that the solution is effectively doing DFS to find a path from N to 1. But it isn't always the shortest path, so BFS is really needed instead. The original tests used during the contest were weak and didn't detect it. I wonder how many incorrect solutions got accepted?

    And even now, having just a single testcase (testcase 99_after_contest_00.txt) in the set makes it possible for some heuristically tuned or even randomized DFS to be incorrectly accepted.

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

Rank 1 has different coding styles for each problem, how is that possible? chokudai Can you take a look?

→ Reply