Aris's blog

By Aris, history, 2 weeks ago, translation, In English

Hello! Codeforces Round #820 (Div. 3) will start at Sep/12/2022 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them. One of the problems in this round is interactive. Don't forget to read the guide on interactive problems.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University team: MikeMirzayanov, myav, Gol_D, Aris, Gornak40, SixtyWithoutExam and Vladosiya.

We would like to thank: Kniaz, BledDest, Svyat, Be_dos, Timur2006, FelixDzerzhinsky, alphabet321, FedShat, vsinitsynav, Jostic11, HamletPetrosyan, _Roma_, KKT_89, ABalobanov, lightseba, powergee101, DafuQ_o and AshrafEzz for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

UPD 1:


We are in the middle of the round (and missing Gornak40 and Gol_D).

UPD 2: Editorial

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

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

Auto comment: topic has been updated by Aris (previous revision, new revision, compare).

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

Good luck for everyone . Do your best to be the best !!

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

Good Luck everyone! I hope everyone has fun!❤️ Divs 3 are sometimes moody.

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

Its the 1729th codeforces round! The Hardy-Ramanujan number which is very well known in Mathematics

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

For those who are not familiar with interactive problems. This might help you! Link

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

Finally, my first out of comp-

wait this is div.3, not div.4

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

As a tester, give me a contribution, please

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

Good luck to everyone and I hope the problems will be enjoyable!

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

First unrated DIV3 ❤️, hope to solve 6 or more problems this time!

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

Hope to be Expert this round!

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

Codeforces Language Picker -- chrome extension to fix codeforces language picker.

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

Hopefully I'm gonna be green this contest.

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

Div3 Ftw

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

I hope that I will be able to solve A!!

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

Auto comment: topic has been updated by Aris (previous revision, new revision, compare).

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

As a tester, I hope you enjoy the problem set! Good luck and have fun!

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

Hoping to get a positive delta!!

Give me some upvotes. I'm sad! :(

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

now the time of div 3 bruuh

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

    Hello cheater,

    let's see if your solutions again gets skipped or not.

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

Div. 2.5

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it -29 Vote: I do not like it
    The comment removed because of Codeforces rules violation
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +40 Vote: I do not like it

      Please don't talk about contests before they are finished.

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

        oh sorry but i didn't tell anything consider a spoiler + easiness is a mysterious ( sorry my english is not good) term maybe its just easy for me right? + i see people say mathforces speedforcess etc.. in other rounds why this comment consider deferent from them

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

          In my opinion ANY comment referencing the contest during it shouldn't be allowed, I'm not sure to what extent the codeforces staff want/can block this type of unfair comments, but in any case saying a problem is easy is a bit worse than saying all problems are easy (although I agree they should be removed as well)

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

i am not simp but girl in middle look very cute. if anyone know her username

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

    Whenever someone starts a line with, "i am not simp", there is a high chance that they are not simp. Seems legit.

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

    I know...

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

    no but her insta is @zachscud

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

      what a hypocrisy people got her id because of me and still down vote me and one one who release her id got upvote too many simps here

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

      This is codeforce not site where you get customer so don't promote your business here

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

D is much easier than C.

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

    No it is not. Like C took me 7 minutes at most, D took 15-20.

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

      C took 20 minutes to understand the statement, and another 7 to implement it.

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

        it took me 20 min to solve D and 20 min to solve C but another 30 min to find the mistake in my C

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

      A took 10 min and B took 40 min

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

    How did you come up with intuition that only 2 person will go together to have maximal groups and not even a group of 3 will give us the maximal answer?Is it some common idea or what?

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

      If 3 people can form a group, then there must be 2 people in that group that can form a group. As we only want to maximize the number of groups, if 2 people can already form a group, why add more members to the group? I think basic observation is enough the come up with this idea.

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

any idea for problem no E?? binary search is one solution but it requires 60 quarries.

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

    you can just ask 25 pairs (a, b) and (b, a), and you are able to print the answer once you've got different paths for an arbitrary pair. The probability of getting same path for each pair is 2^(-25).

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

    u can just try every pair {1, i} and {i, 1} for i from 2 to 27. In each two query ({1, i} and {i, 1}) u have a 50% chance that u get distance in different directions. If u do, then the answer is ans1 + ans2, where ans1 and ans2 is results for queries. Also, if u get -1 at some point, it means, that the previous i was the greatest vertex in graph, so it should be the answer. So print i — 1 and return

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

      Instead we can just take the pair (1,2) and query it 50 times. There is a probability of (1-2^-50) that we will get two different numbers. Just summing them ( with a +1 ofcourse) will give the result.

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

        No, I too missed that part in the statement at first: after an answer is determined for a specific query, it wont change, so it will keep outputting the already computed value

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

      Well, there is a possibility that all pairs are equal, right?! So why is the solution correct!! Could he give a wrong answer in my opinion.

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

        yes, but that possibility is really really low, so it will almost certainly pass (and if it miraculously doesn't, submit a second time)

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

        Yes, its possible, but the probability of it happening is equal to 1/2^25, which is veeeery small, so u can hope that it wont happen)

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

          Please, can you explain where did the number come from(1/2^25)?

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

            there are 25 pairs, the probability of each of them to equalize is 1/2 and also the probabilities are unrelated, so the probability for all of them to fail at the same time is (1/2)^25

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

              Moreover, if you want your solution to fail then the average number of times you need to submit to get first WA is 2^25 ~ 10^7.5

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

                Actually a bit less, remember there are multiple test cases. But in general yes, that's what I said, the solution won't fail

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

      Gosh, I thought about that, but I was like "hey, this won't pass for whatever test case, there must be another way"...

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

