Edvard's blog

By Edvard, history, 8 years ago, translation, In English

Hello, Codeforces!

Educational Codeforces Round 13 will take place on 13 June 2016 at 19:00 MSK for the first and the second divisions. Almost two months passed from the previous round. That is due the next reasons: 1) I coordinated regular CF-round at the end of April; 2) about whole CP community were busy with preparing and competing in ACM ICPC WF in May; 3) at the beginning of this month I start to work at AimTech (I hope that I'll have enough time to continue prepare ERs).

<It's need to read at least once maybe you'll find something interesting>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks (of course the difficult tasks are also needed). Please send only the problems for which you know the solution with clear statement (the story is not required). And also please add one or two samples to make the problem statement more clear.

</It's need to read at least once maybe you'll find something interesting>

The problemset was suggested by Codeforces users. The problem А was suggested by user Abdrakhman Ismail bash. The problem B was suggested by Arthur Jaworski KingArthur. The problem C was suggested by Sheikh Monir skmonir. The problem D was suggested by Zi Song Yeoh zscoder (there are a lot of unused his problems). The problem E was suggested and prepared by Alexey Dergunov dalex. The simpler version of the problem F was suggested by AmirMohammad Dehghan PrinceOfPersia.

Thanks a lot to them and all others who are sending the problems! The number of unused problems are increasing. If I didn't miss anything I already replied to all who sent me the problems at least 5-6 days ago. Please be patient if your problem was not used a long while.

As I said the problem E is prepared by Alexey Dergunov dalex. All other problems was prepared by me (Edvard Davtyan). Thanks to Tatiana Semyonova Tatiana_S for checking the English statements. The problems was tested by users suggested them, respectively: Abdrakhman Ismail bash, Arthur Jaworski KingArthur, Sheikh Monir skmonir, Zi Song Yeoh zscoder, Alexey Dergunov dalex and AmirMohammad Dehghan PrinceOfPersia. Thanks a lot to all of them!

I hope you will enjoy the problems! Previous time the problems were too hard. I've tried to fix that. The problems should be simpler than usual.

Good luck and have fun!

UPD: The round is finished. The editorial is published.

It's the first summer round :-)

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

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

Where is Delinur?

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

    They don't need her since Edvard is a native Russian speaker and he also knows English (obviously!) and Tatiana Semyonova has checked English statement.

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

      Usually I'm translating the problems by myself (it helps me to improve my English) and the interpreter (Maria and now Tatyana) just checking the problem statements and making fixes.

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

        Interpreter — это тот, кто устно переводит. В данном случае наверное надо было использовать translator. By нужно убрать перед myself. Дальше у вас со временами все перепутано

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

    Actually, Maria left the project, she asked to convey greetings and best wishes to all people on Codeforces! Tatyana Tatiana_S Semenova agreed to help us with English :-)

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

      I did not know her handle and could not find it. Now I'll add it to the post.

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

      Mike, I want The Educational Codeforces is rated *. *

»
8 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Couldn't give the previous one....had been waiting for this one for long! Excited! Hoping for a matrix exponentiation problem...I never solved it in a contest!

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

"It's the first summer round"

No here, I'm freezing

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

I know this if Off topic. But Believe me, my rating was 1905. Any changes in rating system?

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

Is this round being delayed for 10 minutes?

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

