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

Автор AhmedSoliman, 7 лет назад, По-английски

Hello, Codeforces!

I'd like to invite you to Codeforces Round #465 (Div. 2) which takes place on Monday, 19 February 2018 at 19:35 MSK. The round will be rated for division 2 participants. However, as usual division 1 can take part out of competition.

The round is prepared by my friends Kammola, Ahmad_Elsagheer, MostafaAbdullah and me (AhmedSoliman). Besides, many thanks to 300iq, mike_live, Arpa, GreenGrape and FalseMirror for testing the round, KAN for coordinating the round and MikeMirzayanov for the great Codeforces and Polygon platforms.

You will be given 6 problems and 2 hours to solve them. The scoring distribution will be announced later. Good luck!

UPD1: Scoring is 500 — 750 — 1250 — 1750 — 2250 — 2750

UPD2: Congratulations to the winners!

Division 1 :

  1. Benq
  2. eddy1021
  3. KrK
  4. kmjp
  5. chemthan

Division 2 :

  1. Iiu_runda
  2. FlzzyDavid
  3. baggins
  4. sorry_teamskiy
  5. InkyFlameMaster

UPD3: The Editorial is available now!

Thank you everyone!

  • Проголосовать: нравится
  • +480
  • Проголосовать: не нравится

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

a bit late for Chinese users.

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

It is raining contests!!!

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

So many writers/testers/coordinators for a div.2 contest! What I mean is that I do appreciate the effort put on this contest and do not mean anything in a negative way.

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

Once again, the purple problem setter.

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

CODEFORCES is on fire ..!!!

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

Unfortunately, I misread the C problem, I passed 4 problems, but the score is very low, I did not have the chance to have the first time to make 5 problems T.T

It seems that I need more practice.

Look forward to the next contests

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

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

The Announcement is 8 days before the contest. Lets hope the scoring will be announced early like the announcement.

UPD: It wasn't in the main page

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

GUC D:

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

Good luck

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

Codeforces is smashing , it is going wild , i think today or tomorrow there will be something named "contest overflow"...

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

Hope it will be a bit harder than the last one

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

    Agree! Hope problem statements are not long or thick, but hard.

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

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

Hate geometry :(

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

More like Mathforces today.

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

One more task and this would have been a beautiful regular round with two divisions.

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

Hackless Round!

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

I think there has been some work on making problems more shitty than they were like in problem E

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

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

A lot of problem C gonna hack this contest

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

Note: Sorry for my bad english.

So, at Problem C the ideea is to find the radius of the biggest circle Which has the laptop point and doesn't exceed the flat Area. This is relative simple The radius is (R+sqrt((x1-x1)^2+(y2-y1)^2))/2; But.. How can I Find the center of this Circle? That is the question. :)

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

    Required radius

    The center will be the point at above calculated distance r in the direction of (x1, y1) from (x2, y2).

    Let P1 = (x1, y1), P2 = (x2, y2) and . Then center should be at .

    Handle the P2 outside apartment and P1 = P2 cases separately.

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

    Find distance from laptop to center of the given circle. That plus the radius will give the diameter of the circle you want. The center of this circle will be at the midpoint of this line, which you can find with a bit of trig or by using ratios

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

    you can use some maths let center of flat to be (0, 0)

    phi = atan2(y2, x2)

    x3 = -R * cos phi y3 = -R * sin phi

    (x2, y2) — (x3, y3) is diameter of circle you need.

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

how to solve c?

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

Someone can explain how to do the C problem? How can I maximize the area of the circle? My only thoughts was achieving this by some binary search...

My general ideas all surrounded something like that: if Fafa's laptop is outside or at some flat's end, then the answer is all flat's area. If not, then choose the center whose maximize the area. This is the right way to do?

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

    you have a line which connects fefa and the room center. extend that line. find the point on the line which lies on the circumference call this P. your coordinates -> midpoint of P and fefa. radius is the distance b/w them — 0.000001~.

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

    Even though I got hacked, I think I have the right idea.Let point a be centre and b be point where laptop is. The answer radius is obviously (r+dist(a,b))/2. You can also get distances from the center and the laptop, which are (r+dist(a+b))/2 and (r-dist(a,b))/2 respectively. Then you can apply external form of section formula to get the coordinates of the center.

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

    Here is my approach.

    First of all, if Fafa is on the border of the flat or outside of the flat, Fifa can place the access point at the center of the flat, and set the radius exactly equal to R.

    If not, we can see that the biggest area will be something like this:

    To obtain such an answer, at first we have to find the other vertex of the orange segment (one vertex is Fafa's laptop location). We can calculate that through geometric vectors.

    After that, we can obtain the access point's location: it will be the midpoint of the orange segment. The radius will be half the length of that segment.

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

      Well, more simple than i thought. I drew some drafts like yours but could not realize how to find the position of the second vertex. Thanks!

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

      Can the boundary of our circle pass through fafa's location?

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

        Yes. The 2nd sample test confirmed that ;)

        With the input 10 5 5 5 15 and the output 5.0 5.0 10.0, we can see that:

        • Fafa's laptop is right on the boundary (its distance to the center is 10, which is equal to the flat's radius).
        • The flat's circle and the correct access point's circle are equivalent.

        Therefore, the access point's boundary can pass through Fafa — and he still gets no coverage at all.

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

          Ok cool,...I submitted and I was afraid about this case..

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

            Same to me. I even had to use plotting program to make sure that it lied on the boundary, though it could be calculated algebraic-ly. :P

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

      That feeling, when you are solved the problem C by binary and ternary search... http://codeforces.me/contest/935/submission/35499682

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