Was E ternary search?

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

About problem E: what is the probability that out of 25 pairs of queries at least one pair of query will give distinct answers, e.g. query(a, b) != query(b, a)?

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

    Roughly 1-2^-25 when n is big enough.

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

      It is said that it may be equal but how you are so sure that it will be equal with 25 queries

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

        The interactor chooses one of the two paths with equal probability.

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

      But the probability of WA is not completely 0. Is there any deterministic solution?

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

        Most likely not. It's the same as the Polynomial Hashes, there is a very small chance of failure, so nothing wrong probably

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

          I thought that codeforces round always has some deterministic solution.

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

            Well, again, Polynomial Hashes are not deterministic, yet still it's a popular way to solve problems on strings. There is nothing wrong about it. You just need to make sure the chance of failing is very small

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

              I get it but usually there is always a deterministic solution. Polynomial hashes has deterministic alternatives.

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

                Not always

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

                "usually there is always a deterministic solution" well, there IS, it just needs more (than 50) queries. People often confuse a problem with a problem statement. You should not consider a problem statement in isolation, rather all of statement, input format, input constraints as a package. For example, for any NP Hard problem, we all know that there are no polynomial solutions. That does not mean they are not solvable. You can set small constraints and expect an exponential solution with some optimization here and there. In other words, this is the difference between math olympiad and programming contest.

                I hope that satisfies your itchy feelings about not having a 100% guaranteed solution. This problem was designed and the constraint was set specifically for a probabilistic solution. If more than 60 queries allowed, one can find an exact solution using binary search.

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

      I see, thank you.

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

    same bro how you can even guess that number .

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

I think that problem E is more suitable for div 2,it's really hard !!

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

    No, the idea, especially with No hacks, 50 test cases, really says it uses random. Also, as there is no binary search, you can only rely on distances, but they could all be simply distances on a part of a graph, so you cannot guarantee the answer is correct. The only way is to minimise the chance of fail

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

    We rarely have "easy" problems with randomized solutions. This is a good way to introduce randomized solutions to beginners

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

      Yup. First time I have ever solved a question with randomized solutions

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

Most unbalanced round ever, downvote.

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

    I guess you've never heard of mr Green Grape

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

Can anyone help me with my solution for Problem E? why is it not working and taking more iterations than 50? although my solution should run within log(1e18) < 50 (correct me if i m wrong here).

submission

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

    log(1e18) > 50

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

      Oops! I calculated log with base e (that is ~ 42). that is why i got confused.

      thanks mate

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

        I calculated the log with base 2 LOL and used binary search

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

cool E

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

In question E how you can be so sure that ans will be find by just finding it upto 25

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