Well, I know what is needed to solve F and I also know that I can't code it so I quit, good luck! :D

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

    Can you tell what was the idea behind solving F??

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

    That's why you're purple. I used to had this "well, it's obvious this problem can be solved by persistent 2D segment trees with heavy light decomposition built on linkcut trees, hire monkeys to code it for me" and walk away proudly for coming up with such a 'brilliant' solution, but I discovered that's not the way one should follow. In half of cases it turns out such problem has some nice tricky solution using very simple techniques and in half of cases it turns out solution is in fact what I thought, but still a lot of people have no troubles with implementing it which is a sign that I should definitely improve my coding skills in that area. Treat contests (especially educational rounds) as opportunities to learn not just the place where you solve problems which you already know how to solve.

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

      After becoming red approach changes, right? :p

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

        Looks like he hired monkeys to code it for him, or coded all the stuff like a monkey himself.

        This way he can be smart in the discussion:

        • Yes, think carefully about nice and tricky ideas and maybe you can become red (like me) someday.

        While copy pasting ton of stuff on every problem in 2 minutes, get the whole problemset done in 10 minutes and red color very quickly :P

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

          I didn't want to say "I invent tricky ideas, so I am red", I wanted to say "Stop giving up, that is not the right way to progress" and "Sometimes appropriate way to solution leads through tricky ideas and sometimes it leads through fighting one's weaknesses with coding something, and surely it doesn't lead through being satisfied with coming up with complicated solution". "I am not able to do this, so I won't even try" attitude is the worst way to improve your skills.

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

        What I said here and copying prewritten code are kinda irrelevant. "hire monkeys to code it for me" was the key part. Main point here is that one definitely should not treat coming up with solution as all the logical difficulty and implementation as dirty duty one can omit and be satisfied (as I used to on high school). Another thing is that as long as code is prewritten by me and contest rules allow me to freely copy-paste it then if it helps me getting fast AC I feel the right to be fully satisfied with it — such scenario is rather the exact opposite to scenario of getting no AC at all which we are talking about.

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

          Edit. The reply should be to your upper comment. I got confused by the comments tree :)

          My comment refers to "That's why you're purple".

          Basically it suggests that red coders either find a nice and tricky idea or have such a good coding skills that can implement a complicated idea quite fast. Which means red coder = very smart or skillful and not red = !(smart or skillful) = !smart & !skillful.

          You forgot to add that you also use additional approach. You got such a huge library, because of spending a lot of time on problem solving and practicing/participating in many contests, that you can just copy-paste most of the complicated stuff.

          This changes things a lot as it means red coder = ((1) very smart or (2) skillful) and (3)having a lot of practice and a lot of libraries.

          And in this case not red means !(((1) | (2)) & (3)) so smart and skillful meets that criteria.

          This was example of discrimination by cf color. I don't know why do you think that once you are red, you can treat not red as somehow worse and less talented.

          I think that being high rated in short competitions really means 2 things:

          • you are extremely smart

          or

          • you can afford to spend tons of time on participating in the contests and solve a lot of problems 12 hours per day. This way you can become a really skillful and have enormous library of code, which gives you additional advantage in such type of contests.
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Maybe "That' why you're purple" was oversimplification, because at any point I didn't want to address the actual smartness or abilities to code some particular thing, so I would like to cut out part of the discussion regarding to being smart, having a lot of practice, having developed library etc. which are of course important factors of someone's colour, but they were not what I was going to point at what may have been a reason for a little misuderstanding.

            Only thing I wanted to focus on was the attitude when facing problems. From my own experiences I can say that difference between purple me and red me is surely also a lot of practice, but also very importantly revolutionizing my way of thinking. No matter of someone's current abilities to code and smartness, "I am not able to do this, so I won't even try, good luck" attitude is a place for severe improvements (no matter whether "I am not able to do this" part relates to coming up with solution (which connected with "so I won't even try" never has been my point of view) or coding a solution (which was exactly exactly very often my point of view in past and I am not happy with this, but fortunately it is no longer the case)). My initial comment's main purpose was in fact to be a purely motivational one.

            Btw on a completely irrelevant note, you made it seem like copying prewritten code is essential part of today's competitive programming. In fact (apart from template) I copy some codes from library in approximately one in 20 problems.

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

            My personal red experience is that "whatever you say can be used against you", that is, no matter how careful you are, something you say is going to be perceived as arrogant by someone (hell, some people told me they thought I was arrogant before they had the chance to talk to me!). So I'd say at least a large part of this discrimination you mention can be attributed to the lower-rated contestants themselves.

            That being said, here's a simplified version of Swistakk's statement:

            "Programming contests consist of coding and implementation, so if you want to be a very good contestant you need to practice both, not only one of them".

            Sounds like really good advice to me (and I should follow it more often, my implementation skills are crap)

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

      Could you givgive an example of such a problem (requiring all techniques you mentioned)?

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

what is wrong with my code it is failing on test 5 http://sprunge.us/iFNf? THe code is for problem D.

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

    I think, we cannot simply divide like this: second = (B*((tmp-1l)/(A-1l)))%MOD;

    Probably there is a smarter way to deal with modular division.

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

    (a/b) mod m is not equal to a mod m / b mod m so you cant divide by (a-1) so easily. you should use modular inverse

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

    Instead of dividing (tmp-1) by (A-1) directly, (tmp-1) can be multiplied with the modular inverse of (A-1). UPD: I did this but my solution got hacked anyway.

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

    Here Scroll down to the modular inverse part!

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

    By Euler's theorem, you can use ((divisor) ** (mod - 2)) % mod to divide if mod is prime. In this case, divisor would be (a — 1) and mod would be 10 ** 9 + 7.

    https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

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

