IgorI's blog

By IgorI, history, 2 weeks ago, In English

Thank you for participation! Here is the editorial:

1621A - Stable Arrangement of Rooks

Editorial
Solution

1621B - Integers Shop

Editorial

1621C - Hidden Permutations

Editorial
Solution

1621D - The Winter Hike

Editorial
Solution

1621E - New School

Editorial
Solution

1621F - Strange Instructions

Editorial
Solution

1621G - Weighted Increasing Subsequences

Editorial
Solution

1621H - Trains and Airplanes

Editorial

1621I - Two Sequences

Editorial
Solution
Tutorial of Hello 2022
 
 
 
 
  • Vote: I like it
  • +96
  • Vote: I do not like it

»
2 weeks ago, # |
Rev. 3   Vote: I like it +115 Vote: I do not like it

Hello, Fastest editorial of 2022 :)

»
2 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

I hate problem B

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

    I hate test case 1

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

    Only B?

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

      After trying to solve it for 1.5 hours and submitting 5 almost correct solutions. I didn't had time to try any other problem.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it -18 Vote: I do not like it

        sounds like a you problem.

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

          I don't think I ever said it's -is-this-fft-'s problem or writer's problem. I know it's my problem that I'm not good enough but that being said my comment was simply his reply to why the OP only disliked B (like me). So, I replied and I don't think my original comment in any way says it's anyone else's problem.

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

    I do not understand at all what is wrong with problem B. After reading the reviews, I sat down and solved this problem in contest mode. She's great! There's a simple greedy idea in there. It is not another math puzzle. There is a place for a little coding in it.

    If you have difficulties with its implementation, it rather means that you need to write more code. I'm afraid this is one of the basic skills that you can learn from CP: to accurately and quickly implement simple logic. Do this in such a way as to minimize the number of special cases.

    The only minus of the problem is that it is a bit difficult for position B.

    I was lucky to solve it in without any debugging. And it's a nice feeling.

    My code
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -39 Vote: I do not like it

      I guess what most of us meant was that, it is slightly more tougher than the usual Bs!

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

      This is brilliant! Seems like I need to develop a lot in implementing without any bugs. Thanks, Mike!

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

      That means sir you are using multiple codeforces accounts....:)

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Do you agree that hacking during div1 and div2 contests became obsolete after changing single test cases to packets of test cases? The amount of test cases increased and many corner cases are included.

      For example B and F could have smaller amount of pretests, then participants could search for incorrect solutions, and possibly that round would become no less interesting.

      How about splitting CF rounds (div1,div2 with uneven scores) into two variants: 1. Round without hacking (full tests) or hacking time 30 min.after solving time finishes, 2. Oldschool round: weaker pretests and hacking anytime (and possibly with novelty — progressive bounty for (un)successful hack).

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

      after taking input of l ,r ,c in condition if(L.count(l)) without assigning anything to map L .what does it means?

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

    Can someone explain why my solution to B (141591638) is getting Runtime Error instead of WA (I'm not handling the case of using a single longest segment, but I don't see anything in my code that wouldn't work) ?

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

      NVM it's because 10^5 != 10000

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

    ++

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

I was clicking the editorial in expectation that I will get to homepage (as editorial can be so fast) and get to know their standings but to my surprise editorial is there.

»
2 weeks ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

problems are good but im noob lol Happy new year!

»
2 weeks ago, # |
Rev. 2   Vote: I like it -37 Vote: I do not like it

Problem D was nice

»
2 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

How excellent the problem B is!

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

B

»
2 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

I hate WA on pretest(2)

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

Can anyone help me with B ?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Keep track of three values:
    i) Lowest cost of range with lowest integer value till now
    ii) Lowest cost of range with highest integer value till now
    iii) Lowest cost of range with both lowest and highest integer value till now
    
    Then answer is min(i + ii, iii) if iii exists else it is simply i + ii
    
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Here is a simple implementation of the above approach:Link

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

      Why do we need to maintain (iii) if we are already maintaining (i) and (ii) won't it lead to an optimal solution?

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

        `` Example

        1 5 10

        6 10 10

        1 10 18

        iii keeps track of last one else we may need to take 10 + 10 ``

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

          wow, I never thought of that. Thanks for the help.

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

      Got it thanks

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

Small typo on tutorial for problem E : It can be easy done with prefix sum arrays. --> It can be easily done with prefix sum arrays.

»
2 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

Is there any chance you could include the model solutions for our reference? Links to submissions would suffice. Thanks

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

The solution for O (n) on python, problem B shows TL without the use of additional modules. Sorry for my English.

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

    Use Fast I/O. I faced the same issue, but it worked when I switched to a better I/O method. (Note that we had to take lots of small inputs in this question, unlike usual problems where we take a few very long inputs. Hence, better I/O in Python is necessary, I guess.)

»
2 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

