Блог пользователя aropan

Автор aropan, история, 4 года назад, По-русски

Хорошего настроения и чистых мыслей всякому зашедшему сюда.

1422A - Ограждение
Автор aropan
Решение 94875319

Разбор

1422B - Красивая матрица
Автор andrew
Решение 94875245

Разбор

1422C - Торг
Автор aropan
Решение 94875502

Разбор

1422D - Возвращение домой
Автор aropan
Решение 94875536

Разбор

1422E - Минлексы
Автор aropan
Решение 94875558

Разбор

1422F - Скучные запросы
Автор andrew
Решение 94875580, авторское решение с персистентным деревом отрезков 94875295

Разбор
Разбор задач Codeforces Round 675 (Div. 2)
  • Проголосовать: нравится
  • +101
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -74 Проголосовать: не нравится

I am first?

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Hi, I have a doubt in the tutorial of problem D(Returning home), if I take P1=(1,1), P2=(5,50), and P3=(3,2), then distance(P1, P3)+distance(P3, P2)=1+2=3 is not equal to distance(P1, P2)=4. I am not sure if I am missing anything, can someone please help?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you're right. The minimum distance(P1, P2)=3. Our target is to minimize the distance.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Understood, thanks for the help. Got confused by the line "the distance between the first and second point will be equal to the sum of the distances between the first and third and between the third and second.", I think it should be "less than equal to".

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        Nope man ! see first of all the distance between first and third and third and second is equal to the first and second is right provided they are first , second and third by some parameter which here can be x co-ordinate or y co-ordinate . Refer to your example , Note that third is middle as referred in the editorial , it's not third by sort, so if we sort by x we have : first — (1,1) third- (3,2) and second — (5,50) so distance between first and third = |1-3| = 2 distance between third and second = |3-5| = 2 distance between first and second = |1-5| = 4 so LHS = 2 + 2 = 4 and RHS = 4 Hence , LHS = RHS . Similarly one can do it for y as well if if were less than or equal to than we have to connect another edge and that situation may lead to O(m^2) edges so that we want to avoid . If you still in doubt you can watch : https://www.youtube.com/watch?v=X1nmTo_Gkww&t=2s

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Hi, thanks for the detailed explanation. But, referring to your explanation the distance between first and third point will be |1-2|=1 and not |1-3|=2.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How is median of all numbers equal to the average of the sorted set ? Consider 1, 1, 1, 1000 median = 1 average = 334.3333

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Problem C: How the number of combination of left side will be i*(i-1)/2

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    It is basically nC2 where n = i-1 since the editorial is considering 1-base indexing. So if we are at ith position and we consider removing left side substring we know the power of ith element for sure since right side is static so for every substring removal of left side it will contribute that same power. Therefore we need to check how many total substrings can be generated on left side i.e.nC2(choose two ends of substring in nth length string where n = i-1)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain the persistent segment tree solution on F?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    have you understood the editorial one , can you explain me the second part in the editorial (finding lcm for max prime-factors of ai)?thanks in advance!!

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Problem E can be solved without hashes, as we could just calculate the first character which is not equal to the first character of each suffix. It could be easily re-calculated when we add a new character to each suffix. After that when we have an option to remove 2 equal characters we should compare those 2 characters with the first not equal character, and if it's smaller then we should remove those 2 characters. 94883205

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone explain how to calculate the lcm for those max prime-factor of every Ai(second part) in problem F, i haven't understood the editorial?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have an alternate solution to the problem C. My solution : Solution . In this, I assumed dp[i] to be the required sum of the numbers if I consider first i digits of the number. Now, I have two choices either to include the last digit or not. If I include the last digit then the sum of the numbers will be equal to 10*dp[i-1]+(i*(i+1)/2)*(ith digit). Here i*(i+1)/2 indicates the number of times in which ith digit will appear in one's place. Now coming to the 2nd possibility, i removed the last digit and in the question, it is mentioned that we can remove a continuous segment so I will have to add all those numbers which will form upon removing the digits one by one from right to left. That value is val2 variable in my code. I used 0-based indexing!! dp[0]=1st digit.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

It may be a bit dumb of me, but why doesn't the greedy work in question E? Let's say at a point we have a streak of characters followed by a different character like this: "...xxxxy..." where x and y stand for any arbitrary character. If x > y, then it should always be better for us to delete as much x as we can. We would leave one x if the number of x is odd and delete all of them otherwise. On the other hand, if x < y, keeping all x should always be lexicographically smaller. What am I missing here?

EDIT: Although I don't think it will contribute that much to my question, here's my submission if you want to look at it: 94749759

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The y's could be deleted previously! So it's more like xxxxyyz so we should be comparing x with z or y here depending on whether the double y are deleted in your previous choices. And also for xxxyyxz we may also compare x with z or y.

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