That N = 1 case in E. -_-

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

How to solve problem E?

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

    i think dynamic programming, like hamiltonian cycle but im not sure, i couldnt make it pass test 4

    http://codeforces.com/contest/678/submission/18433012

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

    I tried DP, but its complexity is bad.

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

    You need to find an order which maximizes your probability of winning. This is a standard Bitmask DP.
    My solution : code

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

      What to search for to get this standard dp problem?

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

      Your code is a little messy , so can you tell me the DP states you used?

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

        Lets define DP[mask][prev_winner] as the max probability such that we have covered people in mask and prev_winner is our winner.
        Now we try N * (N — 1) possibilities for first 2 position and try to find the max ans.
        Transition is :
        if prev_winner = 0:
        DP[mask][prev_winner] = max(prob[prev_winner][i] * DP[mask | (1 << i)][prev_winner]) for all i's which we have not seen.
        else:
        DP[mask][prev_winner] = max(prob[prev_winner][i] * DP[mask | (1 << i)][prev_winner] + prob[i][prev_winner] * DP[mask | (1 << i)][i]) for all i's which we have not seen.
        I hope this helps.

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

          Now we try N * (N — 1) possibilities for first 2 position and try to find the max ans.

          I thought we have to consider two disjoint subsets and use their maximum values for the union of these subsets. I can't prove why we only need first two positions. I'm missing something very obvious, possibly.

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

          I don't understand these formulas:

          "DP[mask][prev_winner] = max(prob[prev_winner][i] * DP[mask | (1 << i)][prev_winner]) for all i's which we have not seen."

          It means that in order to cover people in mask you look at all the masks with one more people, you ask what is the probability that 0 will win among all these people and then you calculate the value for the mask with the smaller amount of people. It looks like your final state is dp[0][0]?

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

            Final state for DP is dp[(1 << n) — 1][0]. I add one more person into mask and ask what is the probability that the person I want to win is the winner. And I split the dp based on whether I have seen 0 or not. So above formula is for the case when I have seen 0 (what is the probability that 0 is the winner when I add one more person into mask). Other formula covers the second case as both of them can win.

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

        A simple way is to set dp[mask] = best probability for Ivan to win among people with bit=1 in the mask.

        18433677

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

          How do you prove that only mask is important? I believed that the last winner is also important, but stress-test of your solution says that it isn't.

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

            I choose two fighters to move between dp states, maybe this confuses you.

            So basically for a given mask we can independently get the best probability of Ivan to win. To compute this, we take maximum over all possible choices for next fight (choice of two fighters, possibly including Ivan).

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

              That's a nice solution, but it is very magical for me.

              If you choose the last 2 people it is against the rules, as you can choose only 1 last person.

              So if you are going to choose the last 2 people (i,j):

              • Ivan had to win in the mask without j, so now you multiply that by the probability that i beats j (and we know that i already got beaten by Ivan, so Ivan beats the whole new mask this way).

              or

              • Ivan had to win in the mask without i -> the same logic holds.

              I don't know how do the people come up with such ideas, but is there a way to do this problem more straight forward?

              Like you have the probability dp[mask] that Ivan wins the mask or dp[mask][winner] that winner wins the mask and you are selecting one player in each move?

              Despite being more straight forward, that solution would also reduce the complexity to O(n*2^n).

              Edit — it will reduce the complexity only in case with dp[mask] state.

              Edit2. Now I see that you are not choosing the last fight, as you can't do that. Ivan has to fight the last fight in each mask. You are choosing the best fight among all possible fights within the mask and you take the sum of 2 different outcomes of it. It is more clear now.

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

                Actually now I realized that I forgot that the winner from the last fight has to be chosen. That is, my solution assumes a tournament, where there are multiple fights with elimination in parallel.

                So I solved a different problem and that's why the solution seemed clear for me (and unclear for others).

                It is quite strange that this got AC.. Maybe it could be hacked? Though, intuitively, it would fall on large random tests, which I assume already exist in the set.

                Maybe this works because the strategy from the problem is indeed optimal? :)

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

                  Your solution works because:

                  dp[mask] = maximum probability that Ivan wins the mask.

                  If there is no Ivan in the mask dp[mask] = 0.

                  If there is Ivan in the mask, you choose the best tournament in that fight. You have 2 cases here:

                  a) You choose 2 fighters without Ivan and I explained that case above. That fight would happen in any but last position — my explanation covers that too. But to make it more clear: you don't care at which stage that fight would happen, the point is that the winner of that fight would be defeated by Ivan later.

                  b) You choose Ivan and another fighter — that fight has to happen as the last one.

                  So you evaluate the fight between 0 and i.

                  So your formula will take dp[mask^1]*prob[i][0] and this is 0, because dp[mask^1] = 0

                  • dp[mask^(1<<i)] * prob[0][i] — and this means that Ivan beats the mask without i and beats i in the last fight.

                  Which is exactly what we want.

                  That's why I said that it is a great solution with memory O(2^n) and was very impressed how did you manage to come up with this reasoning during 2 hours. It's interesting to see that you were thinking of something different :P

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

                  this explanation is wrong, lol

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

                  That's what I wrote in case a). In case b) you are adding the new candidate to the mask. The mask is already beaten by Ivan — so it will be the last fight with new candidate.

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

                  Are you sure every sequence can be made into a chain? For instance, what about 3 beats 4, 5 beats 6, 2 beats 3, 2 beats 5?

                  And even if that transformation is possible, the sequence of fights is not determined in advance (because as you said you can change it depending on prior results), so you wouldn't necessarily know what transformation to use.

                  It's very interesting that this solution works, but I think the explanation why is not that simple...

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

                  I'm not sure about a chain, but I can't see what is the problem with my explanation.

                  It is clear that you choose the most profitable battle. If Ivan is engaged, it is the last battle, no matter what was the order of the other battles.

                  If he is not engaged, that battle is not last, as the winner of it got already beaten by Ivan in the state we have calculated. So we can insert it everywhere, but the last position.

                  Your example doesn't include Ivan and for such case the solution immediately outputs 0.

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

                  I was replying to dalex's explanation, not yours, which I only read now. As far as I can see, you don't address the requirement that the winner of the last fight has to be part of the next fight.

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

                  Because we already reached the discussion depth limit — it is hard to say to which answer was the reply.

                  That requirement is addressed in the following way:

                  If Ivan won the last battle, he obviously will be participating in the next one.

                  Below part was edited:

                  I got lost in one case.

                  If you choose the battle between (i,j) and i won that battle. You know that in the dp[mask^(1<<j)] he was defeated at some point (as Ivan won the whole mask^(1<<j)). You insert that battle after the last battle won by i in mask^(1<<j) (which means that after i's victory we invite j to fight with him).

                  If i didn't win anything in mask^(1<<j):

                  a) If he lost in hist first fight, then add battle between i and j on the first position.

                  b) Otherwise there exists k, who defeated i and k had to win at least one battle (as i didn't loose the first fight). Let's say that k defeated r just before defeating i. And let's assume that r also defeated m.

                  Now it is clear that i and j have to fight in the first fight, as i didn't win anything in mask^(1<<j). After (i,j) should fight (i,k) and after that (k,r) but r would be defeated by k and it has also defeated m...

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

                  I constructed a case by ffao, which ruined the explanation about chains: http://ideone.com/QYmfXx... or not? Look what it outputs for mask 31 (after 5 defeats 6).

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

          My solution uses the same idea as yours, but I don't really know why it works! I just code it to see if it solved the problem, but I was skeptical. In my mask I store the participants that are dead, and try all possible pairs, and sum the combinations that result in only Ivan alive. The code turns out to be very simple but I don't know why it works! 18510404

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

      can you tell me what i did wrong here, please?

      http://codeforces.com/contest/678/submission/18433012

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

        Reads comment and then realises that it's pointless.

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

    I solved it using dp, Let f[s][i] be the probability that the jedi winns if s is the set of siths that are alive, and i the sith that won the last round. We can try over all possible siths j!=i, and over all possible outcomes (of the fight between i and j), of course we should chose the one that maximizes the probability that the jedi winns.

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

      But don't you have to deal with two subsets each time?

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

        Why two subsets? As you can see my recurrence use just one subset. Note that the set of died siths is the complement of the alive siths

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

          two mutually exclusive subsets , with one winner of each subset, fighting in the current round which covers union of both subsets.

          At least this is all I could come up with.

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

      @Alei : I do nt get in ur dp how u are ensuring that 0th index is the last winner. could u pls elaborate how uve done that.. or how is it implicitly taken care of.?

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

        ok got it now didnt read the base condition carefully.. very nice code :)

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

      Tnx for providing us with your clear and simple solution. :)

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