I'm curious how you found the solution for problem D? For me, I tried to analyze the problem but got nothing. But since I saw so many people pass this problem, I started to guess some random strategies and verify them manually. But this doesn't seem plausible, so I'm curious if there's some more plausible way to get the solution?

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

    At first I thought that the solution is to find the shortest path (the one with least snow to clean) from any of the top left squares to any of the bottom right. But there was no way to move the people along it without cleaning one of the 8 cells. Got AC but wasn't able to prove it throughout the competition. The fact that so many people had the problem, made me think of an easier solutin, otherwise I probably wouldn't have solved it.

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

    when I want to find a way to go from the left-top to right-bottom, I notice these 8 cells are special, because we cannot go to the right-bottom without passing one of them, after that, I found all friends can go to the right-bottom just using one of these cells.

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

For problem E, how do you compare averages : convert them to doubles or convert them to fractions (p and q) ?

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

    Doubles have precision issues, so it's better to compare them as fractions. A general trick to do the comparison $$$a/b < c/d$$$, is to multiply both sides by $$$b \times d$$$ (assuming $$$b, d >0$$$). Then you get $$$a \times d < c \times b$$$. These numbers could be big, so use long longs.

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

    You can even take ceil value of the division since it has to be greater than or equal to that

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

    I use double and Coordinate Compression, so you can only care about intergers with maxval = O(n)

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

I just spent 1:30 minutes thinking the same and then used if elses for rest of time and WA2 for problem B.

»
2 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

In this contest, (and the previous one) I knew the solution (as far as it is covered by the editorial) to problem C after like ten minutes. And then was not able to implement it until end of contest.

Now, the question is, isn't that implementation part the interesting one (at least in such problem), the one that should be covered by the editorial?

I mean, this observation that there are cycles in a permutation is fairly trivial. I don't think that like 20k partitipants did not solved it because they did not had that idea.

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

    C wasn't too bad to implement... 141526460

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

      Yes, I did inspect some solutions, looks like a three liner. Still there are a lot of partitipants not able to write down that (simple looking) lines of code.

      How is the process to come up with that? Which abstractions are usefull here, which are not?

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

        usually, when you can't implement a solution, it means that you don't actually (or deeply) understand the solution you have come up with :v 141527334 btw here is my implementation.

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

          I think the difficulty with typical implementation problems is more likely to confuse things, and simple off-by-one errors. The solution is then to use the right abstractions in the thought process and to sort them cleanly.

          The solution "I have to see it, its simple!" did not work for me in this problem, and actually does not in general.

          Edit: However, congrats to reaching a new color!

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

          Thanks for that implementation. I now understood it But why are you not printing cout.flush() after printing the query?

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

      Yes C was pretty easy to implement as compared to B in my opinion.

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

    Here is a simple implementation 141573460

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

Could you tell me what's wrong in my solution for task B? 141567260

I tried to maintain 5 values: the leftmost number, cost of optimal line containing it, the rightmost number and cost of optimal line containing it, and the flag — are these lines same.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    Input
    Expected Output
    Your Output
    Comments
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

worst ordering of questions

»
2 weeks ago, # |
  Vote: I like it +45 Vote: I do not like it

tourist's solution to E is so genius, even cleaner than the editorial.

Just throw everything into a segtree then forget about casework.

»
2 weeks ago, # |
  Vote: I like it +72 Vote: I do not like it

In problem D, it took me about 30 minutes just to prove the following case doesn't exist