Fifa and Fafa? Really? What about Fofa? And Fafi? And...

Joke aside, it's usually better to have easy to differ names (e.g. Alice and Bob). Otherwise it can be really hard to follow the problem statement while remembering who is who.

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

Does anyone know what test 6 D would look like?

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

Hi, how to solve E?

I have a solution if there has no constraint of P & M, that is: Greedily choose '+', but if expression satisfies |E1 — E2| > |E1 + E2| and it's not leftmost expression, choose '-', such that the answer is optimal.

But I have no idea about with constraint of P & M.

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

    Use dynamic programming.

    • hi[i][j] is the maximum value of the ith expression with j pluses used within it

    • lo[i][j] is the minimum value of the ith expression with j pluses used within it

    Transition states are relatively straightforward, but it is a bit tricky to implement the dp order correctly. Final complexity is O(E2).

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

can someone tell me why my approach for d is wrong https://ide.geeksforgeeks.org/TGNpoGcVTH

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

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

I think the problems are sorted by how shitty they are but then I think about problem C and how awful it was to implement.

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

    C wasn't particularly hard to implement for a geometry problem. There was only one extra case to take into consideration: (x1, y1) = (x2, y2). Other than that, the implementation was relatively clean.

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

      The whole idea of geometry problems are shitty and awful

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

      Apparently, Fafa's laptop can be outside the Flat too. Test case 3 shows this. This is another case I guess. Personally I felt the problem had incomplete information/ is misleading. Why say that Fifa and Fafa share a flat together when Fafa's laptop can be outside the flat?

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

        The problem specifically states The flat is centered at (x1, y1) and has radius R and Fafa's laptop is located at (x2, y2), not necessarily inside the flat. Plus, there is that test case. There was absolutely no ambiguity.

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

          I understood that. All I was saying is it was said Fafa and Fifa share a flat in the problem. Many people misunderstood this as Fafa always stays inside the room.

          UPD : It is mentioned in problem that Fafa's laptop is not necessarily inside the flat. I guess I missed it.

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

I think some drawing would have made C easier to understand :\

Anyway, nice problem and problemset also, thanks :D

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

Spent half of my time minimizing the 'uncovered area' which not at all required. And like kirjuri said, assumed Fifa and Fafa as Fifa. Problems were good but statements could have been made better.

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

