Geothermal's blog

By Geothermal, history, 2 months ago, In English,

A — Can't Wait for Holiday

The only approach here is the trivial one--compare the input to each of the possible seven values and print the appropriate answer for each of them. One reasonably fast way to implement this is to create an array $$$A$$$ containing the seven inputs, with "SUN" in position zero and "SAT" in position six. Then, we compare $$$S$$$ to each value in the array and, upon finding the value $$$i$$$ such that $$$A[i] = S$$$, we print $$$7-i$$$. This is valid because the next Sunday after the day represented by our input would come in position seven.

Runtime: $$$O(1)$$$. Click here for my submission.


B — ROT N

Again, the only real solution here is to directly implement the approach given in the problem statement. However, character arithmetic gives us a fairly nice way to do so. For each character in $$$S$$$, we can compute the position of the corresponding letter in the alphabet by taking $$$S[i]$$$ minus the character 'A'. From here, we can add $$$N$$$ to this value and take the result modulo $$$26$$$ to find the offset corresponding to our new letter upon ciphering. Then, we can add 'A' to the offset and set $$$S[i]$$$ to the result to update $$$S$$$ accordingly. Finally, we simply print $$$S$$$.

Runtime: $$$O(N)$$$. Click here for my submission.


C — Buy an Integer

Observe that we should buy a number with the greatest possible number of digits, since any number is strictly greater than any other number with fewer digits. We iterate over the possible numbers of digits in decreasing order and print our answer as soon as we find a number of digits at which we can afford some number.

Given that we want to buy an $$$N$$$-digit number, the cheapest one is $$$10^{N-1}$$$, which will cost $$$10^{N-1}A + NB$$$. If this is greater than $$$X$$$, we must try a lower value of $$$N$$$. If not, let's solve for the maximum number we can buy. Suppose this number is $$$M$$$. Then, we must have $$$MA + NB \leq X$$$, so $$$MA \leq X - NB$$$, so $$$M \leq \frac{X - NB}{A}$$$. Thus, any $$$N$$$-digit number that is at most $$$\frac{X - NB}{A}$$$ will be cheap enough. Keep in mind that since we've assumed we're buying an $$$N$$$-digit number, $$$M$$$ must be at most $$$10^N - 1$$$, even if $$$\frac{X - NB}{A}$$$ is $$$10^N$$$ or greater. (For example, if $$$A = 1$$$, $$$B = 20$$$, and $$$X = 40$$$, then we clearly cannot buy any number with at least two digits, and when we consider one digit, we find $$$\frac{X - NB}{A} = 20$$$. However, since we're only considering one-digit numbers, the greatest possible answer is $$$9$$$.)

From here, we can iterate over all possible values of $$$N$$$ in decreasing order and print the answer corresponding to the first sufficiently cheap value of $$$N$$$. It's probably a good idea to check separately whether we can buy $$$10^9$$$, since this case works a little differently because we can't buy any larger $$$10$$$-digit numbers.

Runtime: $$$O(\log MX)$$$, where $$$MX$$$ is the greatest integer sold. Click here for my submission..


D — Coloring Edges on Tree

We claim $$$K$$$ is the maximum degree of any edge. Our construction is fairly simple. Root the tree at vertex $$$1$$$ and perform a DFS. Then, when we reach a node $$$v$$$, color its children edges with any set of colors from $$$1$$$ to $$$K$$$ not already used to color the edge from $$$v$$$ to its parent, if $$$v$$$ isn't the root. This will always be possible because we know by our choice of $$$K$$$ that there will be at least $$$\textrm{deg} \, v$$$ colors to choose from, so we can use the colors $$$1$$$ through $$$\textrm{deg} \, v$$$ for this, possibly excluding the one already used for the edge from $$$v$$$ to $$$v$$$'s parents. In practice, my solution iterates through the colors starting with $$$1$$$ and skipping the one already used if necessary.

Proving that no answer lower than this $$$K$$$ is possible is fairly trivial. Suppose for contradiction that $$$\textrm{deg} \, v$$$ is greater than the minimum possible $$$K$$$ for some vertex $$$v$$$. Then, by the Pigeonhole Principle, it is impossible to color the edges incident to $$$v$$$ with different colors from $$$1$$$ to $$$K$$$, so this must not be the case. Therefore, $$$K$$$ must be at least $$$\textrm{deg} \, v$$$ for all vertices on the graph, which implies that our solution is optimal.