:(

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

    I didnt realize this until now xD

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

    I am also thinking about the same case. can you pls provide your proof.

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

      lets see on 4 points (1,1),(1,n),(n,1),(n,n) when first of them moved one of them will go to one of 8 points mentioned in solution.

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 5   Vote: I like it +32 Vote: I do not like it

      Say, you want to take this path. This will result in

      Now, you want others to follow the same path for which you'll either do a column up or down, so that the element is placed on the same row (So that same path can be followed). This can be done on any column, either up or down.

      The problem is that, one element moves out of the first n*n square, and takes another path (B)

      So, the answer becomes Cost(A)+Cost(B) (for now). It will add up even more if you do the same with other columns. But, you can accomplish the same thing with only Path B too. So, that becomes the minimum cost path ( Cost(A)+Cost(B) > Cost(B) ). This way, all eight corners can be proved.

      PS. Sorry if this didn't explain the problem

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

    I only realized this in the last 2 minutes of the contest. Also couldn't implement C on time. :(

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

Could you PLEASE show the solution(code) for B? Have been trying to solve it for hours...

»
2 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

sad :(

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

Can anybody show the solution for problem a in java? I don't know why mine is wrong. I used prettt much the same logic in the editorial

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

    I don't know if anything else is wrong in your code but the first mistake i noticed is that you are taking k and n instead of n and k.

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

      Yes.. k for the size of board and n for the rooks. Btw thank you for the reply.. I forgot to put the continue; after 2nd if.. jsbsvajnfnn.. but i hope that's not the only error or else i wont sleep tonight.

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

Can anyone please tell me the 94th test case for test 2 in problem B?

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

I literally got the exact solution described in the editorial for B and got WA on 2. What was B?

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

Can someone point out my mistake on B? 141546457

»
2 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

I liked C — interactive problems without binary search have become extinct nowadays. My solution is very short and the problem involved reasonable amount of thinking.

On the other side, D is not a great problem. I couldn't come up with the solution during the contest (or, to be correct, I came up with it, but it seemed to me totally wrong). However, the problem is ad-hoc and it is not very beautiful.

E was merely an implementation task. I think it's rather good problem. The detail about $$$m \le n$$$ (not $$$m = n$$$) was unexpected and confusing, though.

How do you calculate the number of increasing subsequences that starts in $$$a_i$$$ and ends in $$$a_{x_{y'}}$$$ in G? For me, it was the most difficult thing in it. Am I missing something? We have $$$O(n)$$$ different start points ($$$a_i$$$) and also $$$O(n)$$$ different end points ($$$a_{x_{y'}}$$$) and how we calculate all the numbers fast?

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

    In G, fix the end point, and calculate the answer for all the starting point that corresponds to the current end point. We can just store the updates done to fenwick for current endpoint and undo them in the end.

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

      Ah, thanks a lot! I was missing the moment that no value (no $$$a_i$$$) can correspond to different endpoints. I thought it is somehow possible, so we need to consider $$$O(n)$$$ values for every endpoint. But actually it is $$$O(n)$$$ in summary :)

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

    How can you think that tasks where you just need to implement trivial idea are good, but tasks where you actually need to think — are bad. Do you think cp should become fast-typing competition?

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

      Yes, indeed it sounds strange.

      No, I don't think so. Competitive programming is solving problems and afterwards coding them. I don't like the problems that omit one or another part.

      The problem 1375C - Element Extermination is great example of creating a problem that involves pretty much thinking while the correct solution is so simple, that you can't believe in it. Well, to be objective, it is just simple. I am pretty sure that the majority of the participants, who solved it, just guessed the answer. I was one of them (the contest was about to end and I just had different tries). The process of solving the problem didn't get me much joy.

      I haven't solved the problem D from Hello 2022, but I think the problems are really similiar. The only difference is that it's harder to guess the answer in the problem you were talking about, while one-liner for 1375C - Element Extermination makes it somehow beautiful, while easier to guess the answer. (It is my personal opinion, I am not certain, what is more beautiful or more evident).

      The proportion (thinking : coding) is really unjust in such problems. You make some complicated thought process and afterwards submit quite easy code. The problem would look much better not here, on CF, but on some mathematical contest. Of course, with proof required.

      On the other side, in the E problem the proportion (thinking : coding) was the opposite. The implementation part was huge, and because of that I named it implementation task. However I don't think it was stupid straightforward implementation. The problem required some observations: {you can't dynamically move elements in the set and compare all of them to corresponding values in given array. However, here all the values move at most one position to the right, or one to the left. It wasn't obvious for me, while it wasn't difficult too}. It required some data structure to achieve 'range logical AND of boolean array' (prefix sums).

      Probably, it is too weak for global round E. Well, it may be too standard. However, I managed to mess up something in binary search (it was really disappointing), so it's not only about fingers speed, but also about correctly implementing the solution. Here coding mattered more than thinking, but I believe the proportion was fine.

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

        you can't dynamically move elements in the set and compare all of them to corresponding values in a given array

        $$$\pm 1$$$ shift observation lets you do prefix sum-style solution, but it was not necessary to make it. As long as the array $$$b$$$ is split into a constant number of parts one may apply a certain rmq-like structure with a log overhead.

        Specifically, for all segments $$$b[l..l+2^k)$$$ we can precompute the leftmost position $$$i$$$ such that $$$a_{i + j} \ge b_{l + j}$$$ for all $$$j \in [0, 2^k)$$$. Then we can compute the same position for any segment of $$$b$$$ with log overhead.

»
2 weeks ago, # |
Rev. 6   Vote: I like it +64 Vote: I do not like it

Alternative solution for 1621E - New School

If you fix the student to remove, you can check if the answer is 1 with the following algorithm:

  • Keep a multiset of teachers, for each group of students assign them the teacher with the minimum value $$$\geq$$$ to the average of the group and remove the teacher from the multiset. The answer is 1 if there is always an available teacher.

The key observation is that the algorithm works for any order of the groups of students. So, if you want to check the answer for all the students of a group, you can insert the other groups first, then try to remove each student from that group.

Now, we want to solve this problem:

  • For each group, find the result of the algorithm if you consider all the groups except that one.

This can be solved in $$$O(n \log^2 n)$$$ with D&C (similar to offline deletion). The D&C looks like

solve(l, r) { // for each i in [l, r], find answer if you remove group i
    if (l == r) { // you've inserted all groups except l, so you can check students of group l
        check(l); return;
    }
    m = (l + r) / 2;
    insert(m + 1, r); // assign a teacher to groups in [m + 1, r]
    solve(l, m);
    rollback(m + 1, r); // undo the assignments
    insert(l, m);
    solve(m + 1, r);
    rollback(l, m);
} 