in problem E, how the sample gives 0.68??
Stuff that can happen so 1st person win are:
1 win 2, 1 win 3
1 win 3, 1 win 2
2 win 3, 1 win 2
3 win 2, 1 win 3

All this happen with 0.49333 probability.
What am i missing?

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

    Question asks to find the maximum probability which comes from this order 2, 3, 1.
    2 wins, 1 wins : 0.4 * 0.5
    3 wins, 1 wins : 0.6 * 0.8
    Total prob = 0.2 + 0.48 = 0.6

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

      Note that optimal choices can differ depending on the results of the previous battles. So talking about "order" is not correct.

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

PROBLEM C: It is wrong with my code?

#include <bits/stdc++.h>
using namespace std;
int main()
{  
 int n,a,b,p,q;
 cin>>n>>a>>b>>p>>q;
 long long  s=0;
 int na=0,nb=0,nab=0;
 na=n/a;
 nb=n/b;
 long long  z=(a*b)/__gcd(a,b);
 nab=n/z;
 long long  val= p>=q?nab*p:nab*q;
 s=(na-nab)*p+(nb-nab)*q+ val;
 cout<<s<<endl;

return 0;
}
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    z overflows try 1000000000 1000000000 1000000000 1000000000 1000000000

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

      the solution change the data type of the input variables int a long long

      #include <bits/stdc++.h>
      using namespace std;
      int main()
      {  
       long long n,a,b,p,q;
       cin>>n>>a>>b>>p>>q;
       long long  s=0;
       int na=0,nb=0,nab=0;
       na=n/a;
       nb=n/b;
       long long  z=(a*b)/__gcd(a,b);
       nab=n/z;
       long long  val= p>=q?nab*p:nab*q;
       s=(na-nab)*p+(nb-nab)*q+ val;
       cout<<s<<endl;
      
      return 0;
      }
      
      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        You can do: a / __gcd(a, b) * b

        To avoid overflows as the division will be carried out at first

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

    Why do you need __gcd()? What are you trying to achieve with the variable z?

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

      find the number of numbers divisible by two numbers given

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

        Interesting, I haven't thought about that. I've calculated that number with expression n / (a * b).
        It is good that the contest is not rated :)

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

    Probably (na-nab)*p overflows, try (na-nab)*1ll*p (and same with q). Or simply use long long for all vars.

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