Runtime: $$$O(N)$$$. Click here for my submission.


E — Rem of Sum is Num

First, note that the required conditions cannot hold for a sequence of at least $$$K$$$ elements, since any value $$$K$$$ or greater cannot be the remainder when our sum is divided by $$$K$$$. Otherwise, we can write the given equation for the range $$$i$$$ through $$$j$$$ as

$$$\sum_{k = i}^j A_k - 1 = 0 \, \textrm{mod} \, K.$$$

We thus decrease all values in the array by $$$1$$$, reducing our problem to counting subarrays summing to $$$0 \, \textrm{mod} \, K$$$ with length less than $$$K$$$. This can be solved using prefix sums and a sliding window. First, ignore the condition on the length of $$$K$$$. Then, the number of valid sequences ending at $$$j$$$ is the number of earlier positions $$$i$$$ such that

$$$\sum_{k = 0}^i A_k - 1 = \sum_{k = 0}^j A_k - 1,$$$

working modulo $$$K$$$. We can iterate over all prefixes of the array and maintain a map from prefix sums modulo $$$K$$$ to the number of times they've occurred so far to keep count of this. Then, to bring back the condition on the length of our array, we can remove the sum that occurred $$$K$$$ positions earlier from our map before incrementing the answer at each position so that at any given time, all subarrays of length $$$K$$$ or greater are not considered as options.

Runtime: $$$O(N \log N)$$$. Click here for my submission.


F — Sugoroku

We employ dynamic programming. Let $$$dp[i]$$$ be the minimum number of moves to reach cell $$$N$$$ from cell $$$i$$$, and let $$$nxt[i]$$$ be the least possible next move from position $$$i$$$ that makes it possible to achieve this minimum. We can compute $$$dp[i]$$$ for all positions except the game-over cells as one plus the minimum of $$$dp[i+j]$$$ over all $$$j$$$ from $$$1$$$ to $$$M$$$, and $$$nxt[i]$$$ is the least $$$j$$$ that achieves this minimum. (For simplicity, we let $$$dp[i]$$$ be infinity for all game-over cells.)

Of course, implementing this as given would take $$$O(NM)$$$ time, so we need to be faster about it. There are lots of ways to do this--for example, we could use a segment tree. However, my solution employs a priority queue. The queue will store pairs $$$(dp[i], i)$$$ and will be sorted such that the lowest element is that with the lowest value of $$$dp[i]$$$, with ties broken by selecting the lowest value of $$$i$$$ (in order to satisfy lexicographic minimality), since at any given point we should transition to the smallest possible next point. Then, we iterate over all positions in decreasing order of $$$i$$$. To compute $$$dp[i]$$$, we first check the top element $$$(dp[j], j)$$$ from the queue and, while this top element has $$$j > i+M$$$, pop it from the queue, since we can no longer make a move that will get us far enough to reach this position. Then, if any elements remain in the queue, we can set $$$dp[i]$$$ to $$$dp[j] + 1$$$ and $$$nxt[i]$$$ to $$$j-i$$$. If no elements remain in the queue, it is impossible to reach the end of the board from position $$$i$$$.

From here, we can print $$$-1$$$ if $$$dp[0]$$$ is infinity. Otherwise, we can reconstruct and print the answer using the $$$nxt$$$ array.

Runtime: $$$O(N \log N)$$$. Click here for my submission.


As always, questions and comments are welcome below.

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

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

Auto comment: topic has been updated by Geothermal (previous revision, new revision, compare).

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

So, printf("%I64d",ans); doesn't work well on AtCoder :)

»
2 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Well, I solved A by using if-else. :P

»
2 months ago, # |
Rev. 4   Vote: I like it -14 Vote: I do not like it

Hi, Geothermal, can you tell me what is wrong with my submission https://atcoder.jp/contests/abc146/submissions/8621102

I already solved the problem, thanks anyway

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

Other approach for C:

  1. Observer that cost function is monotonically increasing because both the number and length of digits are monotonically increasing.
  2. Apply binary search.