Implementation: 141541065

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

can anyone tell me what is wrong with my solution for task B??141576250

update: I got my mistake

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

    Can you please tell me a testcase where your code was wrong?

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

      output should be : 7 7 7

      my code was not working on this test case, so I keep track of maxLen as also mentioned in the editorial.

»
2 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Is the answer to the bonus part of A: $$$\binom{n-k+1}{k}^2$$$ ?

Basically, there are $$$\binom{n-k+1}{k}$$$ ways to choose the rows containing a rook, and $$$\binom{n-k+1}{k}$$$ ways to choose the columns containing a rook, independently, such that the arrangement is stable.

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

    Close, but there are $$$k!$$$ ways to arrange the rook given the column and rows.

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

Problem B goes to show many people are brick at implementation.

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

In Problem C, is there any specific theorem of any kind or its just based on observation??

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

    "permutation the way it is presented here , exists as a set of disjoint cycles"-> something which is useful here picked from Abstract Algebra

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

I undertand it, pass me!

why Problem D can't acts like the following e.g

for simplify e.g, set i = 10e9

4
0 0 0 0 i i i i
0 0 0 0 i i i i
0 0 0 0 i i i i
0 0 0 0 i i i i
i i i i 2 0 2 2
i i i i 1 6 2 1
i i 3 4 2 4 7 4
i i 2 i 2 0 1 6

in this case, I think friends can move by (8, 3) -> (7, 3) -> (7, 4)

did I ignore something?

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

    You ignored that one of the friends in the four corners must moved one cell out of the upper left quarter. There is simply no way to move them at all without doing this.

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

Can someone tell me the meaning or compiler error message?

wrong answer Token parameter [name=grid[1]] equals to "R", doesn't correspond to pattern "-1|[.R]{3}" (test case 1)

Why my pretest 1 was not passing in spite of doing everything correctly ??

Problem A — My sub-link - https://codeforces.cc/contest/1621/submission/141523368

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

So, I think that problem B can’t be on position B

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

B was a hell

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

Why does solution to E work in time?

We check the removal of each of the 1e5 students. Foreach one its group will move some positions (i to j). We recheck all groups in range (i,j). i,j is not bounded, the dist can be also 1e5.

So how is this not O(n^2)?

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

Can anybody tell me where 141564677 for problem B is wrong?

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    1
    4
    1 100 50
    1 10 20
    40 50 20
    1 5 5
    

    Sorry, your code is working perfectly fine in this testcase. I evaluated it wrong. Even my submission is giving the same expected answer.

    We need some other testcase!

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

Need help in finding a test case where my code fails for Problem B! Link to my submission

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

    Can you tell what was the problem as I seemed to have same problem

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

      I thought I had a counter example. But I evaluated it wrong. My code is working perfectly fine in it. We still need help from someone!

»
2 weeks ago, # |
Rev. 2   Vote: I like it +48 Vote: I do not like it

Here's a more complex but IMO more intuitive solution to E, which I believe was used by a lot of other participants in contest.

It's possible to assign teachers to groups if for every value v, there are more or equal teachers of age at least v compared to groups with average age of at least v. It's easy to see that this is equivalent to the original condition.

Let diff[i] be the (number of teachers with age >= v — number of groups with average age >= v). Then, the condition means for all i = 1...1e5, diff[i] >= 0, or min(diff[i]) for all i = 1...1e5 >= 0.

It's easy to see adding a teacher of age v will add diff[v], diff[v + 1], ..., diff[1e5] by 1, and a group with their rounded up average v will reduce diff[v], diff[v + 1], ..., diff[1e5] by -1. With this, the problem becomes a straightforward lazy segment tree problem: we add all teachers, then add all groups, when we remove a member of a group we temporarily change it's average, and then change it back. All in all, it uses about n + 4 * m segment tree operations, which is far fast enough to AC.

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

    Nice approach! But shouldn't the condition be min(diff[i]) for all i from 1...1e5 >= 0?

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

      Thanks for pointing that out. That was written in not the best of mental conditions.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Alternatively, instead of using a lazy segment tree, you can use an ordinary segment tree which stores the sum and the minimum suffix sum in each node.

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

      I don't understand can you explain your idea bit more.

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        (adding a teacher/group should actually add 1/-1 to diff[1..v], not diff[v..1e5] in the original solution)

        Let a[i]=diff[i]-diff[i+1]. Then what adding 1/-1 to diff[1..v] does is adding 1/-1 to a[v]. You can get the diff array from the a array by noticing that diff is just the suffix sum of a. So, when you're looking for the minimum value in diff, you're looking for the minimum suffix sum in a, which a segment tree can easily handle.

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

Video Editorial for Problem B: Integers Shop

I use 3 pair data structures, instead of 6 variables as mentioned in the editorial, in order to reduce the length of the code and make it easier to understand.