In problem F, shouldn't $$$k$$$ be $$$\frac{\sqrt{MaxA}}{\ln{\sqrt{MaxA}}}$$$ instead of $$$\sqrt{MaxA}\ln{\sqrt{MaxA}}$$$?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone plz explain a bit more clearly (proof, with an example maybe, with better intuition) in problem D editorial.

It turns out that for each point of the graph it will be enough to draw the edges to the points nearest along the x axis in both directions. Similarly for y.

Thanks in advance!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    consider these points (1,2) , (2,4) , (3,8) and (4,16). if you want to consider the edge from (1,2) to (3,8) with cost 2 (i.e. from (1,2) to (3,2) and from (3,2) to (3,8) using the teleportation) , instead of that edge travel from (1,2) to (2,4) with cost 1 (i.e. from (1,2) to (2,2) and then from (2,2) to (2,4) using teleportation) and then from (2,4) to (3,8) with cost 1 (i.e. from (2,4) to (3,4) and then from (3,4) to (3,8) using teleportation).

    So our main observation is that if we want to consider any edge from point x to point y instead of considering that edge from x to y , add on all the edge weights of (x->x+1) , (x+1->x+2).......,(y-1->y) , beacause the cost for these both cases would be same and the no of edges that we have to consider decreases from m^2 to o(m).

    I don't know if you have asked this or not , if not just ignore this.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks for your reply. Can you please tell how the number of egdes decrease from O(m^2) to O(m). and what optimisation u used for it. Sorry, but For me the lines you wrote in black were a bit unclear for me :(

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        actually for given m teleportation points , we will not consider all the possible edge pairs (m^2) , instead we will form only edges of adjacent x values and the edges of adjacent y values so total no of edges we will consider is 2*(m-1) . consider p1,p2,p3...pm are m teleportation points(sorted acc to x coordinates) and we will consider only these edges i.e. (p1<->p2) , (p2<->p3) , ..... and the reason why we will not consider these type of edges (p1<->p5) or (p2<->p7) is beacuse we can get the same cost, as we go from p2-p3 and then p4-p5 and then p5-p6 and then p6-p7 , we will use this path (because the cost would be same so no need to consider the useless edges like (p2<->p7)) (Try with pen & paper for an example).it will be more clear.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi I had a doubt in the first question. In the tutorial it is written that the condition is satisfied by putting d = a+b+c-1. This is what I intuitively thought too and wrote a code outputting d as a+b+c-1. But the online judge reported WA in one of the tests. Please help

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi I had a doubt in the first question. In the tutorial it is written that the condition is satisfied by putting d = a+b+c-1. This is what I intuitively thought too and wrote a code outputting d as a+b+c-1. But the online judge reported WA in one of the tests. Please help

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Integer Overflow

    Your Submission

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Why should overflow occur, I have used long datatype. My code:


      #include<iostream> using namespace std; int main() { int t; long a,b,c; cin>>t; for (int i=1;i<=t;i++) { cin>>a>>b>>c; cout<<a+b+c-1<<endl; } return 0; }
      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Codeforces' judges use Windows operating system so long is 32-bit which is equal to int.

        You can run the following code on custom invocation:

        cout << sizeof(int) << '\n';
        cout << sizeof(long) << '\n';
        
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You should use long long (which is 64 bits) for the reason mentioned by alwyn.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I use IT for F,this is my solution https://mirror.codeforces.com/contest/1422/submission/94746466.Someone can help me,pls?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I use IT to solve F but it wrong answer on test 4.This is my submission https://mirror.codeforces.com/contest/1422/submission/94746466 .Can someone help me,pls?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you explain your logic for F , i haven't understood the editorial.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think lcm(a,b,c,d)=lcm(lcm(a,b),lcm(c,d)). so I manage my IT 's node: node[i](l->r) is lcm of a sequence from a[l] to a[r] node[i]=node[i*2]*node[i*2+1]/__gcd(node[i*2],node[i*2+1])

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Yeah, problem E can be solved without hashes. Here's my solution and I think it is more delicate. I used an array better[i], which means "is the lex order better after deleting character i and only i in the stack". The logic is way more simple than I thought during the contest, and the core logic is actually expressed in less than 10 lines! Refer to my code for more details.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