Thanks, the problem really was easier than last time. Maybe you had to swap B and C. UPD. Take back a words about the B and C after start of hacking.

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

I sent two solutions for problem B that got OK. One of them was hacked, the other wasnt. But the table says I havent solved this problem. Why?

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

C was solved by 1500+. now it has become 900+. #HackEffect

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

Can someone tell me why my solution fails for C?


int main(){ long long int a,b,c,d,e; int cnt=0; scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e); long long int res = 0; long long int res1 =0; res= ((a/b)*d) + ( abs((a/b) - ((a/b+a/c)-(a/(b*c))) ) * e); res1= ((a/c)*e) + ( abs((a/c) - ((a/b+a/c)-(a/(b*c))) ) * d); if(res>res1){ printf("%lld",res); } else printf("%lld",res1); }
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Compiler got confused by cnt and abs, so it gave up =)

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

    You can't just divide by (b * c), it should be GCD(b,c). Consider this input: 6 2 4 1 3 Your code gives 6 as an answer, where it should be 5. Edit Wrote 3 instead of 6, corrected.

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

My first hacking attempt and i hacked 15 solutions for problem C

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

How could problem D be solved using matrices?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    a[0][0] = A;
    a[0][1] = B;
    a[1][0] = 0;
    a[1][1] = 1;
    
    this matrix multiplying with  
    [x 1] gives [A*x+b 1] and we can repeat this process..
    
    
    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      why a[1][0]=0 and a[1][1]=1??

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        Because of this 0 and 1 we get column vector with Ax+b and 1 from column vector of x and 1.and since Ax+B is our next x we actually have new x ,1 column vector.so this allows us repeating the process.but is actual program we will do the matrix multiplication in log(n) time rather than doing all the multiplications.
        
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Simpler way: you can exponentiate f itself: f^2 = (a*a)*x + a*b+b. Then use fast exponentiation to compute W,R from f^n = W*x+R:

    Python code:

    cur = x
    while n > 0:
        if n & 1:
            cur = (a * cur + b) % MOD
        a, b = a*a % MOD, (a*b + b) % MOD
        n >>= 1
    print cur
    
