AnandOza's blog

By AnandOza, history, 5 years ago, In English

Hi all, Atcoder Beginner Contest 146 was today. I wrote an unofficial English editorial. Hope it helps!

A: Can't Wait for Holiday

We simply find the index in the week, and print $$$7-i$$$ (taking care to order the days correctly so Sunday gives us $$$7$$$ as the output).

Runtime: $$$\mathcal{O}(1)$$$.

Sample code

B: ROT N

We can simply loop through the string and increment each character by $$$N$$$, taking care to subtract $$$26$$$ if we go past the end of the alphabet.

Runtime: $$$\mathcal{O}(|S|)$$$.

Sample code

C: Buy an Integer

For a given length $$$L$$$, we can consider the maximum integer we can afford of that length (this is easy to calculate because given a fixed $$$d(N)$$$, the cost is monotonic in $$$N$$$). There are only a small number of possible lengths, so we may loop through them.

Note that if any number greater than $$$10^9$$$ is affordable, then $$$10^9$$$ is as well (since it has smaller-or-equal numeric value and length than any number greater than it).

Runtime: $$$\mathcal{O}(\log_{10} X)$$$.

Sample code

D: Coloring Edges on Tree

We can construct an optimal coloring by greedily assigning colors to edges while traversing the tree. Given a vertex $$$v$$$, we can assign colors $$$1$$$ through $$$\mathrm{deg}(v)$$$ to its unassigned incident edges (if one of them is already assigned, we leave it as-is). The final answer for total colors is $$$\mathrm{max}_v(\mathrm{deg}(v))$$$.

I implemented this using a BFS through the tree. When visiting a node, at most one of its edges is already assigned (the one we just came from, if we aren't at the root), so we simply skip this one and note that we can't use its color for another edge on this node.

Runtime: $$$\mathcal{O}(N)$$$.

Sample code

E: Rem of Sum is Num

First, we can consider all sums modulo $$$K$$$ throughout this problem. Let's weaken the constraints of what we're looking for and consider the number of elements modulo $$$K$$$ for a moment as well.

Notice that if we let $$$S_n = \sum_{i=1}^n A_i$$$ (and $$$S_0 = 0$$$), then the sum of a range $$$[i, j]$$$ (1-indexed) is $$$S_j - S_{i-1}$$$ and the number of elements in it is $$$j - (i-1)$$$.

This leads us to compute $$$P_i = S_i - i$$$ for $$$0 \le i \le n$$$, and we look for pairs $$$i < j$$$ such that $$$P_i \equiv P_j \pmod K$$$ (corresponding to taking the range $$$A_{i+1}, \ldots, A_j$$$).

Note that we actually have one more constraint: we shouldn't actually take the number of elements modulo $$$K$$$, so we need the number of elements modulo $$$K$$$ to be equal to the actual number of elements, so we require $$$j-(i-1) < K$$$.

We can count the pairs by maintaining a hashmap of the counts of values of $$$P_n$$$ within a sliding window of the past $$$K$$$ items (these are our candidates for the first coordinate of our range), and adding the count that match each possible second coordinate of our range. Each update takes constant time, so overall this solution takes linear time.

Runtime: $$$\mathcal{O}(N)$$$.

Sample code

F: Sugoroku

Let's make a few observations.

Observation 1: in order to minimize the number of steps, we should take steps that are as large as possible. We don't have to worry about a smaller step ever being better, because if in one step we can choose to go to either $$$i$$$ or $$$j$$$ (with $$$i < j$$$), then anything reachable from $$$i$$$ is also reachable from $$$j$$$ in the same-or-fewer steps. To prove this, consider an index $$$k > j$$$ that is reachable from $$$i$$$. At some point when traveling from $$$i$$$ to $$$k$$$, we will take a step that passes $$$j$$$. At this point, the endpoint of that step is also reachable from $$$j$$$ in one step (because it's at most $$$M$$$ away from a square that's before $$$j$$$), so we could have gotten here at least as fast from $$$j$$$.

Observation 2: in order to find the lexicographically-smallest sequence for a given number of steps, we need to put the largest steps at the end of the sequence. Therefore, we can start at $$$N$$$ and takes steps as large as possible towards $$$0$$$, then reverse the order of the steps at the end for printing.

Observation 3: Let's say we took a (backwards) step from $$$L$$$ to $$$C$$$ just now ($$$L > C$$$), and $$$C$$$ is the minimum index reachable in one step from $$$L$$$ (since we take the biggest steps possible). Then when evaluating the candidates for our next move, we don't need to evaluate anything that's $$$\ge (L-M)$$$, because those are all either unreachable or greater than $$$C$$$. This optimizes our runtime from quadratic to linear, since we only end up looking at each candidate once ever.

We can put this all together to code up a fairly straightforward linear-time solution.

Runtime: $$$\mathcal{O}(N)$$$.

Sample code

Thanks for reading! Let me know if you have any questions or feedback for me.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For D, I am using the same approach as u mentioned.

Can anyone help me where my solution fails?

Solutionhttps://atcoder.jp/contests/abc146/submissions/8625427

Note — I am starting traversal from root node always in a tree and then applying bfs as mentioned in this blog.

It would be of great help to me. Thank you:). I appreciate your time.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I don't understand why you are making a directed graph . Also just take root node as 1 it doesn't matter what root node you take.

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

      But it doesn't matter we make a directed or undirected in a tree.

      Also in my previous submission, i took 1 as node but it didn't work out.

      I think because I am making directed, I am taking into account importance of traversing from root node.

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

        You could get an input with the edges $$$(1, 2)$$$ and $$$(3, 2)$$$ and your traversal wouldn't realize this is a strongly connected graph because you'd have edges $$$1 \to 2$$$ and $$$3 \to 2$$$. I think per nihal_47's comment you should try adding both directions of each edge to your adjacency list. (I believe there are also some other issues with your implementation, but this is a good starting point.)

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

          ok, so the graph isn't always strongly connected?

          I assumed by reading the question that the graph is strongly connected.

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

            The question says that the graph is a tree with $$$N$$$ vertices, nothing else.

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

        You are assuming that in the input you will get edges in the traversed order. For example let input of edges be (2 3), (1,2) then your code will take root as 1 and assign ans = 1 to edge 1 when you should be assigning the ans = 1 to edge 2.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for that editorial. I solved all but E. Thats the one I really dont get.