Wow, I'm impressed. The problems included some interesting Egyptian background, which I enjoyed. The last problem was tricky for me, and I spent much time thinking, fixing the code and analysing special cases. Personally, I had a great time. Thank you very much!

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

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

    The problems were excellent.

    We didn't perform well doesn't imply that the problems were bad.

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

    Problems were of a good quality. Only I didn't like the naming convention of Fifa and Fafa :D

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

Can someone please tell me what's wrong with this solution to D : link?

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

Finding centre of the circle after finding the required radius can be done by the sector for external divison in problem C(handling corner cases differently)

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

For problem D:

P is number of valid changes, Q is the number of all changes. The result is P/Q mod MOD ...

How to calculate P/Q mod MOD ? I thought about modular multiplicative inverse but I couldn't implement it...

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

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

      What exactly is M ?

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

      But wait,if you do it that way, it means that the answer is going to be just Q^(mod-2) * P and it is not necessarry for those 2 to be co-prime. Then it won't work. For example for sample 3 the answer is 16*25*24*23 / 26*25*24*23 . So we need to find the modular inverse for 26*25*24*23 and multiply it by 16*25*24*23 and output it %(1e9+7). If i do that in the 3 sample i get the wrong answer. We need an ireductible fraction, so how to get it?

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

        After getting P and Q divide them with gcd

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

          How to divide P and Q by GCD if they, while being calculated, will be % mod because during the calculation there will be for sure values bigger then 10^18. So applying gcd so make it ireductible just doesn't make sense.

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

            We don't actually need to divide by gcd because of how mod works.

            and that is unique

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

              So what you're saying is that just by calculating the answer randomly and getting P%mod and Q%mod, then calculating Q^(mod-2) and multiplying by P we get the correct answer??

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

                You don't even need to maintain p and q separately, just multiply by the inverse element every time you need a division.

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

    ll realMod(ll num, ll denom, ll MOD){ for(int i = 0; ; i++){ if((num + MOD*i) % denom == 0){ return (num + MOD*i) / denom; } } }

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

    P/Q mod MOD means we're looking at P*x mod MOD where x is the modular inverse of Q mod MOD, which means that Q*x mod MOD = 1. So, Find the modular inverse MI for Q mod MOD. P*=MI; ans=P%MOD;

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

      It doesn't work if you do that for the third sample, we need an ireductible fraction before we do the modular inverse thing, so p and q must be co-prime before applying modular inverse to Q.

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

    Another way to calculate it is to use the Extended Euclidean Algorithm, that is given a and b, find integers x and y such that ax + by = 1. If we set a = Q and b = M, then 1 = Qx + My = Qx (mod M), so x = Q^{-1} (mod M)

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

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

Can someone say if this method for problem E would work?

lets say we process expressions in decreasing order of nesting.Dp[i][2] denotes the maximum and minimum value of that expression.So now we can make transition easily to lower nesting .

Sorry if this question is too naive.

»
7 лет назад, # |
Rev. 7   Проголосовать: нравится +19 Проголосовать: не нравится

Problem C using ratio and proportions

Question

UPDATE (It is Correct)

There is nothing wrong with this solution. It is actually correct. As people below pointed out I didn't check for integer overflow and printed wrong variables. After I fixed that I got AC

SOLUTION : http://codeforces.me/contest/935/submission/35502661

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

Классный раунд, спасибо авторам!

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

Can someone please point out what is wrong with my code for C? http://codeforces.me/contest/935/submission/35496680

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

    Shouldnt this if((dist+r<=R)) be 2*R in the last if which do not have matching else?

    Edit: it passed with 2*R at both places

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

      Thanks for your reply! But No, I think the condition was right (condition for a circle to be inside another circle), I found the mistake ,it should have been. if((dist+r-R)<=0.000001) It passed with this.

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

Solved the first two problems as fast as I could.Then saw FIFA my eyes lit up :) but it took forever to actually get it AC.

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

The radius is the same as in the correct answer, why is it WA?

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

Could someone explain how to do D?

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

Sadly my incorrect F passed systests. I incorrectly thought that the minimum difference would just subtract -1*diff instead of -2*diff during the contest and when the ranges are small I just passed through the whole range to get the best answer.