»
8 years ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

What is the hack case for D?

My solution is to find value An·x + (1 + A + A2 + A3... + An) * B. To find sum of GP, I use the standard formula with an exception case where A = 1, when GP sum = n. What is wrong with this 18423561

UPD: Mine was hacked due to overflow of GPSUM*b in special case as I forgot to take modulo with n and it overflowed even long long :(

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

    Overflow in gpsum * b is the problem here. I made the same mistake :(

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

I am getting overflow in Java7 at problem C when running this test : 1000000000 1 3 1000000000 999999999 My code: https://ideone.com/kHjrJT

Any idea?

EDIT: Now I see that I was not the only one facing this problem. I changed every variable from int to long and now everything seems to work. God, I hate when this happens. But better here than IRL.

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

    if operands are int, then result is int. So in pieces:

    long nr = a * b;  
    ...  
    sum = sum.add(BigInteger.valueOf(Math.max(p, q) * x));
    

    overflow exists. Two possible solutions:

    1) Make all operands long-type;
    2) Add 1l literal:

    long nr = a * 1l * b;  
    

    1l — is long-type const so during multiplications overflow wouldn't appear.

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

My god, problem C is a pure hacking bloodbath...

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

I want some advice about hacking. Sometimes the contestant doesn't initialize a variable, so it contains a garbage value, which might give WA. What should I do in such cases, is the garbage value machine dependent or is it some fixed value?

This thing happened in last CF round, one solution didn't initialize a variable, and he was taking max of it with another variable. Fortunately for him, the garbage value was some large negative value, so I couldn't hack him. I would have hacked if the garbage value was some large positive value. What to do in such cases?

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

What's the idea for problem F?

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

    I instantly came up with the idea of using a fully dynamic convex hull and then evaluating at certain coordinates. I coded it and debugged it without thinking, only to fail at Test #9. Then I thought a little bit and I realized that when deleting a line, some lines that were removed earlier because they weren't relevant anymore, might become relevant again, so I'm not sure if fully dynamic convex hull is something we can do.

    I still don't know how to solve it.

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

      I think you can solve it without fully dynamic convex hull. Just process queries by blocks (block can have sqrt(n) size, but this is not the best choice). Build convex hull on previous blocks (without deleted pairs in current block of course). Then lookup answer for query in O(sqrt(n) + log(n)). O(n * sqrt(n)) for all.

      I think it is good solution, but I am too lazy to check it today =D

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

    One solution is that: for each line there is an interval it exists. So, build a segment tree each node contain a convex hull. See link. The other one is sqrt decomposition query. Build a convex hull at each block!

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

      Huh, I haven't written a single task using either of those techniques, guess I have to try :)

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

What does "Unexpected verdict" mean for my hacking attempts #236256, 236261, and 236265?

UPD: fixed.

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

i hacked myself in problem D due to this- ans = ((b%mod * n %mod)+x)%mod test case — 1 1000000000 10000000000000000000 1000000000

due to operator preference b%mod * n will take place first thus overflow!

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

    in the test case you mentioned, the value for n is 10^19 which won't fit even in long long. I think you meant to type 10^18.

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

there will be no tutorial for this round?

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

Where is the editorial for fifth question??

»
8 years ago, # |
  Vote: I like it -32 Vote: I do not like it

When i run c number code on my laptop it answered me 813.But why codeforces answered 625?

include<bits/stdc++.h>

define ll long long

define sf scanf

define pf printf

define end return 0

define d double

define f float

define b break

define c continue

using namespace std; int main() { ios::sync_with_stdio(0),cin.tie(0); ll m,n,o,p,q,a=0; cin>>m>>n>>o>>p>>q; a+=(m/n)*p; a+=(m/o)*q; a-=(m/(n*o))*(min(p,q)); if((n*o)>m) if((m!=1)&&(((m==n)&&(!(m%o)))||((m==o)&&(!(m%n))))) a-=min(p,q); cout<<a<<endl; end; }