antontrygubO_o's blog

By antontrygubO_o, 5 months ago, In English,

Hello Codeforces!

ozon

We are glad to invite you to the upcoming “Ozon Tech Challenge 2020”, which will start at Mar/03/2020 17:35 (Moscow time). The round will be open and rated for everybody!

This round is initiated and supported by Ozon.

Ozon — one of the leading players in e-commerce (provides its customers with over 2.5 million product names in 24 categories), a tech company that actively developing its IT department. They already have the largest Golang team in Russia, a proprietary WMS fulfillment management system completely written by the Ozon team, 250 million lines of logs per day, collected on the site and in the Ozon mobile application. Ozon experts perform at the leading profile conferences GoperCon, Heisenbug, GoWayFest, GolangConf, and also at the company site meetups are held for the IT community.

The company shows great interest in the support of the developer community — for schoolchildren there is Ozon Academy, for the older audience there is an internship program Ozon Tech Camp and training program Ozon Masters.

Participants will be asked to solve 8 problems in 2 hours 15 minutes. Scoring will be announced a bit later.

The problems were created by Akikaze, Ari, Kuroni, zscoder, xuanquang1999, and antontrygubO_o

We would like to thank:

Thanks to Ozon for the gifts to the participants:

  • top 10 participants will receive stylish branded backpacks and branded T-shirts;
  • 11-20th participants will receive compact portable chargers for 10000 mAh and branded T-shirts;
  • 21-60th participants will get branded t-shirts;
  • another 30 T-shirts will be played among the rest of the participants, who solved at least two problems, randomly.

We hope everyone will find an interesting problem for themselves. Wish everyone a successful round and high ratings! Good luck!

UPD1:

Score distribution:

500 — 1000 — 1250 — 1750 — 2000 — 2500 — 3250 — 4000

UPD2: Editorial

UPD3: Congratulation to the winners!

  1. tourist
  2. maroonrk
  3. peehs_moorhsum
  4. ksun48
  5. Endagorion
  6. Benq
  7. gisp_zjz
  8. neal
  9. Um_nik
  10. yasugongshang

Information about prizes will appear soon.

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

»
5 months ago, # |
  Vote: I like it +247 Vote: I do not like it

Is anybody going to talk about the "no subtasks" tag? :))

»
5 months ago, # |
  Vote: I like it +109 Vote: I do not like it

AC round #2

»
5 months ago, # |
  Vote: I like it -54 Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Finally prizes

»
5 months ago, # |
  Vote: I like it -31 Vote: I do not like it

Small prizes though

»
5 months ago, # |
  Vote: I like it +34 Vote: I do not like it

No subtasks

No subtasks

»
5 months ago, # |
  Vote: I like it +243 Vote: I do not like it

![ ]()

»
5 months ago, # |
  Vote: I like it +82 Vote: I do not like it

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    Hah,that's a serious problem. However,no matter whether you will get the T-shirts finally,wish you enjoy the competition!

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

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it +43 Vote: I do not like it

      On my way home I saw this meme and planned to change the text on the pink monster to "using question instead of problem", but thanks, that even better! :D

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it -21 Vote: I do not like it

      Nothing Here

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i just realized your name means toucan, the bird in rainforests. or maybe i just had too much moonshine

»
5 months ago, # |
  Vote: I like it -30 Vote: I do not like it

In my opinion, a person who has a better rating should have a better chance of winning a prize! (For 30 T-shirts) This is fairer!