»
2 weeks ago, # |
Rev. 3   Vote: I like it -17 Vote: I do not like it

Thanks for the editorial.

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

Can someone please explain how to solve problem C? I am having difficulties understanding the tutorial. Thanks!

»
2 weeks ago, # |
  Vote: I like it +149 Vote: I do not like it

You can do problem I in $$$O(n \log \log n)$$$ time (linear time per op)! Code: 141611373

We need 3 additional observations. First, we rephrase the copy operation into something a little simpler. Then, we complete the analysis of part 3 of the editorial to find a closed form for whether the the smallest subarray starts at $$$c_l$$$ or $$$c_k$$$. Finally, we show a linear time algorithm for finding the lexicographically smallest suffix of each prefix based on Duval's algorithm for Lyndon factorization.

The copy operation

First, let's rephrase the copy operation. If, in the $$$i$$$th operation, we find the smallest substring of length at least $$$i$$$ starts at index $$$j \le n-i$$$, then $$$D_{i} = (D_{i-1}[1:n-i] + D_{i-1}[j:n])[1:n] = (D_{i-1}[1:n-i] + D_{i-1}[j:n-i] + D_{i-1}[n-i+1:n])[1:n]$$$ (here, we use inclusive substrings). In other words, we insert the string $$$D_{i-1}[j:n-i]$$$ (which is a possibly-empty suffix of $$$D_{i-1}[1:n-i]$$$) directly after the $$$n-i$$$th character, and then we truncate the result to the first $$$n$$$ characters. Then, there are a few useful observations:

  • Picking the smallest substring is equivalent to picking the possibly-empty suffix $$$D_{i-1}[j:n-i]$$$ of $$$D_{i-1}[1:n-i]$$$ (with $$$j \le n-i$$$) that minimizes the result $$$D_{i-1}[j:n-i] + D_{i-1}[n-i+1:n]$$$. Furthermore, note that $$$D_{i-1}[1:n-i]$$$ has not been modified before this step, so this is equivalent to $$$D_0[1:n-i]$$$.
  • With this definition, it's easy to see that we don't actually need to truncate the $$$D_i$$$ to the first $$$n$$$ characters; it's fine to let them grow.
  • We can reindex slightly so that $$$D_i = D_{i-1}[1:n-i] + D_{i-1}[j:n-i+1] + D_{i-1}[n-i+2:n]$$$. In this formulation, we need to pick a nonempty suffix $$$D_{i-1}[j:n-i+1]$$$ of $$$D_{i-1}[1:n-i+1]$$$ to replace $$$D_{i-1}[n-i+1]$$$ so the result is minimized. Once again, $$$D_{i-1}[1:n-i+1] = D_0[1:n-i+1]$$$.

From here on, let $$$A_i$$$ denote the suffix of $$$D_0[1:n-i]$$$ we inserted in the $$$i$$$th step, and let $$$B_i$$$ denote the suffix of $$$D_0[1:n-i+1]$$$ which we substituted for $$$D_{i-1}[n-i+1]$$$, so that $$$B_i = A_i + D_0[n-i+1]$$$. Part 3 of the editorial showed that $$$B_i$$$ is either the minimum suffix of $$$D_0[1:n-i+1]$$$, of it's the maximum number of copies of the minimum suffix. We make a few more observations:

  • Because of the replacement scheme, our final result is $$$D_n = (B_n + B_{n-1} + \cdots + B_2 + B_1)[1:n]$$$. Thus, it suffices to find the $$$B_i$$$.
  • We can consider 2 consecutive steps at once with our 2 indexing ways: $$$D_{i+1} = D_{i-1}[1:n-i] + B_{i+1} + A_{i} + D_{i-1}[n-i+1:n]$$$, where $$$A_{i}$$$ is a possibly empty suffix of $$$D_0[1:n-i]$$$ and $$$B_{i+1}$$$ is a nonempty suffix of $$$D_0[1:n-i]$$$ chosen to minimize the result $$$B_{i+1}+A_{i}+D_{i-1}[n-i+1:n]$$$. This is convenient because $$$B_{i+1}$$$ and $$$A_{i}$$$ are both (almost) minimal suffixes of the same string!

Closed form for which suffix

Now, using the last observation, we can classify whether $$$B_{i+1}$$$ starts at $$$c_l$$$ (the minimum suffix of $$$D_0[1:n-i]$$$) versus $$$c_k$$$ (the maximum number of copies of the minimum suffix of $$$D_0[1:n-i]$$$): $$$B_{i+1}$$$ starts at $$$c_l$$$ if $$$A_i$$$ is empty, and $$$c_k$$$ otherwise. Note that $$$A_i$$$ is empty iff $$$B_i$$$ has length $$$1$$$.