30

1000 990 980 970 960 950 940 930 920 910 900 890 880 870 869 870 880 890 900 910 920 930 940 950 960 970 980 990 1000 1010

1 1 2 29 1000

This case breaks my solution (it prints 2269 instead of 2268, it should choose the 869). http://codeforces.me/contest/935/submission/35492061 this is the wrong submission. This is a small mistake from me that usually wouldn't happen to anyone but I hope that the tests didn't impact any rating (the implication of this is that there's no big query where it's better to get an i where a[i — 1] > a[i] and a[i + 1] > a[i]).

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

Can some one please tell me what is wrong with my solution the radius i am getting in the test case 14 is correct but the checker comment reads "wrong answer Too large radius." link

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

    You should output more digits after the decimal point for the x and y values, my guess is that there is some point on your circle that is outside the given circle by more than 1e-6.

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

    just print more digits after the decimal point. e.gcout << fixed << setprecision(10) << x << endl;

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

      Thanks bro after changing it to cout << fixed << setprecision(9) << x << endl it got accepted but in my previous submission i wrote cout<<setprecision(9) in the beginning. Are these two ways of setting precision to 9 two different things?? BTW Thanks for the help.

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

        The fixed specifies that you want the specified precision to be applied only after decimal point. without it, it'd just output a total of 9 digits, the first 9 from the left, regardless of whether the digit is after or before the decimal point.

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

I got confused by Fifa Fafa Fafa Fifa Fafa Fifa Fifa Fafa

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

Can you please suggest what is wrong with this solution for problem D: https://ide.geeksforgeeks.org/el12hkWIU0 ?

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

    when you did this:

    if (!a[i] && !b[i]) r = (m * solve(a, b, i+1) + m*(m-1)/2) % MOD;

    the denominator should change to m*m but at the end you are still dividing by m only.

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

Hi, I submited a code (35493900) in the contest for problem c and it gave Idleness limit exceeded!!! but after the contest I submited the same code (35503114) and it was accepted!!! I was wondering if you could fix this problem and fix my score !!!!!!!!!!!

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

I got the message below after competing in this round. I did not cheat or attempt to cheat during the contest. Furthermore, I worked locally on my own computer. Could you please take a look at this issue? The odds of submitting a very similar code for a div 2 A problem are rather high. Thanks!

Attention!

Your solution 35483271 for the problem 935A significantly coincides with solutions HSNBRG/35477249, wertzu/35483271. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.

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

Random observation regarding test data in problem F:

solution which says "OK, in case there is local maximum — let's pick it, otherwise let's check all possible moves in O(N) per query" passes easily without any additional tricks or optimizations. 35497796 is an example (obfuscated though, since it was originally an attempt to code correct solution).

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

awesome C :)

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

I think I can get up,but...

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

A bit late for coach Marcil!

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

F problem. I think we should add such data.

5

2 3 1 1 1

5

2 5 5 2

2 3 4 3

1 4 4 1

1 3 5 2

1 1 1 1

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

Can someone please tell me what's wrong with the following approach for problem D? :

For each i, I find the number of ways that all the letters upto i - 1 are the same, and a[i] > b[i].

Then, the number of ways for each index is p = x * pow(m, unknown[i + 1]) where x is the number of possibilities of a[i] > b[i], with different possible conditions, and unknown[i + 1] is the count of erased numbers in either a or b, from i + 1, to the end.

Also, I multiply to p, pow(m, bothZeroes), where bothZeroes is the number of indices up to i - 1, at which a[i] = b[i] = 0, because any 1 of the m numbers could be chosen for such indices.

But, I looked into this code, and he hasn't multiplied the pow(m, bothZeroes) part to his answer. What's wrong with my approach, and how come the m^bothZeroes part isn't required?

Link to solution.

Will be glad if someone could help. Thanks in advance.

Edit : p is not the probability, it's the numerator part.

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

why fifa and fafa ???? can't you use good names ??? i got confused while reading the statement , fifa.. fafa.... fafa... fifa.... what the hell