AhmedSoliman's blog

By AhmedSoliman, 7 years ago, In English

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!

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

| Write comment?
»
7 years ago, # |
  Vote: I like it +26 Vote: I do not like it

a bit late for Chinese users.

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

    Yes. It's late for me and I will fell a bit tired during this contest.

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

    have to stay up late again :)

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

    I slept for it at noon

»
7 years ago, # |
  Vote: I like it +45 Vote: I do not like it

It is raining contests!!!

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

    5 rated contest in 6 day :))

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

      and after this, 6 days without contests :))

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

        and after this, there will be Codeforces Round #466(a rated contest) :))

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

    For me, it was more like a storm, losing 224 points in 6 days! :D

»
7 years ago, # |
Rev. 3   Vote: I like it -46 Vote: I do not like it

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 years ago, # |
  Vote: I like it -28 Vote: I do not like it

Once again, the purple problem setter.

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

CODEFORCES is on fire ..!!!

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

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 years ago, # |
  Vote: I like it +23 Vote: I do not like it

»
7 years ago, # |
Rev. 2   Vote: I like it -39 Vote: I do not like it

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 years ago, # |
  Vote: I like it +37 Vote: I do not like it

GUC D:

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Good luck

»
7 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Hope it will be a bit harder than the last one

  • »
    »
    7 years ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +74 Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Hate geometry :(

»
7 years ago, # |
  Vote: I like it +73 Vote: I do not like it

More like Mathforces today.

»
7 years ago, # |
  Vote: I like it +81 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Hackless Round!

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

    Nonetheless, I hacked one solution in my room)

»
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +135 Vote: I do not like it

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

A lot of problem C gonna hack this contest

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 years ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve c?

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

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 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

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

            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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +122 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, that is why it wasn't required to remember their names. :P

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

    yeah, i get confused by C problem, because they have similar name.

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

      Yeah, I was confused why doesn't he wants his own laptop to get the wifi. Weird fifa dude.

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

Does anyone know what test 6 D would look like?

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

    wtf pretest 6 don t love me also 7 submission too badd

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

    I have WA6 in D. I have forgotten put some code in else block, so when s1[i] = s2[i] = 0, my solution changed ans twice So i think there is such i that s1[i] = s2[i] = 0

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

    Edit: nvm lol

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

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 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Dat test:

    3 2
    0 1 0
    1 2 1

    In first position you can write just 2. Then whatever what you write in third position. So real P / Q = 1 / 2 and ans is 5000000004 while your answer is 750000006

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

    Not sure if the approach is wrong or not but there is atleast a overflow.

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

    The first what I saw is that in your power function long longs are missing (t*t can overflow).

»
7 years ago, # |
  Vote: I like it +76 Vote: I do not like it

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

    Or throw his laptop against the wall. Problem solved!

»
7 years ago, # |
  Vote: I like it -72 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it -68 Vote: I do not like it

      The whole idea of geometry problems are shitty and awful

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

      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 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

Anyway, nice problem and problemset also, thanks :D

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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 years ago, # |
  Vote: I like it +87 Vote: I do not like it

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 years ago, # |
  Vote: I like it -126 Vote: I do not like it

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

    The problems were excellent.

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

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

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

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

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

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

    in first else if it should be a[i] < b[i] in solve() I think?

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

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
    Rev. 3   Vote: I like it +11 Vote: I do not like it

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

      What exactly is M ?

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

        M is the mod, which is 1000000007. Since M is a prime, φ(M) = M - 1.

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

          So I should first calculate RES = Q^-1 your way and fast exponentiation and then print P*RES mod MOD ?

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

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        After getting P and Q divide them with gcd

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

          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 years ago, # ^ |
            Rev. 3   Vote: I like it +9 Vote: I do not like it

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

            and that is unique

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

              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 years ago, # ^ |
                  Vote: I like it +6 Vote: I do not like it

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

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

                  sh** you are so right, thank u very much.

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

    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 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +155 Vote: I do not like it

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

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 years ago, # |
Rev. 7   Vote: I like it +19 Vote: I do not like it

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.net/contest/935/submission/35502661

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

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

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

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Could someone explain how to do D?

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

    Let P(x) be the probability that a[i] = b[i] for i < x and a[x] > b[x]. Then the answer is because probabilities. To find , we observe that , so we can just compute numerator and denominator mod M at each step.

»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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.net/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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

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

      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 years ago, # ^ |
        Rev. 2   Vote: I like it +7 Vote: I do not like it

        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 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

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

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

    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 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.

»
7 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    http://codeforces.net/blog/entry/57702?#comment-415778 so far it's been at least 2 solutions affected by this :|

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

      In your solution you at least say "when the ranges are small". Mine is simply "screw it, YOLO, let's try them all" :)

      On an unrelated note: while my solution to E from the contest failed because I forgot to check if P>100, solution in upsolving passes with wrong check containing < instead of <=. It isn't going to work well for a case with P>100, M=100.

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

awesome C :)

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

I think I can get up,but...

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

A bit late for coach Marcil!

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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