The proof of this is pretty similar to the analysis in part 3 of the editorial. Let $$$S$$$ be the minimum suffix of $$$D_0[1:n-i]$$$, and let $$$E = D_{i-1}[n-i+1:n]$$$. Then, either $$$A_i$$$ is empty, or $$$A_i$$$ starts with $$$S$$$, and $$$B_{i+1} = S$$$ or $$$B_{i+1} = S^l$$$ for some $$$l$$$ (this denotes $$$S$$$ repeated $$$l$$$ times). Then, note that $$$A_i + E < S + A_i + E$$$ iff $$$S + A_i + E < S^2 + A_i + E$$$ iff $$$S^2 + A_i + E < S^3 + A_i + E$$$ and so on, so we should take $$$B_{i+1} = S$$$ iff $$$S + A_i + E < S^l + A_i + E$$$ iff $$$A_i + E < S + A_i + E$$$.

Now, because $$$A_i$$$ is optimal on the $$$i$$$th step, we must have $$$A_i + E < P + E$$$ for any other prefix $$$P$$$ of $$$D_0[1:n-i]$$$. In particular, if $$$A_i$$$ is empty, then $$$A_i + E < S + E = S + A_i + E$$$, so we should take $$$B_{i+1} = S$$$. Otherwise, $$$A_i$$$ starts with $$$S$$$, so $$$A_i + E < A_i[len(S)+1:] + E \implies S + A_i + E < A_i + E$$$, so we should take $$$B_{i+1}=S^l$$$.

Thus, we've proven that $$$B_{i+1}$$$ is the minimum suffix exactly when $$$B_{i}$$$ has length $$$1$$$.

Fast algorithm for min suffix

Finally, we sketch a linear time algorithm to find the minimum suffix of each prefix of $$$D_0$$$ (and the max number of copies).