»
5 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Will all sponsored rounds be combined? :(

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

    How to make round with prizes not combined?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -106 Vote: I do not like it

      Prizes only for div1, or for top30 of div1 and top2 of div2.

      And I didn't know what there will be prizes in all sponsored rounds.

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

        Only for Div1 sounds unfair and the round becomes just the usual round for majority of participants.

        If you make prizes for Div2, Div1 people are likely to create fake accounts.

        Sponsored rounds usually have prizes or are elections to some onsite competition, in which case it's also reasonable to make round combined.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it -70 Vote: I do not like it

          Only for Div1 sounds unfair

          Why? Making qualification rounds before most important (third) online round of Google Code Jam is also unfair?

          the round becomes just the usual round for majority of participants

          that's a plus :)

          If you make prizes for Div2, Div1 people are likely to create fake accounts.

          top2 div2 isn't much easier than top30 div1

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

            I don't know of this happens in reality, but when round is combined it makes sense for organising company to promote the competition on their own channels. If div2 is without prices it makes much less sense for them because newly registered users can't actually win

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

              Ok, this is a very good point.

»
5 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Official drink of the contest

»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Solve two problems! That's so great for me, maybe I will get my first T-shirt in these rounds.

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

    With <1% probability? You are the big optimist.

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

      Worst case: about 30/10000=0.3%.

      Best case: about 30/2000=1.5%

      But 0.3%>0% !

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

        You should keep trying with 2+ solves as in future you will be able to solve more

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        nah it is bigger than 0.3%. All of the competitors will not solve 2 problems.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        Previous combined round have ~7000 participants and only ~4500 of them solved at least 2 problems, so your estimation of 10000 is very inaccurate. Anyway 0.3% < 1% so I don't understand the reason of this calculations.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That is the worst case :(

          Of course impossible XD

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wish you good luck!Hah( ´▽` )ノ

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    No,you wont get a tishort becouse u would not solve 2 problems. Uoy won't solve anything.

»
5 months ago, # |
Rev. 2   Vote: I like it -46 Vote: I do not like it

.

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

    Good question. If only the name of the contest gives us that answer.

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

Are there any previous Ozon Tech Challenge contests held on Codeforces?

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

    No, it is the first one.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Believe it or not, I'll get the shirt

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        1%

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

          1% is still too good, lets say there are 6000 participants that solve 2 problems. 30 out of 6000 XD, 0.005 chance.

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            multiply 0.005 with 100 ,to get percentage.... i.e. 0.5 % still close :->

            • »
              »
              »
              »
              »
              »
              »
              5 months ago, # ^ |
                Vote: I like it -11 Vote: I do not like it

              multiply it with 200, to get percentage.....i.e. 100% we all win.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

That feeling when you really need a new backpack knowing that you have no chance to win...

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

what's the score distribution?

»
5 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Can I participate in this contest? I don't know the full process. Anybody help me plzz.

»
5 months ago, # |
  Vote: I like it -32 Vote: I do not like it

A lot of problem setter and tester including 300iq.I think this contest will be interesting.

»
5 months ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

Sorry, but is any of authors or testers working in Ozon?

»
5 months ago, # |
  Vote: I like it +33 Vote: I do not like it

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

    :thinking:

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it -14 Vote: I do not like it

      Lol. I just reposted. Originally it was the reply to the meme which said "I'm out because Akikaze is setter" and that comment got removed. ¯\_(ツ)_/¯.

»
5 months ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

.

»
5 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Ozon Ozone O 3 :)

»
5 months ago, # |
  Vote: I like it +82 Vote: I do not like it

Why some users appear with it's real name, cities and in Black?

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I wish every round is combined

»
5 months ago, # |
  Vote: I like it +55 Vote: I do not like it

TFW you can't submit a solution because "You have submitted exactly the same code before", list of submissions is empty, and mirrors are not working, nice

// And it isn't a joke :(

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

    Same here!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is more! We can not ask the questions in the contest interface because of request status code 500 error!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you use late registration? I did, probably this is the source of bug

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't. It doesn't matter where the source, it just should not happen. And what surprises me most is the fact that this is a new bug. At least I never heard about this issue before

»
5 months ago, # |
  Vote: I like it -23 Vote: I do not like it

I dislike this contest!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Same here! I cannot submit any task, but I want to participate in the lottery!

»
5 months ago, # |
  Vote: I like it +59 Vote: I do not like it

Me after solving A, B and waiting for the contest end to see if I win a T-shirt or no :

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

farewell, rating

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is another contest tomorrow , you should be able to make it back.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    turns out, i disappointed the cf rating formula enough with my initial 4 rounds that I'm still getting rating even with poor performance:(

»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Was randomized solution supposed in F?

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

    Probably. I don't see any other way especially because it can be costly to even factor everything on the input.

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

      I have a deterministic solution for F — answer is always less then N + 1 (since we can always make everything even in at most N moves). Then it means we can only change smallest element d to (d — N, d + N). We can make a sieve upto 10^6 to find all primes in factorization of all numbers in this range, and then proceed with classic algorithm for each of those primes. I couldn't see what's the upper bound on number of primes like that, but I assume it's pretty small :P

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

        What if every element in array is big prime number and also elements in array are pairwise different? Do you proceed n times?

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

          I factorize all elements in range (d — n, d+n) for one element of the array (in my case minimum), so this test should not be a problem

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

        I just tried this solution, but n could be 2*10^5 and there're 17,986 prime numbers between 1~200,000. since we need O(n) time to obtain the sum of move counts for such prime number, it seems like 17,986 * 2*10^5(n) cause TLE. Do you have any idea about this?

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, my best improvement is saving global answer and terminating gcd check as soon as my partial answer is bigger. I think I can unpack my solution, so take it with a grain of salt :P

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            So it's something like $$$O(N^2/\log)$$$ with constant optimisations?

            • »
              »
              »
              »
              »
              »
              »
              5 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Probably yes, but I couldn't create a test where it would behave super badly. The "break when answer is bigger" check is pretty good in stopping almost all cases.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Yeah, that complexity is already pretty good for many $$$O(N\log^2)$$$ problems if the constant factor is good. I'd rather not bet on it in-contest though.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it -31 Vote: I do not like it

      EDIT: This is wrong You can factor every number in O(nlogn) if you use a sieve like this:

          /**
           * Return an array of primes up to and including N. Takes only O(N) time!
           * Also generates an array of the minimum factor for every number
           * from 1 to N, which can be used to find all factors of any number up to N.
           */
          private static List<Integer> primeSieve(int n) {
              List<Integer> primes = new ArrayList<>();
              // minFact[i] contains the minimum prime factor of i.
              int[] minFact = new int[n + 1];
              for (int i = 2; i <= n; i++) {
                  if (minFact[i] == 0) {
                      primes.add(i);
                      minFact[i] = i;
                  }
                  // Find multiples of i where primes[j] is the minimum prime factor. This loop will go exactly once for each
                  // composite number. How it works: given a number i with prime factorization p1*...*pn, where p1<=...<=pn,
                  // we say that, for each prime p <= p1, the number i*p is composite with minimum prime factor p.
                  // Why this gets to every number exactly once: the number p1*...*pn will be generated only by p2*...*pn.
                  // That's because all of it's prime factors need to be higher than it.
                  for (int j = 0; j < primes.size() && primes.get(j) <= minFact[i] && i * primes.get(j) <= n; ++j) {
                      minFact[i * primes.get(j)] = primes.get(j);
                  }
              }
              return primes;
          }
      
      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        But $$$a_i$$$ is up to $$$10^{12}$$$, so it will work too long

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

    Yes, choose any two element x, y, get all prime factor of gcd(x-1,y-1),gcd(x-1,y),..., gcd(x+1,y+1). Then try each factor. Each turn, you might get the correct answer with probability 1/4.

    Upd: choose any element x, get all prime factor of x-1,x,x+1. Then try each factor. Each turn, you might get the correct answer with probability 1/2.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +40 Vote: I do not like it

    I don't know, but at least I solved with randomized solution.

    My Randomized Solution

    1. When $$$gcd = 2$$$, the number of operation must be less than or equal to $$$N$$$.
    2. Let $$$t_i$$$ be the number of operation that made for $$$i$$$-th element of array. It means: $$$t_i = |a_i - b_i|$$$ when $$$a_i$$$ is initial array and $$$b_i$$$ is final good array. You can prove easily, that in at least $$$\frac{N}{2}$$$ element, $$$t_i \leq 1$$$.
    3. Repeat 30 times as follows:

    • Choose random index $$$i$$$ from $$$1 \leq i \leq N$$$.
    • Let $$$t_{-1}$$$ be the set of prime factor of $$$a_i - 1$$$.
    • Let $$$t_{0}$$$ be the set of prime factor of $$$a_i$$$.
    • Let $$$t_{1}$$$ be the set of prime factor of $$$a_i + 1$$$.
    • Let $$$T$$$ be the union of $$$t_{-1}, t_{0}, t_{1}$$$. For all value $$$v \in T$$$, check the minimum cost when $$$gcd = v$$$ with complexity $$$O(N)$$$.

    Total Complexity is $$$30 \times O(\sqrt{a_i} + N)$$$. It fails with at most $$$2^{-30} \approx 0.0000000931322$$$% probability.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you check the minimum cost in the whole set of primes T in O(N)?

»
5 months ago, # |
  Vote: I like it +129 Vote: I do not like it

The gap from A to F is pretty good, but G and H are too hard..

»
5 months ago, # |
  Vote: I like it +74 Vote: I do not like it

FaIr aNd BaLaNcEd cOnTeSt!

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

It was a tough game, but it was great!

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve D ?

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

    Hint: Consider any $$$2$$$ leaves of the tree $$$u$$$ and $$$v$$$. Say $$$lca(u, v) = w$$$. Observe that $$$w \in $$${$$$u, v$$$} if and only if $$$w$$$ is the root.

    Solution
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How the heck is F solved? I passed pretests with what I presume is a nasty wrong solution, though I don't think I'm capable of generating tests that break it. Is there anything clean for that problem?

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

    We can always make gcd=2 by using <= n operations, so let's use only < n operations. Let's say we applied operation on i c[i] times in optimal answer, then at least for n / 2 indices c[i] <= 1(otherwise (n/2) * 2 >= n). So just pick some index i and try to prime divisors of a[i] — 1, a[i] and a[i] + 1. Not sure if it's good enough to fit into TLE though.

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

      Fair enough, I guess that works. I feel dumb now.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve E?

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

    I think you can construct the answer. Maximum possible number of triples is achieved in sequences like x, 2x, 3x, 4x, ..., kx, and you can calculate how many triples you can get for each k. If m > this number for n, the answer is -1. Otherwise you take the biggest number k less or equal to n, such that m is bigger than the maximum number of triples possible for this k. The first part of the answer would be 1, 2, 3, ..., k. Then you can add just one number: something like 2*k — 2*(how many more triples you need to get m in total), and you satisfy condition for m. If there are spare numbers left (n — k — 1), you can add a sequence of type (big number) * x — 1, which does not produce any more triples.

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Great problems! What's the logic behind E?

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

how to solved D ??

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For every query, pick 2 from the current graph having degree 1. If the LCA is equal to any one of the 2 nodes you queried for, it is the root! Else remove these 2 nodes from the graph and repeat the same process.

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

Nice contest! I hope, i will get a T-Shirt ;)

»
5 months ago, # |
  Vote: I like it +93 Vote: I do not like it

In case I win a random T-shirt.

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I don't think it's allowed to send portable chargers? (lithium batteries)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can ship it on flights, given they satisfy the maximum mAh criteria. And I guess 10000 mAh is pretty much fine.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's not true. Lithium batteries are only allowed to be hand carried in passenger planes or shipped in cargo planes. Since most mail services make use of passenger planes, they outright ban lithium batteries. Even if you use carriers like DHL you will need special approval.

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

    Tell that to bootleg Chinese sellers on EBay.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

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

    If a[i] % m = a[j] % m for some i < j, then answer is 0. Otherwise there are <= m numbers, so you can calculate answer in O(N^2).

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

      Yeah the brute force will work, but I got a wrong answer in test case 15. Probably an OverFlow. I don't know what it is. I have used Long.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got WA on Pretest 9 ;/

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

        Not sure is it the case or not but...
        A possible cause is absence of "ans %= m" inside the loop after the "ans *= ..." part. I think that int64_t could be not enough to hold the value.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I even tried that, (a*b) mod m = (a mod m * b mod m) mod m but got WA on the 9th pretest itself. So then I changed it to this and no luck.

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

      You probably meant O(m^2) because O(N^2) should be TLE for N=10^5.
      I still do not get how to do that in O(m^2). Can you guys please explain?

      (The best I managed to try during the contest was O(N*m*log(N)), and I failed.)

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If ans!=0 for some i and j then it will be O(m^2) and unless m==N which is not the case(constraints).

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Got it (from this thread on this page).

        The pigeonhole principle. When N > m, existence of two numbers which are equal (mod m) zeroes the whole product.

»
5 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Is there a deterministic solution for F ?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very fine and good statements. Thank you for these nice problems, but I had some problems with pretests on problems B and C -specially.

»
5 months ago, # |
  Vote: I like it +66 Vote: I do not like it

If anyone's interested, the solution to F is described here.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow the solution to today's problem had been written 2 years ago

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

    Thanks, I was wondering why that felt so familiar.

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

Another bloody lesson on CF Round: rand() only generate [0,65536) on codeforces......

I got 6 wa and debugged for 20mins...Now I only hope that I can pass the system test...

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

    The real lesson would've been to not have this covered by pretests.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Kinda tough to do that without keeping $$$N$$$ small in pretests.

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

      We decided to be nice, it's a bit less unfun to fail in pretests compared to failing on a hack :)

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

        Bro, Thank you for being nice and preparing this excellent round~

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Very good point! I am very grateful now.

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

      Just realized I haven't touched pretests of F. Completely forgot what I've done last year with hacking rand() lul, good thing someone else covered that.

»
5 months ago, # |
  Vote: I like it +22 Vote: I do not like it

This round was one of the most interesting rounds I've participated!! Sooooo Amazing!!!!!

»
5 months ago, # |
Rev. 2   Vote: I like it -43 Vote: I do not like it

I think it's better to give a warning in the blog if the contest contains any interactive problem(s).

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

    I guess there is no rule as such.
    Usually the problem setters are kind enough to let us know before-hand so that anyone who is new to such problems, will take a look at it. :)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Yeah. Actually that's why I am talking about this. Anyone who is not familiar with such problems may learn before participating and solve more problems.

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

        Why only interactives? Just make the problemsetters announce all the problem topics so those who aren't familiar with them can learn them beforehand.

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

"**The resulting string does not have to be empty**." due to this statement i got 2WA + late submission in B problem anyone faced same issue

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oh wow so i will get WA since i just deleted all the possible brackets...... (()) would fail for me :/

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

      actually i just realized i did solve it correctly since the number of deleted brackets dont matter , it is only the number of operations that matter.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same mistake. My answer should fail on cases like () but got an AC instead

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You should be grateful that the pretests covered it.

    I FSTed. :(

»
5 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Does D involves finding longest diameter of the tree, then query end points of that dia, if output of the interactor is one of the 2 ends, return that as that root. If not, then if interactor's output is a vertex not lying on the longest dia, return that vertex. Else (if lca returned is on the dia (but not the ends)), then check recursively the same process in the subtrees of that lca (by removing connection of lca and its neighbors that are not on the dia)?

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

    It is more simple. Query two leaves, if response if one of those leaves, thats ans. Else remove those two leaves. Repeat.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this approach will fail if all the nodes are connected to the same node

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      in that case you can output the last input we receive from interactor since that is the only vertex which will be left as we have removed all other vertex by removing 2 vertex n/2 times .

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

    If the output of interactor, say w, is not one of the 2 ends(say n1 and n2) then you remove the edges connecting w to n1 and n2. You find the longest diameter again and repeat the process.

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

    I did something related to diameter of the tree.

    You may notice you want to remove a lot of nodes, which are not candidates to be the root in each query, until you are left with one, which is done (fitting exactly in queries) by the approach in the editorial, too.

    I, instead, went on querying the ends of the diameter, and removing all nodes (and of course all other nodes in "subtrees" of the diameter nodes, except the LCA returned in the query, because all of them except the "w" returned in the query, are no longer candidates to be the root as all of them have atleast one vertex "above" them), and continued to do so until I have one node remaining.

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

Systest when, fellow Stalker?

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

How to solve G?

»
5 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Tests are strong (at least not shitty) this time, yes?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Pretty sure making strong tests for F is a difficult problem in and of itself. My shitty solution passed pretests, we'll see about tests.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I also have something what I'm not sure about in E.

      Also was close in G, we'll see in upsolving.

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

      Well, your solution definitely can't get WA because the last part of your code checks all large divisors of (some number)$$$\pm n$$$ and every number will be modified at most $$$n$$$ times. The only thing I'm not 100% sure of is whether it's fast enough.

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

        Yes, in worst case scenarios it can check ridiculous amounts of primes (millions) and it checks each linearly. However, lots of optimizations and early stops make it very fast on most data.

        P.S.

        Accepted in 561ms. I am not capable of generating tests against it even if I strongly believe it's slow. Can't prove any good complexity either, but oh well, it passed.

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

          There are at most (78498 (number of primes <= 1e6) + 2 * n) primes in the factorization of numbers in [x-n, x+n] and that's a kinda loose upper bound anyway so it's not millions.

»
5 months ago, # |
Rev. 4   Vote: I like it +34 Vote: I do not like it

Hacks for C:

Hack Test Case

You can prove that when $$$M < N$$$ the answer is $$$0$$$. But, even if your source code assumes that when $$$M \leq N$$$ the answer is $$$0$$$, you will get pretest passed. (There is some hack cases like above)

For me, first, my source code assumed that when $$$M \leq N$$$ the answer is $$$0$$$, and then I resubmitted. So I was able to notice hack case earlier, but there is no such source code in my room :(

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I checked that for all N < M the answer is 0 but how to formally prove it ?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There exist i,j i!=j such that a[i]%m==a[j]%m, hence (a[i]-a[j])==0 (mod m).

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

      If a and b have the same result after modulo m, |a — b| mod m = 0. Then it's pigeonhole principle.

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

      I guess you meant M < N. According to the pigeonhole principle, among >M numbers there will be at least two (call them a_i and a_j) with the same remainder upon division on M. Since there will be |a_i — a_j| or |a_j — a_i| in the product, the entire product will be divisible by M.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Does that mean we assume all numbers given will be distinct?

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, if some two are not distinct, that still have the same remainder. Moreover, then the product will be 0 automatically.

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Ok now I get it that for n > m even if we all are distinct there will be 2 that have same modulo by m. Thanks for your help

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

    After staring at C for a good 20 mins, I had an epiphany. Pigeonhole principle! I smirked like the ninja in https://www.youtube.com/watch?v=pKO9UjSeLew

    And then wrote m>=n in my pigeonhole condition instead of m>n

    FML

»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Nice problems with clear statements.

»
5 months ago, # |
  Vote: I like it +77 Vote: I do not like it

TFW B is harder than F >:/

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Weak.Pretests on C

»
5 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Prepare for Polish Mafia in uphacking ;_;

mnbvmar, show them what you think about them.

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

    Hiiii Can you check this submission. Is this agreed in contest? https://codeforces.com/contest/1305/submission/72343610

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

      As idea looks just like a solution from editorial. Of course, it looks like full of bugs, but it's typical obfuscation, which can be found in many places in CF (and is against rules!). Ofc I'm talking about #define int long long.

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

    Please hack 72364530 72364506 72364194 72364859 . They all are same with a change in constant.

    72364859 and 72364466 are exact same but one got WA on tc93. P̶r̶o̶b̶a̶b̶l̶y̶ ̶a̶ ̶h̶a̶c̶k̶.̶ Dori added them ~20 mins before start of round.
    These are my ugly brute forces which survived system tests during testing. Idea was to run sieve and check all primes up to a constant (5e7 in the present case.) and then randomly pick a no and try to factorise it up to primes 1e4 then assume leftover prime and gcd and check it.
    The intent was to break solutions which doesn't check factors $$$a_i+1$$$ or $$$a_i-1$$$ .

    pajenegod has some similar solns which sieve up to 4e8 (using some superfast sieve.) and runs under 2s.

    One plan to break them was to increase $$$a_i$$$ up to $$$10^{14}$$$ but we didn't want to force factorisation in O(primes up to $$$10^7$$$) instead of O($$$\sqrt a_i$$$)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      You know that there is no rating limit for uphacking, yes? You can also try.

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

        We tried hacking them during testing of the round.

        Btw only div1 users can up hack.

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

shouldnt n^2 solution for C fail?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes it would, however a (n <= 1000)^2 solution wouldn't, all answers for n > 1000 are always 0's. this is why you only calculate the answer for (n <= m).

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For anyone interested in detailed analysis of problem C -- Here you go!

»
5 months ago, # |
Rev. 2   Vote: I like it -47 Vote: I do not like it

Can any one plsss check this submission . How on earth this random submission got accepted. Its cheating https://codeforces.com/contest/1305/submission/72343610

»
5 months ago, # |
  Vote: I like it +17 Vote: I do not like it

I had the proper idea for F, but my deterministic solution of course got TLE, but didn't realize I can do a randomized solution. I have never solved a contest problem with randomization till date. Can someone help me how to get started with such randomized solutions, so that it gets intuitive when I see a question in future to use a randomized solution with high probability. :)

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Does anything faster than $$$O(N^2)$$$ exist for C if the modulus was large?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    from what i've seen the absolute difference instead of a normal difference ruins most possibilities of coming up with mathematic solution. ++ for an answer.

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

      If you sort the numbers in decreasing order then you can remove the absolute.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +29 Vote: I do not like it

    I can only present a polylog solution, which should run way slower than the $$$O(n^2)$$$ solution in practice. After sorting the array we can get rid of the absolute value part. Then use divide and conquer, split into two subproblems of size $$$n$$$, then we need to multiply something which can be done using multipoint evaluation of a polynomial, which is a typical problem that can be solved using D&C and FFT in $$$O(n\log^2{n})$$$, therefore the overall complexity is $$$O(n\log^3{n})$$$.

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

      By understanding how multipoint evaluation works, you can make it in $$$O(n \log^2 n)$$$. Assume for simplicity that $$$n$$$ is a power of two. In fact, for each $$$i$$$, we want to find the remainder of the division of $$$(x - a_{i+1})(x - a_{i+2})\dots(x - a_n)$$$ by $$$(x - a_i)$$$.

      For each interval $$$[L, R]$$$ of the form $$$[2^i \cdot j, 2^{i} \cdot (j+1) - 1]$$$, compute $$$(x - a_L) \dots (x - a_R)$$$. Call it $$$P_{[L, R]}$$$. (This is in fact needed in multipoint evaluation as well.)

      Now, a recursive function $$$f(L, R)$$$ will compute all the results for $$$i \in [L, R]$$$. This function will receive $$$(x - a_{R+1})(x - a_{R+2})\dots(x - a_n) \mod{P_{[L, R]}} =: Q$$$. If $$$L=R$$$, we're done. Otherwise, let $$$m := \left\lceil \frac{L+R}{2} \right\rceil$$$ and notice we can call $$$f(L, m-1)$$$ with $$$(Q \cdot P_{[m, R]} \mod{P_{[L, m-1]}})$$$, and $$$f(m, R)$$$ with $$$(Q \mod{P_{[m, R]}})$$$. Each multiplication and modulo operation can be done in $$$(R - L) \log (R - L)$$$ time, hence $$$O(n \log^2 n)$$$ total runtime.


      Edit: notice that the "normal" multipoint evaluation does almost exactly the same stuff, only that $$$f(m, R)$$$ is called with $$$(Q \cdot P_{[L, m-1]} \mod{P_{[m, R]}})$$$; so that in each step, $$$f(L, R)$$$ will receive $$$\prod_{i \not\in [L, R]} (x - a_i) \mod{P_{[L, R]}}$$$.

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

      Can you provide links to some similar questions?

»
5 months ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

Problem C was : Pigeonhole principle

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand why my sub idleness

Plz help me

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that you need to send a new line when you print the answer.

    cout << '!' << " " << ans;
    cout.flush();
    

    vs

    cout << '!' << " " << ans << "\n";
    cout.flush();
    
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have found out why it was idleness, when i used

      cout << flush;

      its no longer idleness. Btw tks bro.

»
5 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Comment on problem C: Next time, when $$$O(nm)$$$ solutions didn't suppose to pass the TL and $$$n=200000$$$, choose your $$$m$$$ like $$$3000$$$ or something!

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

    Your solution is correct!

    The TLE was caused by an overflow

    You can see my submission of your code Here..

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

      Ohhh, Thank youuuu! Now I feel much better!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, my solution for "B" got an Runtime Error on Test 24, where the String was all "(" (length;1000). The code gives correct answer on this case ("0", that is) on my editor, as well as some online editors too, when checked upon.

Can someone please, check out and tell where it could have got a Runtime Error, because I don't think it (the code) can give Runtime Error.

Thanking you with anticipation!

Solution Link: https://codeforces.com/contest/1305/submission/72323474

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

    ll i=0, j=close.size()-1; This will init j to huge value if close is empty.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got your point,

      But actually j's value is saved "-1" through this statement, in most of the editors, as I told, above.

      Then, why does it assign a large value of "j" on the Editor and Compiler of CodeForces? Please explain the reason, if you know!

      Thanks!

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The vector.size() returns size_t, which is unsigned.

        However, if it is -1 the code still is undefined, since j is used as an index, and -1 is not allowed there, too.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it -6 Vote: I do not like it

          The "while" loop condition is there for not allowing the neg. value of "j".

          j>=0

          This condition will stop that, anyways.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
          Rev. 3   Vote: I like it -16 Vote: I do not like it

          Now, the code works, when I write the equations as follows:

          ll j=close.size();

          j--;

          Then, it works!

          Why is it happening like that?

          MikeMirzayanov

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
          Rev. 2   Vote: I like it -6 Vote: I do not like it

          Also, when I write "int", instead of "ll", it works!

          int i=0, j=close.size()-1;

          Can someone explain, why?

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

            The type of .size() is size_t which is an unsigned integer type, so if the size is 0 and you subtract it by one, it will overflow (it may become a large integer). Therefore, you should not subtract the size without type casting.

            If you use ll j = close.size();j--; or int j = close.size();j--;, close.size() will be cast to ll or int, which is a signed integer, before you subtract it, so it works.

            If you use ll j = close.size() - 1, close.size() will be subtracted before it is cast, so it is wrong. But if you use int instead of ll, it "may" (since overflowing is an undefined behavior) be correct. size_t is a 4-bytes integer type and so is int. The binary result of subtracting an unsigned integer is as same as a signed integer type with the same size commonly, so the binary value of (size_t)0 - 1 is as same as (int)-1. (The value is the maximum value of a 4-bytes unsigned integer which is $$$2^{32}-1$$$, but the maximum value of a signed 4-bytes integer is $$$2^{31}-1$$$, so it will overflow to -1 when you cast it to int.)

            ll is not like that. Although the value of (size_t)0 - 1 is -1 when we regard it as an int, it cannot be cast correctly to ll.

            • »
              »
              »
              »
              »
              »
              »
              5 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Got the point.

              Thank you so much, for such a nice explanation!

»
5 months ago, # |
  Vote: I like it +25 Vote: I do not like it

when we get the result of random t-shirt winner

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

    I guess they first have to eliminate those hundreds of smart people who, after solving A and B, started modifying their codes to send from other accounts, instead of solving C.

»
5 months ago, # |
  Vote: I like it +181 Vote: I do not like it

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove the cheaters and update them again!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Excuse me, I don't know how to report the cheating behavior, but it seems like the User Qingyu98821, who got the second place in Contest Codeforces Round #624 (Div. 3), is suspected of making his code obfuscated.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -31 Vote: I do not like it

    In problem B of todays contest it is clearly mention ed in the question that after applying the operations the string does not have the empty size. So naturally for test cases in which string is Simple string any answer is not possible.Kindly check the question..

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

      The resulting string does not have to be empty.

      "Does not have to be empty" meant it could be empty, or non-empty, will not affect the verdict.

      Mind your English, please. And if you were unsure about the statement, what prevented you from asking?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it -24 Vote: I do not like it

        ok.from next time i will ask during the contest itself..

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it -52 Vote: I do not like it

        the resulting string does not have to be empty means that after the operations the remaining string must be of non-zero size.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Actually not. That'd be "the string cannot be empty" or "the string must not be empty".

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

How to get test cases for D?

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    How is it possible?

    Time: 15 ms, memory: 148 KB

    Verdict: OK

    Input

    6 4

    1 4

    4 2

    5 3

    6 3

    2 3

    Participant's output

    3

    Jury's answer

    1

    Checker comment

    ok Passed.

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

      when the prize is T-shirt Its possible

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

      Interactive test data is quite different from normal problems.

      In this problem specifically, the "input" showed in the submission details is equivalent to the hack format described in the statement, and the "output" here is number of queries used (actually this part is quite a placeholder, since I implemented the process of judging the answer to be in the interactor, not the checker).

»
5 months ago, # |
  Vote: I like it -30 Vote: I do not like it

I solved 2 problems in the whole contest. I was relieved by this . My submission was accepted so I started thinking about next problem. Now I only got 1 correct submission . What is this ???? Who should I report to for this incident? :(

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

    Looks like your solution on B failed on system test.

    To make it clear, ịn a contest your solution will be judged by a smaller set of tests (called "pretests"). After contest time, it'd be judged again.

    We tried our best to make the pretests strong, but it's certain that not every case can be covered. :(

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

    Btw your error was on this line

    while(open[o]<close[o] && o<close.size() && o<open.size())
    

    You should have checked o<close.size() && o<open.size() before doing open[o]<close[o]. That would have given you AC, 72370968.

    One good thing about making this mistake is that you know now how to avoid it in the future!

»
5 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Give me T-shirt

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

    You'll get a T-shirt if you're lucky, Because there are only 30 T-shirts, good luck everyone.

»
5 months ago, # |
  Vote: I like it +63 Vote: I do not like it

I am just wondering what tourist does with all those T-shirts and iPads that keep piling up...

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

    Obviously he puts on all t-shirts at once and pretends to be an onion while simultaneously watching 20 cooking shows on his ipads

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

      Actually when I read it I picture Um_nik doing that. I don't know why.

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

        I guess because in 1 T-shirt I look like a human in 20 T-shirts?

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You made my day with your joke ... I am laughing now :)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    tourist be like:

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Im so sad because i miss the last one second to submit my D answer.And after the contest ,i checked it's right...

»
5 months ago, # |
Rev. 2   Vote: I like it -36 Vote: I do not like it

.

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Great round, really nice non-standard problems.

»
5 months ago, # |
  Vote: I like it +33 Vote: I do not like it

When t-shirt winner will be announced?

»
5 months ago, # |
  Vote: I like it -9 Vote: I do not like it

this contest broke my record: the previous greatest rating change(with the maximum absolute value) is +131 and now it's -145. QWQ

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

if my submission gets partially acceptd or it passes 3-4 testcases, will that be counted or not?? I am not getting rating mechanism, kindly help??

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My rank go up about 200 after the system tests...

»
5 months ago, # |
  Vote: I like it +30 Vote: I do not like it

When the t-shirt winners will be announced?

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

    I think they have finished removing fake accounts.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why Rollback, any valid reason please?

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

I guess removal of fake account done by team codeforces. Waiting for tshirt winner announcement

»
5 months ago, # |
  Vote: I like it +167 Vote: I do not like it

And the winners of t-shirts are (congratulations!):

List place Contest Rank Name
1 1305 1 tourist
2 1305 2 maroonrk
3 1305 3 peehs_moorhsum
4 1305 4 ksun48
5 1305 5 Endagorion
6 1305 6 Benq
7 1305 7 gisp_zjz
8 1305 8 neal
9 1305 9 Um_nik
10 1305 10 yasugongshang
11 1305 11 izban
12 1305 12 boboniu
13 1305 13 mnbvmar
14 1305 14 yhx-12243
15 1305 15 NoLongerRed
16 1305 16 I_love_Tanya_Romanova
17 1305 17 yosupo
18 1305 18 Radewoosh
19 1305 19 Marcin_smu
20 1305 20 E869120
21 1305 21 vepifanov
22 1305 22 BigBag
23 1305 23 icecuber
24 1305 24 ohweonfire
25 1305 25 cuizhuyefei
26 1305 26 Martin53
27 1305 27 Golovanov399
28 1305 28 qazswedx2
29 1305 29 receed
30 1305 30 ashmelev
31 1305 31 Kostroma
32 1305 32 ainta
33 1305 33 Petr
34 1305 34 SkyDec
35 1305 35 Hazyknight
36 1305 36 DCXDCX
37 1305 37 KAN
38 1305 38 cwise
39 1305 39 chemthan
40 1305 40 Quang
41 1305 41 Reyna
42 1305 42 isaf27
43 1305 43 molamola.
44 1305 44 8-_-8
45 1305 45 wrinx
46 1305 46 Elegia
47 1305 47 jijiang
48 1305 48 orz
49 1305 49 poisonous
50 1305 50 cerberus97
51 1305 51 marX
52 1305 52 AndreySergunin
53 1305 53 Maksim1744
54 1305 54 nickIuo
55 1305 55 wucstdio
56 1305 56 voidmax
57 1305 57 Noam527
58 1305 58 Alex_2oo8
59 1305 59 yashChandnani
60 1305 60 darnley
114 1305 114 Marckess
215 1305 215 olphe
386 1305 386 idxcalcal
475 1305 475 HCPS42
579 1305 579 _dsstar
765 1305 764 nicoing
866 1305 866 WildWesam
921 1305 921 smurf
1488 1305 1488 Hitesh_0301
1556 1305 1555 arshad2117
1920 1305 1920 killer_lsy
2025 1305 2025 crazy__1234
2026 1305 2026 Srk1C
2325 1305 2324 mutinner2
2427 1305 2427 zmy123456
2467 1305 2467 ssvirk
2570 1305 2569 volkov179
2690 1305 2689 vaibhavsarda
2711 1305 2711 sachitb
2932 1305 2932 Chintan_295
2961 1305 2962 wangjingting
3777 1305 3770 shreyas.mandade
3933 1305 3930 pln.
3943 1305 3944 garadu18
4188 1305 4186 AmineWeslati
4264 1305 4265 MadWarlock
4306 1305 4306 uddeshya.singh
4340 1305 4344 usertab34
4500 1305 4495 Anuj_0911
4652 1305 4657 Icewill
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey MikeMirzayanov! I can see my name in this list, might I ask how do I redeem this Tshirt? Like where can I fill in my delivery addresses and everything? (newbie at this section of forces)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can fill it at your home page where you can see an address page and select your T-shirt size.(also a newbie at this section,figured it out just now)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Excuse me,if I see my name on the list,but didn't filled the address beforehand,if I filled it now can I still receive it?(didn't even thought I'd be able to use the address page)

»
5 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Congrats to Pajaraja for his 11th consecutive rating increase, all the way from Specialist!

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

When will the T-Shirt winners be announced ?