NVM, already answered here

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help me the problem F. 94925909. I have tried a lot of test cases and my answer is always right. But it wa on test4.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am wondering if anyone can take a look at my submission for problem E. It gets WA 46 and I have accounted for the issue of not removing pairs which are not adjacent in the original string. I have looked for a while and I am not sure what else is wrong, any help is appreciated!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am wondering if anyone can take a look at my submission for problem E. It gets WA 46 and I have already accounted for the issue of removing pairs of indices which are not adjacent in the original string. I am not really sure what else is wrong, a hint or a break case would be greatly appreciated!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Failing test case:

    Spoiler
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I just think the best name for problem F is "The real Forced online Query"

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Because I have seen one named "Forced online Query" can be solved by offline method QAQ

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It is wrong that in A task the answer is (a + b + c — 1). To tell the truth, before giving the solution that passed all the tests I tried (a + b + c — 1) as the answer and it did not pass.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

About Problem E, I have understand the solution of author, but I can't find what's wrong with my way. My approach is based on 2 conclusion (which may be wrong): ⁣1. For any suffix, the maximum continuous prefix which consists of the same letters should either not be removed once, or be removed as much as possible. ⁣2. If the first char right side of the prefix is smaller than chars in prefix, we should remove pairs in prefix as much as possible, otherwise we should not remove any pairs in it. ⁣So I traverse the string from back to front, and follow the above strategy to remove pairs greedily. If I removed a pair, I will mark it to avoid to remove chars not adjacent afterwards. ⁣ ⁣Finally I got WA on test 46, and I am very confused. Can someone help me find the bug?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please help me on Problem C. I have written my code and it is working but fails in TC6. I have also checked with other TC's on the problem and it works fine and I am not able to understand the problem in my code.

https://ide.codingblocks.com/s/360158

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    What is your idea behind this code? how your solution works? is very difficult to see a code without know what are you thinking with that.

    What $$$ digit[i] $$$ and $$$ sm[i] $$$ does mean in your code?

    And what your functions int fxp(int a,int b,int m) and int m_m(int a,int b,int m) are supposed to do?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Apology for not mentioning the necessary information.

      My idea for this problem is the calculate the contribution of all the digits in all the possible ways in which we can remove some digits except that particular element.

      eg:- 1213121 Let's say we can calculate the contribution of digit 3

      Case 1 => digits which are before 3 would not change the decimal place of 3, so we simply need to add the total number of ways in which we can remove some digits before 3 and multiply with it decimal value i.e 3*10^3.

      Case 2 => digits at the right of 3 will change the decimal place of 3, so here we add the contribution of 3 on the based of its decimal place.

      1. If single elements are removed from the right then its decimal place would be 10^2 and we have a total of 3 ways to do that. Total = 3*10^2
      2. If two elements are removed from the right then the decimal place would be 10^1 and we have total of 2 ways to do it. Total 2*10
      3. And last if we remove all the elements from the right of 3 then Total = 1*1.

      Total right contribution = digit*(300+20+1) = 3*321

      Total contribution of 3 = Left + Right ==> 3*10^3 + 3*321

      This thing we apply for all the digits. For the above example

      power[]=1 10 100 1000 10000 100000 1000000

      sm[] = 0 1 21 321 4321 54321 654321 7654321

      sum_n() = calculates total number of was in which we can remove some digits i.e (i*(i+1))/2

      This is my Idea. If there are some bugs then please help me to detect them.

      And function like int fxp(int a,int b,int m) and int m_m(int a,int b,int m) are just part of my template. They do not perform any function in this code.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I found the bug.

        your solution with some changes of mine: 96360406

        You just didn't pay attention to the operations module, normally after each operation you must modulate the operands, when you don't do that an overflow can happen (even using long long), so, I just used the module after each operation and everything worked good. (I used the module in the function int sum_n (int n) too).

        After that, i can only congratulate you with that brilliant solution :D

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thanks a lot, man!!!. I could have never check that error. Literally thanks, man.

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Alternative solution for C:

$$$ \sum\limits_{r = 1}^n (f[r-1] . 10^{n-r})+(suffix[r+1].r) $$$

Where:

$$$ n $$$ = length of the number given at input.

$$$ suffix[i] $$$ = number formed by the suffix that ends at i position.

$$$ prefix[i] $$$ = number formed by the prefix that ends at i position.

$$$ f[i] = prefix[i] + f[i-1]$$$

The above formula is a faster way to calculate all of $$$ g[l][r] $$$, where $$$ g[l][r] $$$ is the number formed without the segment $$$[l,r]$$$:

$$$g[l][r] = prefix[l-1] .10^{n-r} + suffix[r+1]$$$

My solution: 96168877

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for your kind help. I understood your approach but if you please help to find the bug in my code, It would be very kind of you.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please can someone explain in problem B, why taking mean of 4 numbers won't work?? sorting the 4 numbers and taking the mid element seems to work but why doesn't mean work ??

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

QB

is there any proof that the most suitable number is the median?