Note that the minimum suffix of a string $$$S$$$ is exactly the final Lyndon word in the Lyndon factorization of $$$S$$$. Furthermore, the maximum number of copies is the number of equal Lyndon words at the end of the factorization of $$$S$$$. (This is pretty trivial/uninteresting statement, but it's useful terminology/framing.)

We can find both using an algorithm similar to Duval's algorithm for Lyndon factorization (emaxx writeup), which is itself similar to KMP. I'll refer to terms from the writeup, so please read that first. In essence, we build the KMP failure function to compare the string to its suffixes, but if the suffix is smaller than the whole string, then the suffix is part of a later Lyndon word, so we can cut off and output some prefixes as a maximal Lyndon word.

In this case, we need to modify it slightly. Duval's algorithm is already almost online, so we're pretty close being able to find the Lyndon factorization of every prefix. First, we'll modify it to be a little more online and less amortized: in the case where our next character is small and we want to cut a pre-simple string $$$ww\ldots w\overline{w}$$$ down to $$$\overline{w}$$$, the algorithm typically resets the state all the way back to an empty string and reprocesses $$$\overline{w}$$$. Instead, note that $$$\overline{w}$$$ is a prefix of $$$w$$$, so we can just store our current pre-simple string in a stack and pop all the way down to $$$\overline{w}$$$. (This adds linear memory, which is why it's probably not used in normal Duval's).

Now, to find the "tail" of the Lyndon factorization of a prefix, we need to process up to that prefix, and then append a terminator with value $$$-\infty$$$. Note that this will cause a series of cuts from $$$ww\ldots w\overline{w}$$$ to $$$\overline{w}$$$, each of which jumps back to some smaller stack size. The last cut we do is the tail of identical strings in the Lyndon factorization. Thus, we can just precompute the final cut starting at each location: it's just the final cut of the location you would jump to.

Thus, we have a linear time algorithm for finding all minimum suffixes of each prefix of $$$D_0$$$.

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

https://codeforces.cc/contest/1621/submission/141560289 Can anyone help me out what i might be missing in B's Implementation

Update: Resolved

»
2 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

I think that Problem E has a serious problem: Nobody has the age of 1e5

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

can someone please explain problem 'c' in detail i am unable go through the editorial ?

are there are any prerequisite for that question ?

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    i have done like this(but after the contest). we can consider p array as directed graph. eg if p=[4,2,1,3] then the graph will be like this https://ibb.co/sJZ4tM2 now there are 2 type of edges, one is self loop. other is cycle. now what i do is, for every i in [1,n], i ask for the value at that index if i dont know p[i]. for every i, i ask multiple times, if corresponding values are equal, then it is a self loop and p[i]=i; else i ask q[i] until i see the complete cycle, lets say q1=a and q2=b, then p[q1]=q2.

    here is my code: https://codeforces.cc/contest/1621/submission/141614438

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

      thanks! with an example i was able to see that elements present in a cycle simply exchange their positions as if they are in cycle .

      Can any explanation be provided about why this is happening ?

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

My solution for B is similar to editorial but getting wrong answer at Test Case 2. Can someone help me here? Link to solution — here

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

Hi everyone, can anyone provide me a edge case for my code for problem C? CODE Thank You.
My implementation has same logic as the editorial has but I'm not able to find why I'm failing at test 2 subtest 34.

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

    please check for permutation "1, 2, 3, 4, 5"?

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

The problem statement for B was pretty confusing to be honest.

»
2 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

If you are looking for video solutions, HERE they are(for A-D)

»
2 weeks ago, # |
  Vote: I like it -27 Vote: I do not like it

what is wrong in this implementation for problem B. I tried to implement the same logic as is given in the editorial but could not get it right?

void solve() {

int n;
cin >> n;

pair<int, int> arr[n];
int cost[n];

for (int i = 0; i < n; i++)
{
    cin >> arr[i].first >> arr[i].second >> cost[i];
}

int mi = 0, ma = 0, len = 0, costlen = 1e9 + 1;
// mi for min index.
// ma for max index.
// len for max length.
// costlen for cost of max length.
cout << cost[0] << endl;

for (int i = 1; i < n; i++)
{
    if (arr[i].first < arr[mi].first)
    {
        mi = i;
    }
    if (arr[i].second > arr[ma].second)
    {
        ma = i;
    }
    if (arr[i].first == arr[mi].first && cost[i] < cost[mi])
    {
        mi = i;
    }
    if (arr[i].second == arr[ma].second && cost[i] < cost[ma])
    {
        ma = i;
    }
    if (len < arr[i].second - arr[i].first + 1)
    {
        len = arr[i].second - arr[i].first + 1;
        costlen = 1e9 + 1;
    }
    if (len == arr[i].second - arr[i].first + 1)
    {
        costlen = min(costlen, cost[i]);
    }

    if (len == arr[ma].second - arr[mi].first + 1)
    {
        cout << min(cost[mi] + cost[ma], costlen) << endl;
    }
    else
        cout << cost[mi] + cost[ma] << endl;
}

}

int main() { int t = 1; cin >> t; while (t--) solve(); }

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

Can someone tell me what I am doing wrong with the https://codeforces.cc/contest/1621/submission/141567369 submission for problem B.

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

Here's another (more systematic) way to arrive at what you want to compute in G.

Let $$$X_i$$$ be the indicator variable such that $$$X_i = 1$$$ if and only if $$$i$$$ (by index) is included in an increasing sequence and there exists $$$x$$$ such that $$$a_x > a_i$$$ and $$$x$$$ is past the end of the sequence. If $$$tot$$$ is the number of total increasing sequences of the array, we are interested in computing $$$tot \cdot E[X_1 + \cdots + X_n]$$$ by definition.

Let's focus on the $$$E$$$ term. By linearity, this collapses to $$$E[X_1] + \cdots + E[X_n]$$$. Note since $$$X_i$$$ are all indicator variables, $$$E[X_i] = P(X_i)$$$.

Let $$$lst_i$$$ be the largest index such that $$$a_{lst_i} > a_i$$$ (similar to editorial). Then,

$$$P(X_i) = P(i \ \text{is included}) \cdot P(\text{the sequence including} \ i \ \text{ends before} \ lst_i).$$$
$$$ = P(i \ \text{is included}) \cdot (1 - P(\text{the sequence including} \ i \ \text{includes } \ lst_i)).$$$

If $ $$$tot_i$$$ denotes the total number of sequences including $$$a_i$$$, and $$$tot_{il}$$$ is the number of sequences including $$$i$$$ and $$$lst_i$$$ then this value is just

$$$P(X_i) = \frac{tot_i}{tot} \cdot (1 - \frac{tot_{il}}{tot_i}) = \frac{tot_i - tot_{il}}{tot}.$$$

Proceed as mentioned in the editorial to find $ $$$tot_i$$$ and $$$tot_{il}$$$, and don't forget to multiply the entire sum by $$$tot$$$.

Here's my implementation (a bit messy).

This idea of assigning indicator variables to compute what we want works on a lot of mathy problems like these, especially on AtCoder. Also, excuse the wonky latex (was being annoying when typing this up).

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

I solved problem B using priority queue (i.e, heap) in O(n*logn). Added comments for easy understanding. Have a look!! :)

I wasn't able to solve it in live contest as I could not think of the third point mentioned in the editorial of the problem. (i, e, The length of the longest segment and the cost of the cheapest of such segments.)

Link to solution

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

The proof in $$$D$$$ may not be convincing much as we still can move the columns $$$[1, N]$$$ one by one through the $$$2^{nd}$$$ column for example. Although will not be able to complete the solution, this does not pass through the mentioned $$$8$$$ points in the first operations.

Another proof that we must always pass by at least one of the mentioned $$$8$$$ points:

For the points $$$(n+1, n+1)$$$, $$$(n+1, 2n)$$$, $$$(2n, n+1)$$$, and $$$(2n, 2n)$$$ to be filled, they have to be filled from the bottom-right corner itself, as any filling from the other $$$3$$$ corners would pass through one of the mentioned $$$8$$$ points. Now let's try to fill one of the $$$4$$$ points, we will notice that any shifting in the bottom-right corner to fill one of those $$$4$$$ points will result in emptying another one of them, and this will just go indefinitely.