Why do we look for Pi===Pj? Why does this corespond to a range i,j?

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

    So, we want the sum in a range (mod K) to be equal to the number of elements (let's consider it mod K for now). The sum in the range $$$A_{i+1}, \ldots, A_j$$$ (note the slightly different indices from in my solution, to make it easier to understand) is the the difference of $$$S_i$$$ and $$$S_j$$$ and the number of elements is the difference of $$$i$$$ and $$$j$$$.

    So we set $$$S_j - S_i = j - i$$$, and transform this to $$$S_j - j = S_i - i$$$.

    Does that help? I'll edit my post if so. :)

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

If you'd like to read slightly different solutions (and sample code in C++ instead of Java), Geothermal has also posted an english editorial: https://mirror.codeforces.com/blog/entry/71699

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C, where it is given that if the answer is greater than 1000000000, than we should print 1000000000?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It was mentioned in the problem statement that " The shop sells the integers from $$$1$$$ through $$$10^{9}$$$ ".

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was looking forward to your editorial :)

I couldn’t solve $$$E$$$ as I mistook the question to be asking for subsequences, not sub segments. Now, I see that the problem was asking about contiguous subsequences.

Suppose the question was generalized to find number of subsequences and not sub segments, how would we solve it ?

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

    Yeah, I disliked how it said "contiguous subsequences" the first time and then said "subsequence" afterwards, because normally solvers are very careful to know "subsequence => not contiguous" (so it was confusing).

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

      How to solve the problem of it asked for number of subsequences ?

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

Nice solutions! The linear approach to F was particularly elegant--thanks for sharing it!

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

It's difficult for me to read java code..

Can You please explain the following Line from solution of problem E:

count.merge(prefix[i - k], -1, Integer::sum);

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

Can someone please help to find what's wrong with this code? I am getting wrong answer only in the last test case. This is the 3rd problem (C).

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll fun(ll n)
{
  ll count=0;
  for(;n!=0;n/=10)
    count++;
  return count;
}
int main()
{
  ll a,b,x;
  ll max=0;
  cin>>a>>b>>x;
  for(ll i=1;i<=20;i++)
  {
    ll n=(x-i*b)/a;
    if(n<0)break;
    if(n>max && fun(n)==i)
    {
      max=n;
      if(max>1000000000)
        break;
    }
  }
  if(max<=1000000000)
  cout<<max;
  else
    cout<<1000000000;
}
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it
This is the first time I have solved all the questions. first four by myself and the last two by reading your editorial.
Thank you so much for your effort and time.