According to some cursory analysis, my solution for E seems to have a 99.391488785% chance of passing a set of 100 test cases. Don't think this is the intended solution.

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

    i guess it is (i did the same btw), because hacks are disabled and there are 50 tests only. Moreover, the problemsetters did even tell us that amount of tests is 50, which is kinda strange.

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

      The problem emphasized "with equal probability" in bold letters, and also made sure to state that "? a b" will not necessarily yield the same result as "? b a". They also mentioned the number of tests in the jury (which I've never seen mentioned before in the problem).

      So yes, I am pretty sure the intended solution is to try "? a b" and "? b a" until you get something different. You do need to make sure you try distinct pairs each time, but there are easy ways of doing that (including ways that guarantee the correct answer if the result is ever -1). My submission: 171950029

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

Great round <3 <3 <3

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

How to solve C?

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

    Find all the characters in string that lie between letters s[0] and s[n — 1] and use all of them for jumps.

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

      sorry can you elaborate further how this achieve the minimum cost ps : sorry i meant the maximum jump in this case for example: abchhhhhhhhhhhhhhd shouldn't your solution fail?

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

        abchhhhhhhhd it will be as a b c d (b-a)+(c-b)+(d-c)=4 and also as d-a=4

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

          oh you are right i was thinking in a scenario where taking a character which is not between s[0] and s[n — 1] can lead to minimum cost too but this example doesn't satisfy it thanks alot

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

How solve E

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

    I try every pair {1, i} and {i, 1} for i from 2 to 27 ^^

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

      why till 27?? can you please explain?

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

        Because there is a total of 50 queries, and for each vertex you need to use 2 queries

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

          Thank you.

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

          Hi Noobish_Monk. I have a doubt. If I print all my queries as 1 and 2 for 50 times, then if I get 2 different sets in my answer then it's just the sum . What's wrong with this approach. And the probability that I always get the same answer is 1/power(2,50) which should be approximately 0. Why do we need to print for 27 queries ??

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

            The answer for the same query is the same However queries ? a b and ? b a are different So you can't just ask 1 2 and 2 1

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

              I should have read that statement :( . Thanks mate :)

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

        You can also do it from 4 to 29, because the problem states that n ≥ 3.

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

        Cause we have 50 queries bro

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

Solution for E was probably meant to be different, But here is how I AC it:

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

    same thing for me too!

    I never thought it would work but some how it worked

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

    I share the same idea with you ^^

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

    IT'S IS THE INTENDED SOLUTION

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

      Can you explain how it is the intended solution like very first thing that comes to mind is Binary search but it didn't work.

      I also tried the concept of binary search on infinite array but it failed at test 18.
      
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Because of how many times the statement highlighted the idea of equal probability i think this is the intended solution.

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

        There is no deterministic solution that guarantees 100% correctness. Suppose I was an adversary that doesn't have a specific graph in mind, or even a value of $$$n$$$, but I make answers to screw you over while always ensuring that there exists some graph that is consistent with all my answers. Then I can always ensure that each answer I give will be either -1 or some distance that is below the established lower bound from the program.

        With 50 queries, you can only gain enough information to distinguish between $$$2^{50}$$$ possible answers, However, the range for $$$n$$$ goes up to $$$10^{18}$$$ (which is much larger than $$$2^{50}$$$), so you cannot guarantee a correct solution.

        The problem dropped a lot of hints suggesting the randomized approach ("equal probability" in bold, clarifying that "? a b" and "? b a" are processed independently, specifying the number of jury tests, etc), so I'm quite sure this is the intended solution.

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

          If you want your solution to fail then the average number of times you need to submit to get first WA is 2^25 ~ 10^7.5

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

            Why can't we just use pair 1,2 and 2,1 25 times ? What is the probability that use these 2 pairs wont give me the answer in 25 queries ?

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

              It is stated that the same pair will give the same result for all requests.

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

              The problem states that repeating the same query will yield the exact same result every time. There is only a 1/2 chance that "? 1 2" and "? 2 1" will yield different results. If they both produce the same distance, then you will always get the same result for "? 1 2" or "? 2 1", so your probability of success will remain as 1/2. This is only for one jury test, so the probability of getting all 50 jury tests would be $$$\left(\frac{1}{2}\right)^{50} \approx 0.00000000000008817842\%$$$, which is not worth trying.

              But by trying different pairs each time, there is a 1/2 probability of success for each distinct pair. The probability that all 25 pairs fail is $$$\left(\frac{1}{2}\right)^{25}$$$, so the probability of being successful at least once is $$$1 - \left(\frac{1}{2}\right)^{25}$$$. A single success is enough to guarantee the correct answer. We need to pass 50 jury tests, so the probability of ACCEPTED verdict becomes $$$\left(1 - \left(\frac{1}{2}\right)^{25}\right)^{50} \approx 99.999850988\%$$$. It would be extremely unlikely for such a submission to fail, and I would be very interested to see if there is anybody who met this unfortunate fate.

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

                Thanks for your explanation. This is helpful.

                I read this statement of same result produced for same query but didn't realise how important this was.

                Even after reading this, somehow I thought that using 1,2 & 2,1 still is random. But it seems like that the interactor is caching the result of the query.

                Similar to these lines, IMAGINE if 1,2 & 2,1 produced different results with 1/2 prob but they can produce different result every time, then we can just query 1,2 & 2,1 50 times right ?

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

                  If duplicate queries were rolled independently, then yes, you can just query "? 1 2" 50 times. You can mix in "? 2 1" as well, but it is completely identical to "? 1 2" in this case, so it doesn't matter. In this scenario, the probability of failure becomes $$$\left(\frac{1}{2}\right)^{49}$$$ (all 49 queries after the first one match with the first query).

                  Probability of AC becomes much higher then (though it was already high to begin with), and the implementation becomes much easier too (though it was already easy to begin with).

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

              Even without luck being involved, it can very well be the case that 1 and 2 are on opposite side of the cycle so longer and shorter both lengths are INDEED equal. So you must take different pairs to keep a backdoor in case your queried vertices fall on opposite sides.

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

                Ah, you're right; I forgot about that case. We can deal with this by simply performing 25 queries of "? 1 2" and 25 queries of "? 1 3". This slightly hurts the probability of success, but it's still very high.

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

                  25 queries of "? 1 2" gives the same answer each time. So you are really just wasting 24 queries in this case. Same goes for "? 1 3".

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

                  OneBit1024 This was part of a discussion on the hypothetical scenario that each query is rolled independently, even if the same query was made in the past. In such a scenario, it would be optimal to repeat the same query (e.g., "? 1 2") 50 times instead of trying to find new pairs. If all 50 queries yield the same result, then the guess should be on twice this value (since it's likely that both paths have the same length).

                  Obviously, for the original problem E, repeating the same query would be a waste, so you have to keep trying distinct pairs (so the possibility that both paths have the same length would not be an issue at all).

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

                  Oh ok, sorry, I didn't realize that you were discussing a hypothetical scenario. Well in this scenario, this approach will work.

                  actually, during contest I tried the same thing because I missed the part where (a,b) would give the same result each time.

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

          "Suppose I was an adversary" I don't need to read anything else. The solution will fail against an adversary. That's the whole point, that it was not an adversary, and it will honestly return any of the shorter or longer path from a to be with equal probability, without ever trying to make you fail. The moment an adversary comes into play, it will need binary search i.e. 60 queries.

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

            The fact that an adversary will always be able to screw you over is definite proof that there does not exist a deterministic solution that guarantees correctness, which further suggests that the randomized approach is, indeed, the intended solution. Some people were unsure if that was the case, but I don't actually think there should be any doubt.

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

Can anybody explain how they came up with the number 25 that checking this many pairs will have a different result?? really didn't get this part.

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

    It's probability theory. We have a chance of success 1/2, same for failure. As we ask 25 times, we have a chance of failure equal to 2^(-25), which is a VERY small number

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

    Since we have at most 50 queries, we can check 25 pairs in both ways. Assume we got a pair (a, b). Checking it both ways means that you chack a pair (a, b) and (b, a) since it can give different results. Since the output path length is randomized between the 2 paths(the short and the long versions, since it's a cycle), it's 50% chance for each to output.

    Asking 25 queries in this format and checking for -1 or different results for the (a, b) & (b, a) query. If you get -1, it means the last vertice(call it v; 2<=v<=26) is the correct answer, since the current one is out of bounds and the last one wasn't. So we output the last valid run. If the results differ, you can output sum of the results, since you got both paths for (1, v) pair and their sum is a complete cycle.

    This one failing has quite a low chance, since it's 1/2 for each path to be given for a query, it's 2^-25% chance of this idea failing, if I am not mistaken.

    I hope this makes sense.

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

    You're allowed 50 queries. You make a pair of queries "? a b" and "? b a", and hope that you get different results for these two. If the results are different, then you can add the two results to get the number of vertices.

    I'm not sure if the guess counts as a query, but if it doesn't, then you have 25 pairs of queries to get this. If it does count, then you only get 24 pairs of queries, plus an extra query, and one for the answer.

    It's annoying that this is a randomized solution, but the probability of this failing is less than 1%, and there are many hints in the problem statement itself to suggest that this is the intended approach (equal probability in bold letters, mentioning that "? a b" and "? b a" are rolled independently, specifying the number of jury tests, etc).

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

    Also if you ask why the numbers of allowed querry is not greater it's because with 60 querry (which is log2(1e18)) you can just get the result with a binary search

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

Very interesting problems, especially F!I have really enjoyed it!

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

I think my A problem is brief enough.Is there any person can give me some advice to simplify my approach further?

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

Can anyone tell me what i am doing wrong in my solution of problem C ?

My submission

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

    As the solution uses sorting I might suggest it's that the last index is not the last in your sequence. Or you could possibly go in the wrong order if p >= q or less than q. IDK, but that's most likely the mistake

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

    Try "baba".

    I fell into the same trap and got WA. Thankfully, I figured it out before the contest was over.

    I didn't read your code (but I checked "baba" via custom invocation), but it's most likely due to your use of sorting. The assumption that your range covers all instances of first character and all instances of last character only applies if first character < last character. In the scenario where last character < first character, your range likely does not capture all instances of first and/or last character.

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

    Here is the counter case for your solution: 1 yydia

    correct ans: 24 5 1 2 4 3 5

    Your ans: 24 4 1 4 3 5

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

    In the p > q part, you should include p and q in your answer.

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

https://codeforces.cc/contest/1729/submission/171949266 Can anybody help to find a short test where my solution for C does not work?

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

    one counter test case: 1 puvh correct ans: 8 2 1 4 your output: 8 3 1 2 4

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

Worst Div 3

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

Whats wrong with my solution to C? 171872810

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

To the author of problem E: how did you generate the tests? I'm curious to know. Btw, awesome contest!

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

    Yeh same doubt regarding the E part of the contest, in all the test cases, input is in this form-

    3 9195979e279504391c49d2f080c1d8c755d044ca what is this — 9195979e279504391c49d2f080c1d8c755d044ca ?

    Shouldn't this be a long integer? Thanks.

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

    I think you store the length of the permutation as well as it's index in sorted order. Not sure though...

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

i was trying to solve F with condition s(l1,l1+(w-1) ) != s(l2,l2+(w-1)) when i read l1 != l2 then when i realaize my mistake the contest was over :(

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

Can someone find a mistake in my code for 1729C - Jumping on Tiles?

Code: 171911705

Thanks!

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

    Check 1 zzzzza

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

    Try "baba".

    I fell into the same trap and got WA. Thankfully, I figured it out before the contest was over.

    I didn't read your code (but I checked "baba" via custom invocation), but it's most likely due to your use of sorting. The assumption that your range covers all instances of first character and all instances of last character only applies if first character < last character. In the scenario where last character < first character, your range likely does not capture all instances of first and/or last character.

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

Oh my god I solved E. I have never tried random algorithms in competitive programming ever. Too bad the contest is over by now, but holy fuck I would never believe that it would actually work. Holy Jesus. 171950813

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

Nice problem D! It makes me difficult even though it's only div 3. Can anyone give me a solution ?

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

    For C or D?

    For C, jumping directly to the end yields the minimum cost, which is |last character — first character|. How to maximize jumps? Observe that if you're in $$$\alpha$$$ and you jump to $$$\beta$$$ and then to $$$\gamma$$$ such that $$$\alpha <= \beta <= \gamma$$$, then the cost is the same as jumping directly from $$$\alpha$$$ to $$$\gamma$$$. So you can jump to any character in the range [current character, final character] and it would not affect the final cost.

    For example, with "logic", you can go from "l" to "i" to "g" to "c" because "l" > "i" > "g" > "c". To maximize jumps, you need to visit every character in the range [starting character, final character] in order (either non-increasing or non-decreasing order, depending on the relative order between first and last character).

    For D, if you calculate $$$y - x$$$, you basically get the person's balance from paying for their meal. This can be negative if they don't have enough money. You can then sort the balances, and try to pair the one with the lowest (i.e., most negative) balance with the highest balance. If the result is non-negative, it's a valid pair, and you can move on. If not, then the lowest balance is hopeless and you move to the next lowest balance (try with highest balance), and so on.

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

Would you please review 171943515? Maybe it is wrong when $$$n$$$ is small, but I do not know how to fix it.

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

    int isn't big enough to hold the values required.

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

      Damn it you hacked me twice ^_^. Thank you very much!!!!!!!!!! When debugging in a limited time, it is easy to ignore some very basic facts...

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

In problem E, all the AC solutions I've checked till now are querying

$$$?$$$ $$$1$$$ $$$x$$$ and $$$?$$$ $$$y$$$ $$$1$$$ where ($$$2 \le y \le 26$$$).

But how is that acceptable when the interactor chooses with a certain probability? Yeah, the probability of getting a correct answer is very close to $$$1$$$ ($$$1 - 2^{-25}$$$) but certainly not $$$1$$$. I thought of such a solution but ignored thinking since it can create a situation where same solutions may get AC and WA which is unexpected. I don't think this was a good/standard problem for a contest.

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

    I did feel bothered by the fact that the intended solution is randomized, especially since I was trying much more complicated approaches before the contest ended, and only got AC after it was over.

    However, I think it's really a matter of opinion on whether this is appropriate. Randomized algorithms have numerous practical applications in the real world, so this kind of recognition that a randomized algorithm would work is a good skill to have, which can be argued as being among the type of skills that competitive programming should cover. Also, the problem did drop a lot of hints that this was the intended solution ("equal probability" in bold, mentioning that "? a b" and "? b a" are processed independently, mentioning the number of jury tests, etc), so I think it's justified in this case.

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

    I personally think it was a great problem (maybe I have some bias since I solved it quite quickly in the contest). It makes you think outside of the box and consider non standard methods that you don't regularly see in CP, which ultimately is a great way to test/improve problem solving.

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

Can someone explain how does the rating work, I'm confused a little bit because I'm new to codeforces.

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

    It depends on your rank in the contest and your current rating.

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

In problem E ,is it really fair to give such a probability based question in a contest because it's not like the probability of getting them all equal is zero right,just because of that many of us didn't go for that approach and the binary search one was exceeding the queries(which should actually be the intended solution).

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

    The probability of success is over 99%, and the problem dropped a lot of hints to go for a randomized approach ("equal probability" in bold letters, clarifying that "? a b" and "? b a" are processed independently, mentioning the number of jury tests), so I think this was justified. I understand how one would assume there is a deterministic solution, but randomized algorithms have numerous practical applications in the real world, and recognizing when a randomized algorithm would be effective is a valuable skill for a programmer to have, so it can be argued that it should fall within the scope of competitive programming. I understand the concerns, but I think it's a matter of subjective opinion and cannot definitely be ruled as "unfair".

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

Is there a deterministic solution to the problem E, which always works no matter how the generator is configured?

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

    No. An adversary can always ensure that the result for each query is either -1 or some distance that is less than the current lower bound that was established. Therefore, there are essentially two possible types of information to be gleaned from a single query. With 50 queries, this only allows identifying up to $$$2^{50}$$$ different values, which is less than $$$10^{18}$$$. So there is no 100% correct deterministic solution.

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

Are hacks rated?

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

Is square root decomposition the intended solution for problem F?

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

    there is no need in sqrt decomposition, the only data structure we actually need is prefix sum array

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

In problem E, shouldn't it be "in C++ you should use function fflush(stdout)"?

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

Any hints for G?

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it
    Hint1
    Hint2
    Hint3
    Hint4
    Code
»
2 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

An interactive problem without Binary Search ,,,,,, surprising

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

how to solve problem c? I used priority queue but got wa

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

    The maximum number of jumps must be on the characters which in the range between the first and the last character

    ex) s = "codewars"

    character 'w' doesn't belong to ['c' -> 's']

    so you shouldn't jump on it

    Take the rest of the characters, sort them, then print their indexes.

    My submission

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

    The minimum distance is simply the distance from jumping directly from the first to the last.

    How to maximize jumps? If you go from $$$\alpha$$$ to $$$\beta$$$ to $$$\gamma$$$, where $$$\alpha \leq \beta \leq \gamma$$$, the total cost is the same as going straight from $$$\alpha$$$ to $$$\gamma$$$. So you can keep jumping to an intermediate index, provided that the character in it lies between the previous character you were in and the next character that you're going into. So if you need to jump from "b" to "f", then you can jump into all of the characters in the range [b, f], in non-decreasing order. By the same argument, if your final character is actually smaller than the first character, you can still jump into all characters in the range, but in non-increasing order this time.

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

Anyway,I dont think E is a good problem.

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

    Definitely because if you go to exact statement then it will always be a point of discussion whether (2^-25) = 0 or not .

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

    Randomized algorithms are not that bad!

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

      Randomized algorithms are the best thing in the whole universe.

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

        Especially when they're not the intended solution

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

          Based.

          Btw, are u talking about today's E? Wasn't the randomized solution intended?

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

    I agree. Giving such an easy problem at E is confusing. I got the idea in maybe 10-20 seconds but kept wondering whether there are any tricky scenarios or edge cases. It should've been in D.

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

Isn't intentional code obfuscation forbidden?

Please check this: https://codeforces.cc/contest/1729/submission/171937226

MikeMirzayanov

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

So I was just casually looking at the hacks corner and found a few hacks for problem A which seem way too odd.

171954115, by: vaibhav_1710 to: chaudharyvaibhav184; 171952586, by: andreifilimon to: wavetome;171877008, by: just_to_code to: suiiiii

Now how and why in the world did all these people put an a is equal to some random no. check? I don't know where to report these so I'm just posting it here. There are points for hacks so this should count as a violation right?

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

    those are probably made specialy so people who check a lot of submissions can find those stupid mistakes and take the points. I agree to you thats like a violation but as those are there why not to make a easy hack. (there are a lot of this mistakes in submissions) by the way a good way to hack smth i tried a lot on problem C was big tests...

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

    There are some telegram channels which sell these solutions during the contest for as cheap as 20-30 cents per question.

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

    Can those be Trojan Horses for cheaters? In edu rounds (Edu, Div 3, Div 4) there are no points given for hacks. Therefore, there's no incentive to plant deliberate mistakes for future hacks.

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

      Thanks for being the only person to clear my doubts. I didn't know hacks didn't account for any points for div. 3 onwards. Now I feel stupid for posting this.

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

I like problems with randomized solutions. It would be great if there were more such problems as today's E.

Do you like randomized algorithms?

— Yes

— No

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

    I don't know what to say about $$$E$$$, I had that idea early, but I doubted it would work, then i submitted it in the last minutes (because why not) and somehow it worked, but I got high penality.

    I'm certain that many people (maybe hundreds) had this solution in their head but they didn't try because it depends on luck :D

    So i don't like this random algorithm.

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

    me not touching the yes/no button as it will disturb the perfect pattern

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

I had a doubt regarding the E part of the contest, in all the test cases, input is in this form-

3
9195979e279504391c49d2f080c1d8c755d044ca

what is this — 9195979e279504391c49d2f080c1d8c755d044ca ?

Shouldn't this be a long integer? Thanks.

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

Any hints for F? I'm guessing there's some number theory property related to mod9 as $$$w$$$ can overflow int64.

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

    Hint: any number in decimal mod 9 = the sum of its digits mod 9. It would be a good exercise to prove this statement.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Hint about proving this statement & other similar statements
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try this input:

    2
    azz
    bz
    

    The map yields values from 1 to 26. When adding elements to the 2D vector, the first index is given by the map, so the first vector index also ranges from 1 to 26 (1 for 'a', 26 for 'z'). However, when clearing the vector at the end of the test case, only indices 0 to 25 are cleared. So any instances of 'z' saved from earlier test cases (at v[26]) will continue to remain in future test cases.

    (note that v[26] is technically out of bounds, since v was declared to have size 26; this will not necessarily be detected as an error, and the program may continue to use v[26] as the unallocated memory location that sits 26 steps from the start of the vector, until an issue arises with this location later)

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

In problem E, hacks are disabled. Is system testing also disabled or can it be a FST?

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

    The problem statement says that there will be 50 test cases and there were 50 pretests. So I'm presuming that there will not be any system testing for E

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

Curious to know if rating changes have been applied or not for this round. It is showing me as a unrated contest atleast for me when I tab the "all contests" dropbox in rating graph. Or this is a normal case when rating is not updated till now.

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

    It shows it as an unrated contest if rating changes haven't been applied. As of now, the hacking stage has just gotten over and the system testing still has to commence.

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

How to do Question E

If n<10^15 or number of queries < 60 my solution of ternary/binary search would have worked. My naïve idea= ask query as "? 1 m" . if this returns -1 decrease value of m or else increase

but this uses 60 queries. How to approach this types of question

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

    The issue with binary search is that you can only eliminate at most 1/2 of the search space consistently; in fact with question E I think there is no way to get a solution that you can be absolutely 100% sure is correct.

    There is a solution though that has about a 99.99% chance of being correct. It's only possible because of the problem emphasizing that one of two paths will be chosen with equal probability.

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

MikeMirzayanov is the only one without laptop in the picture.

Also I don't know the others. Does anyone else know all of them??

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

    It's the ITMO university team. Just read earlier in the post. There are seven in the team, but two are not in the picture (specified in the caption). I'm pretty sure the seven of them all know each other, and there are probably other people (possibly from ITMO University as well) that would also know them, but I'm not sure why you're so interested in them.

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

      I was just curious, since they were all with Mike and probably at the headquarters from where this brilliant site is maintained.

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

How do you realize when system testing is over in edu rounds and div3 rounds? At the end of hacking stage, it says "Final standings, open hacking phase finished". But don't system tests take place after this, in that case how is it final?

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

    System testing in these rounds usually happen 4-5 hours after hacking phase

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

      I am aware that system testing takes place a few hours after hacking. I am just curious as to how you realise whether sytem testing has finished or not. Like for round 820, what indication do I get to understand that system testing is done or not?

      All it says is "final standings" which isn't true I think because system testing hasn't started.

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

when will the ratings be assigned?

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

Why are ratings still not published, is this round rated or unrated

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

    This round had 12 hours of hacking phase, which will be used to re-judge all of the solutions as far as I know. The hacking round finished a few hours ago, now hacks are being analyzed most likely and after re-testing, ratings shall be published, so a few more hours probably.

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

I am having trouble with this, please share your insights.

  • What is your comment on the difficulty or standard of problem E?
  • Is it a good problem or an average one?
  • Can hard problems have such simple solutions? If so, can you give some examples?
»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Cool update. Would love to have these in future rounds as well :)

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

I think if this problem was placed in the A place,there will be more people solved it.Many people had the corret idea,but they think this solution is not fit to E problem.This kind of problems may be good,but where they should be placed is still a problem.

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

    Well, A through D are easier than E, so everything's fine, imo. And if it had been set as A, more participants would have been determined to dodge this round.

    I think we are forgetting, that this is a Div3 round. This E is even harder, than usual E Div3 problems, imo again.

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

When will the rating change? my rating has not changed yet

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

Where's the editorial

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

Problem F video editorial.

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

when can I see the results? 12 hours-fade is already up...

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

they look awesome!

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

Finally ratings are updated :D

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

Who knows why my raiting is unrated ? why?

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

why is taking so long to update ratings? :/

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

    System testing ended few minutes ago, so you may expect rating change soon!

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

      Ok cool

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

      my rating is yet not changed.neither the contest appears in the list of contests i have taken part in

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

G can be solved in $$$\mathcal{O}(m + n\cdot \log(n))$$$ time and $$$\mathcal{O}(n + m)$$$ memory, by using dp + segment tree.

First compute starting positions of occurences of $$$t$$$ in $$$s$$$. This can be done in linear time in many ways (I used z function). It's easy to notice that we can apply operations in order from right to left. Then, we will compute $$$dp_i$$$ = answer if the rightmost operation was applied to range $$$[i,i+m)$$$.

To compute $$$dp_i$$$, we could iterate to the left of $$$i$$$ on the starting index of the next operation (let's call it $$$j$$$). Two things need to happen:

  • If there is an occurence of $$$t$$$ in $$$s$$$ that is completely between $$$[j+m, i-m]$$$, it won't be covered by any operation, so $$$j$$$ is not valid. This defines a lowerbound on the value of $$$j$$$ (we can easily mantain it when increasing $$$i$$$ by using two pointers).
  • if $$$j+m-1 \geq i$$$, then $$$j$$$ is not a valid candidate, because given that we apply operations from right to left, the operation on index $$$i$$$ removed some of the characters of the occurence starting on index $$$j$$$. This defines an upperbound on the value of $$$j$$$.

This two conditions define a valid range of values for $$$j$$$. We just need to be able to combine the $$$dp$$$ values of this range. We can use segment tree to get this merged value.

Overall, we compute occurences of $$$t$$$ in $$$s$$$ in $$$\mathcal{O}(m + n)$$$ and then compute $$$dp$$$ values in $$$\mathcal{O}(n\cdot \log(n))$$$, so final complexity is $$$\mathcal{O}(m + n\cdot \log(n))$$$ with $$$\mathcal{O}(n + m)$$$ memory.

Here is a link to my submission :)

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

    so cool

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

    That's what I thought! This task seems similar to a (slightly harder) problem from POI 2018, stage 2 problem "Konduktor". Link: https://szkopul.edu.pl/p/default/problemset_eng/oi/25 You change the language to English in the top right corner. Also, forgot to say, nice explaination of your solution

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

    Since the query range is fixed, you could overkill this further by replacing the Segment Tree with a Minimum Queue for a $$$O(n+m)$$$ solution. submission

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

I solved 2 problems in this round but still, the rating is not updated. what is the estimated time it takes to update the ranking?

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

System Testing has ended way back.... then why so long in rating update?

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

Aris Is it unrated round?

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

Editorial section still not uploaded

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

I like E. Open my mind.

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

    I didn't. Even though the probablity is 50-50 still there's a chance that the ans for "? a b" is same as that of "? b a" for the first 50 queries. Change my mind :(

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

      Probability of all 50 queries failing and none giving an useful information is 2^-25, that's basically somewhat like 99.9998% chance of a solution passing.

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

        I don't get this. It fails for an edge case right. What if I'm the testcase author and I wantedly set such a case?

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

          Testcases are random as well, it's not a preset. The answers are generated randomly while testing.

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

          it's not about case work. In statement it is said, that The interactor chooses one of the two paths with equal probability

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

      Probability 0.00000003 is small enough to never happen, that's it

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

        See I get this but they've mentioned that the answers for the queries are pre-determined right so there is a chance that the solution fails for a case.

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

          No, answer is not pre-determined. It becomes determined only after you ask about this pair

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

          Or, if will be better to understand, they are pre-determined, but not with bare hands, but using a randomised algorithm, that randomly picks pre-determined answer for each pair. It is still the same task

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

I submitted this solution https://codeforces.cc/contest/1729/submission/171912216 to the problem D yesterday during the contest, and after the system testing, it gave me a runtime error on test 7. In contrast, after system testing, I submitted the exact same code I submitted yesterday, to the problem and it got accepted. This is the link to that accepted solution https://codeforces.cc/contest/1729/submission/172063331. You can check both the solutions are precisely the same line by line. So why does my code fail in system testing? MikeMirzayanov Vladosiya SixtyWithoutExam Gornak40 Aris Gol_D myav

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

    I do not run your code, but I think while(a[max1] >= 0 ) max1--; is dangerous. What if max1==-1? This causes undefined behaviour. I review your code on a mobile phone. Maybe I am wrong.

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

    Maybe thats the reason of ratings changing delay

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

    I didn't review it in depth, but considering the above comment, I suppose your code once slipped with out of bounds indexing, while another time it didn't. Might be because of the second time out of bound index still made sense(maybe bcs it was allocated at some other place where the resulting index was valid). You can try to send it again, you might get another runtime or might not, lol. Not sure what are the chances of the same happening again.

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