EDIT: It seems that the editorial's proof is complete as well. We can never make a first move with a row/column having one of the $$$4$$$ points $$$(1, 1)$$$, $$$(1, n)$$$, $$$(n, 1)$$$, or $$$(n, n)$$$ without moving another one of them to one of the $$$8$$$ mentioned points.

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

Can anybody please tell me what's wrong with my solution for problem C? :( code-attempt-wa-testcase2

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

Can anybody help me to find out where my solution to B (using ordered set) is failing in test 2? I tried many random generated small test cases with correct output. Didn't able to find any failure test case. :( https://codeforces.cc/contest/1621/submission/141576936

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

    I didn't look into your code too much, but I found a testcase for which your code gives WA

    testcase
    expected output


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

Can someone please help me figure out a test case on which my code will fail for problem B. 141637071

»
13 days ago, # |
  Vote: I like it +16 Vote: I do not like it

Some hints for people stuck at debugging problems B and C (as per the comments above).

avkonyahin

Input
Expected Output
Your Output
Comments

practice_52

Input
Expected Output
Your Output
Comments

pks18

Input
Expected Output
Your Output
Comments

Abhishek357

Input
Expected Output
Your Output
Comments

Mysticode

Input
Expected Output
Your Output
Comments

_s_h_n_

Input
Expected Output
Your Output
Comments

AnestheticCoder

Input
Expected Output
Your Output
Comments

Blinding_Lights

Participant-Jury Interaction
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey i am new here, can anyone explain why k>[n/2] is written as k > (n+1)/2 ?

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

    It is basically telling that

    ceil(n / 2) = floor(n + 1 / 2)

    Intuition
    If n = even, for any non negative i,
    n = 2i,

    ceil(n / 2) = floor(n + 1 / 2) = floor((2i + 1) / 2) = floor(i + 0.5) = i

    If n = odd, for any non negative i,
    n = 2i + 1,

    ceil(n / 2) = floor(n + 1 / 2) = floor((2i + 2) / 2) = floor(i + 1) = i + 1

»
13 days ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

Alternative solution to G:

If $$$a_{x}$$$ affects the weight of a subsequence $$$a_{i_1},...,a_{i_k}$$$, then this subsequence doesn't maximize the value of $$$i_{k}$$$ across all increasing subsequence containing $$$a_{x}$$$. We can also see that the latter implies the former.

So if we can count the number of increasing subsequence starting in $$$a_i$$$ and maximize the position of the rightmost element, we can solve the problem. It turns out that it is possible in $$$O(n log n)$$$ using segment tree.

Implementation

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

Could you please tell me, why my code for problem B (Integer Shop) is wrong. Here is the implementation 141707198

Thanks in advance!!

[Edit: Resolved]

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

I have an interesting idea in problem C:

When the change $$$q_{i}'=q_{p_i}$$$ turn into $$$q_i'=q_{q_i}$$$ ,How to solve the problem?

PS: It's also the mistake I made in the contest

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

    if q is not 1,2,3,4... initially and it is P then the same idea seems to work

»
11 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Hi — I'm pretty sure I have a solution to problem E but i'm not sure it works, and I do not want to implement it right now. Maybe someone could read the following and comment.

After sorting as in the editorial (in decreasing order), we first check if before removing anyone, it's possible to start lessons.

  • If yes, the only way to make the lessons not possible is to remove a student with a lower value than the average of his group, which will make the average larger and move that group to the left in the sorted array. Then either that group itself is larger than teacher, or one of the shifted (shifted to the right) groups are larger than the corresponding teacher. Since each group can only move 1 index to the right, we will denote an index as bad if when moved one to the right, it will be bigger than the teacher. Suppose I remove a student and group is moved from index 9 to index 3, the only question is — is there a bad index between 3 and 8? And that's a very easy thing to answer, all you have to do is save the closest bad index to the left of each index. if the closest bad index to 9 is for example 7, then we know there is a bad index between 3 and 8. If the closest bad index to the left is 2, we know there isn't.

  • If no, it's simpler. Look at the set of all indices violating the conditions of being smaller than their teacher. If there is an index in the set such that moving it to the left doesn't fix the condition, it's never possible. Assuming that moving each of them one index to the left fixes the condition, the only way to make the lessons possible, is to move the entire set of these indices one index to the left. Note it's enough to look at the min and max of that set. Say the set includes 3,6,8,11. Then you just need to make sure to move the segment [3,11] to the left, and you fixed the condition (assuming of course that the moved group doesn't ruin it itself). So you just have to go over the groups 0,1,2 (i.e. the ones less than the minimum in the set), and see if removing a student moves the group to an index >= 11.

Of course some details are missing, but that's pretty much it. Thinking about it — it might've been faster coding it than describing it ^_^.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone have 1621A Bonus Solution?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the editorial mate :)

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

Solution This solution to problem E is failing against second test case, there is only on bit different , tried a lot, please help me out , thanks in advance