Solution

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

    Oh shit, I literally tried this first, and then it didn't work (I printed 4999999994 or something for one of the samples), so I thought I probably made a mistake with monotonicity and gave up. Then I re-did it with a loop (which also failed) and I eventually realized I needed to do $$$\min(ans, 10^9)$$$ at the end. I guess that was the issue with my binary search too, LOL.

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

      You're not alone man(I'm glad I'm not alone either :P)

      I did it in cpp and set the upper bound x/a which probably gave the same answer like you said because of overflow. Then rewrote whole code in Python and after that I saw 10^9 limit in the description. :)

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

      Haha, same. I was stuck for 2-3 minutes, then read the line " The shop sells integers from $$$1$$$ to $$$10^9$$$ ".

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

      I also got that value for Sample Input 2 , unfortunely i couldn't get accepted with binary search . the solution for the "4999999994" problem was that Takahashi could only buy an integer ranging between [1,1e9] , after fixing that i still got WA , and still wondering what's wrong

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

      Lol i got exactly same 4999999994 , it was on this case 2 1 100000000000 and thought my BS is wrong. Indeed it works https://atcoder.jp/contests/abc146/submissions/8640858

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

    I really liked your solution =D, but you can optimize it even more You can calculate number of digits of a number using this formula int(log10(n)) + 1

    UPD: This works only iff n > 0

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

Here's a solution for F using Segment Tree and BS: https://atcoder.jp/contests/abc146/submissions/8632279

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

    Can you elaborate your solution more? thanks :)

    UPD: Got it

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

      Yea, nothing special, just do a BS to find the smallest index with the given min value.

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

I got the intuition for solving D but I don't know how to implement it in a code. i.e how to colour the edges of a tree and was searching google for edge colouring. Here I found the solution on gfg https://www.geeksforgeeks.org/edge-coloring-of-a-graph/.

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

Thanks for the fast tutorial !!
Greedy approach for F: https://atcoder.jp/contests/abc146/submissions/8635899

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

ABC146 F should have an excellent o (n) algorithm

Click there

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

sir please do write editorials for global rounds too.

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

I don't iterate over all color each time in D. I just use previously used color + 1. https://atcoder.jp/contests/abc146/submissions/8641060

»
2 months ago, # |
  Vote: I like it -13 Vote: I do not like it
#include<bits/stdc++.h>
using namespace std;
long long countDigit(long long n) 
{ 
    long long count = 0; 
    while (n != 0) { 
        n = n / 10; 
        ++count; 
    } 
    return count; 
} 
long long binary(long long l,long long r,long long a,long long b,long long x){
    long long ans=-1;long long mid;
    while(l<=r){
       mid=(l+r)/2;
       if(a*mid + countDigit(mid)*b <=x){
           l=mid+1;
            ans=max(mid,ans);
       } 
        else{
            r=mid-1;
        }
       
    }
    // if(ans!=-1){ ans=mid;}
 return ans;   
}
 
int main() {
long long a,b,x;
    cin>>a>>b>>x;
    
    long long l=1,r=x,ans;
    // cout<<start;
    ans=binary(l,r,a,b,x);
    
if(ans==-1){
    cout<<"0"<<endl;
}else{
    if(ans>1000000000){
        ans=1000000000;
    }
    cout<<ans;
}
	return 0;
}

CAN SOMEONE TELL IT IS THE "C" question what is wrong i was getting 12/16 right and rest wrong

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I CAN"T Understand D , can some one explain me some using BFS , but in more simpler way pleasee!

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

How to solve $$$E$$$ if it asked for number of subsequences instead of number of subsegments ?

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

What is hand02 test case in problem E? My submission is unable to pass it. Could you help me figure out what i missed? My submission

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In your solution of D I couldn't understand the following line completely:- if (nxt == p) continue; I understood that it is there to prevent the recursive function from running infinite times by stopping it from getting stuck in a cycle (not the kind of cycle in graphs)and maybe this is applicable only to trees.Since I am new to graph theory, understanding this would certainly help me.Thanks in advance and really loved the editorial.

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

    Yes you are right. This is to prevent infinite loop because from current node we can go back to parent and then from parent go to current node and this goes on and on. Hope this comment helps.

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

      Thanks, this is exactly what i wanted to know.Also my bad ,this was easy to understand, i just didn't read the code carefully, looks like i should go to sleep.Again thanks for the reply.