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

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

Hello Codeforces!

I would like to invite you to CodeCraft-18, which will take place on Saturday, 20th January, 9:05 PM IST. This is a combined Div. 1 + Div. 2 round and is rated for participants of both divisions.

CodeCraft-18 is part of Felicity, IIIT Hyderabad's most awaited set of events, Threads. With a plethora of intellectually engaging online contests in various fields of programming, mathematics and general knowledge, Threads is a celebration of the spirit of computing and engineering. Other than CodeCraft, we have the Project Euler-style contest Gordian Knot and a jeopardy-style CTF event called Break In, amongst other events.

I would like to thank the CodeCraft team -- FundamentalEq, RohanRTiwari, additya1998, aman_shahi2, born2rule, codelegend, crvineeth97, deepanshugarg, devanshg27, mprocks, nir123 and virus_1010 -- for their amazing work in problemsetting. I would also like to thank vintage_Vlad_Makeev for helping us prepare the problems, and MikeMirzayanov for the great Codeforces and Polygon platforms.

Prizes

  • Top 20 participants win Codeforces T-shirts
  • Top 5 participants from India win Codeforces T-shirts

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

Update: Scoring is 500 — 1000 — 1500 — 2000 — 2500 — 3000 — 3500 — 3750

Update 2: We would like to apologize about problem F and G, which turned out to be easier than we expected, and about the mistake in the statement of H.

Congrats to the winners!

Top 20:
1. SkyDec
2. Syloviaely
3. matthew99
4. dotorya
5. FizzyDavid
6. laofudasuanbaofushehui
7. ikatanic
8. jcvb
9. Um_nik
10. molamola.
11. rajat1603
12. geniucos
13. MrDindows
14. Radewoosh
15. pavel.savchenkov
16. shanquan2
17. 613
18. JOHNKRAM
19. mxh1999
20. satyaki3794

Top 5 in India:
1. rajat1603
2. satyaki3794
3. jtnydv25
4. akulsareen
5. akashdeep

The editorial is ready!

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

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

20th is Saturday, typo I believe.

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

Only 20 T-Shirts. Please added High School Programmer Quote :'(. For Prizes

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

Please update the duration in contest tab! I am seeing 2 hours there!

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

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

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

Why is it not on the home tab yet?

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

Hope for even amount of geometry and math problems.

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

r_ _ _ _???

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

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

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

I know it is very hard to prepare a contest and we are so thankful about that, but dear authors please double check your solutions. We all prefer not to have 2 consecutive unrated rounds!

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

Are there any prizes for school students in India

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

Will the Project-Euler style contest be conducted on CodeForces ?

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

Expecting 10,000 registrations.

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

Good luck! Have fun! xD

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

Clashes with COCI

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

Here are some past codecraft contests:

2017: Contest, and Editorial

2016: GYM, and Editorial

2015: Contest: GYM, Replay on codechef and Editorial

2014: Replay on codechef

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

I wonder, is there any reason why you are not giving T-Shirts to random participants like last year's contest?

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

Its time tu up my reting. Good luk to me

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

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

So many indians, its their chance to prove that they can be good problem setters.

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

I hope one day i will get a T-shirt from Codeforces. that will be the best recognition of my hard work.

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

Will the drain be adjusted, please?

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

"The scoring distribution will be announced later" ... ?

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

На русском условия будут?

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

In Problem B, Is there any problem in range of a[i]? check my submission please.

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

problem A: Sample test 2; How 576 is a perfect square????

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

Can't hack solutions , it keeps on loading

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

what a hard contest!!

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

Getting runtime errors on pretest 1 with no error specified for problem C. Can the admin please help? It runs fine on my machine.

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

    same thing happened to me. you are probably using a different compiler. try using custom invocation option. In my case i was using negative indices

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

May be another unrated contest is running..............................

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

Even though I performed miserably in this round, I must admit this round was pretty neat as the problems were good. Good job!

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

this round should be unrated because of problem H like yesterday contest

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

    I think that, because almost nobody even attempts H, the round should still be rated.

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

    You are talking about 'H'; not 'A' or 'B'. As if you have stood 2nd because of this mistake.

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

I'm mentioned in problem H!

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

waiting for notification, when they say , round is "UNRATED " :P

C problem,,, looks interesting :P ...

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

Is fast enough for D ?

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

How to solve C and D?

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

    C digit dp.
    D answer is yes if there is <= 1 numbers that isn't divisible by X.

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

      How to find that for D?

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

        Make a segment tree where you keep the gcd in each node. A query will point to multiple nodes and you'll pick the only one not divisible by X(if there are more, there is no solution). This node has either 1 or 2 sons with a value not divisible by X. If both values are not divisible by X you have no solution, otherwise just go to the node that isn't divisible by X.

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

      Can you share your code for D?

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

      Your solution to D did not timeout?

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

    C : once you apply operation to N, it must less than or equal 1000. So you just have to pre-calculate k-value for 1 to 1000

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

    C is a DP. cases k = 0, 1 are easy. k = 2, 3, 4. needs a DP., rest k's are 0.

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

      I think C pretests are weak. it doesn't have any test case with k = 1?

      just now i noticed a problem with my k = 1. I output s.size() instead of s.size() - 1

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

Was a N * log(N) + Q * log(N) * log(N) solution supposed to pass D?

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

That moment when you realize your C will fail 4 mins before contest end after locking it.

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

    me too, for k = 1? or something else for you?

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

      k = 1. Used it to get 3 blind successful hacks in the end but still RIP rank.

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

        such a bad way to fail a problem :(

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

        Exactly same thing happened to me. So, in the last 2-3 mins, I just put that hacks in other's code. Didn't read them so got 2 unsuccessful hacks as well with 4 successful ones xD

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

          In my opinion, they should have had k=1 in test case. its not something at the core of this problem. .. but maybe that's my defeated soul consoling me..

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

        Haha, I used K = 1 to hack someone else before I realized my code would fail the case too.

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

Is E divide and conquer? If yes, how to merge the answer of 2 sub-trees efficiently?

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

    Maintaining mask of letters will work I think.

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

      Thank you. Oh! I see, you just iterate through 0^mask, 0b1^mask, 0b10^mask, 0b100^mask... right? Now the complexity is some O(26n). Ahhhh...

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

        Can u explain a bit more?

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

          I haven't solved it yet. Here's how I want to merge sub-trees. So use a 26 bit mask to represent the odd/even of letters on the paths that ends at the current node under analysis u.

          If 2 paths p1, p2 ending at u can be connected and form a palindrome path, p1 - u - p2, then, if you xor the mask of p1 and p2, either the resulting mask has only 1 bit set or all bits are 0.

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

            There's only 20 letters, [a, t]. Very important.

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

            What if there is a path p1 ending at u which has mask something like ....000011 and p2 has mask .....000010 so in that case we won't be counting p1?

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

              Since 000011 ^ 000010 = 000001, there's only 1 bit... So p1-u-p2 should also be counted in this case...

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

                But u r not storing the bits except for 00001,00010,00100,01000,10000 for each node right?

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

                  so...in my opinion, u will store all possible masks. since the number of these masks is at most O(n) (# of paths to u from sub-trees), it is acceptable.

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

            I have a doubt. In a subtree there can be atmost N possible masks and when we are merging we have iterate on them. So, isn't the complexity is O(N^2)?

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

              The solution should be a little bit different from dfs, by exploiting the information about the size of sub-trees (centroid decomposition, you may refer to the editorial).

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

Must D be done faster than Qlog^2 or is my segtree implementation just bad?

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

    I do that O(Q log^2 * gcd) with some optimization, and it runs about 2s. (Hope I can pass the system test)

    However, I think the ideal solution may runs in O(Q log * gcd).

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

    My Qlog^2 solution ran pretests in 1092ms

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

      It's possible to implement query() in O(log n) and update() in O(log n * gcd). I think that's the fastest.

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

      How does that work? I use a segment tree and binary search.

      Also, I use the pragma to optimize my code, but it still runs in 2s.

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

        This is my solution:

        Keep a segment tree of gcd()s.

        The query is basically "Is there more than 1 value in this interval, which isn't divisible by X?". You can check it by finding the leftmost and rightmost "bad" index; if they're the same, then there's only 1 bad value.

        Yeah, you can binary search this, but that's not very fast. The segment tree query will produce O(log n) nodes that cover your query interval. Then, you can iterate over them from the left, and when you find one whose (already calculated) gcd is bad, you can locate the leftmost "bad" index in O(log n), by deciding to either go left or right in each layer of the tree. The same thing can be done from the right to the left side, again performing at most one O(log n) traversal.

        Update: O(log n * gcd) Query: O(log n)

        (During the contest, I was too lazy to code this, so my query was O(log n * gcd))

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

          Simple implementation of an update actually works in O(log n + gcd).

          Idea: After each two steps of the Euclid's algorithm, both numbers will be less than half of the original ones. Therefore, the number of steps is bounded by 2*max{a_i}.

          (This should explain faster than expected running times.)

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

        That's pretty much what I did.

        For the queried range, I divided it into 2 parts and recursively went down the segment tree, until reaching a segment of size 1. If during the search, both parts had a gcd not divisible by the guess, that meant, it's wrong. Otherwise I chose the wrong part (if any) for continuation of the search,

        You can check my submission if you want to see it more clearly.

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

How could you solve C?

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

Hacking says that my version of Flash is too low to run. I am running the Flash that came with the latest version of Chrome.

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

For B : Hack Case is

5 1 1 1 2 2

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

What was the hack Case for A ?

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

by a mistake I resubmitted for problem A near the end of the contest and so I got two hundred instead of 490 which was my initial score is there any way for me to get my initial score?

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

what are the hack cases for C ?

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

    111 1

    If you don't write an if() you'll print 3 instead of 2.

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

      I bruteforced for values less than 1000 Maybe mine fill fail on larger values when k == 1

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

Why the third sample input of H is 36?

I think 1 2 3 and 3 2 1 just have a single way to modify. QwQ

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

Problem G submission by rajat1603 LOL

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

How did you guys hack problem C?

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

I Hope F is better than

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

    Bitset is better than everything!

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

    I see O(N2) solutions with bit masks at the top.

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

    I think it can be done in O((N + Q) * rootN) by keeping a suffix tree over each block of sqrtN. Not sure though, got confused with the implementation details.

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

    Me : How to solve F?

    Some red guy : Do kmp 7000 times

    Me : That's obvious, but it won't run in time

    Some red guy : Why not, CF is super fast

    Me : (facepalm)

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

I know it is O(n^3) but why does it get wrong answer on C: code

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

I really enjoyed the problemset especially the tricky ones. Thank you guys!

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

2 — 1 in last min!!

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

During contest I tried to hack 2 solutions with the test "1 -64". However they both gave unsuccessful verdict. So I copied their code by hand, put it into codeforces compiler and it gave WA! Images: https://imgur.com/a/NrhKb. However, now I put their original codes and it gives correct answer! Could anyone please tell me the difference between their original code and my copies that could cause this? Code1 Code2

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

"A path in the tree is said to be palindromic if at least one permutation of the labels in the path is a palindrome."

Is there any reason to call the special paths in problem E palindromic when the obvious notion of palindromic path is different ? I only noticed the different definition 30 minutes before the end of the contest...

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

Anybody knows pretest 5 in problem C? Maybe k=5?

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

lol

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

For C problem, I have doubt, pls someone help me...

question is saying that ,,

He calls a number special if the minimum number of operations to reduce it to 1 is k. ****

so , for the second test case,,,input is like

111111011

2

when I convert binary to integer,,, value is 507,,,

from 1, 507, there are 498 special numbers according to definition of the 'special number'...

then how come answer is 169 ... ( I know answer is 169 for EXACTLY K steps ) ...

I spent whole lot of time on C ,,, could have done D though :| ...

This is my brute force, code,,,

code is here

( this is the code to generate and check special numbers , it takes string(s) and integer(k) as input, and converts binary string to integer value(n) , and then iterates from 1 to n, and for each i check whether it's special number or not )

this is the list of the special numbers

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

    Yes, the statement did confuse me a lot, but here "exactly" is same as minimum number of operations as he any further operations is a wasteful activity on 1.

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

    The problem statement actually means that the minimum number of operations to reduce it to 1 is "exactly" k. Minimum number was mentioned in the statement with respect to the operations needed. Although this is bad on the part of the statement writer since this creates doubt as mentioned by you because the operations needed for a number are fixed and there is no need to minimise the operations. I was also stuck at this for quite a lot of time during the contest.

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

      Maybe they didn't want to tell us that the number of operations was fixed, on purpose, so that we have to figure it out ourselves.

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

        well, next time just give input and output, and we will figure out everything ourself...

        This is ridiculous, I had finished my C quesiton code in just 30-40 minutes,,, and then I was debugging that code for 1 hour,,, then decided to write bruteforce,,, and finally understood that it's "**exactly K**"

        Moreover, we can't make any assumptions ,,,

        in case you want to see my code for C question(considering minimum k)

        code for minimum k steps

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

      He calls a number special if the minimum number of operations to reduce it to 1 is k.

      The word minimum in the above statement changes entire meaning ...

      Now, don't try to fool yourself, and tell me that,,, I should look at the test case and then understand by myself,,,

      I know life is not fair,,, but I had my faith in codeforces, why you do this :( ???

      (JK)

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

      Acctually the number of operations is not fixed because you can keep aplying the operation to number 1 any number of times. So by saying minimum they mean you cannot do that I believe

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

Another Hacking round. It seems to be a hacking contest, not a programming contest.

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

    Cant be worse than me tbh. Solved B, it got hacked. I was like "Yeah, easy fix. Done. No more bugs now." Re-submitted, got accepted, immediately locked and...hacked again XD.

    Lesson: Dont hurry for few points, take time and think over the problem. In the end, thats true- we get hacked because we did mistakes.

    (Anyway, getting hacked> failing systest so...:p )

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

    Why don't you like hacks? maybe it is just because you can't hack?

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

      I can but I think to solve the problem is the matter.

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

        I thiNk that hacking (finding mistakes) is helpful because you learn how not to make your own mistakes.

        Also I solved 3 problems, but the duration of round is 3 hours, so hacking is a good way to waste your own time.

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

      I can, still my opinion is that making three easily hackable problems is not a fine choice for a combined round.

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

please stop systests at this point! haha joke

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

В чём подвох в B? Какие Тесты были для взлома? Заранее спасибо)

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

    Учитывать нужно не только самые большие элементы. Пример:

    6

    1 1 2 3 4 4.

    Побеждает Конан, взяв своим первым ходом карточку 3 (вместе с ней 1, 1, 2). Остаются 2 карточки 4.

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

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

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

    i'm so curious for the hack case do you know it ?

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

      5 0 0 1 1 1

      or

      5 0 0 0 1 1

      might work.

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

      You can check out others' solutions to see where you got wrong. The person who hacked you maybe?

      I think that's better than asking for the specific test case, because your algorithm is likely to be already incorrect anyway :p

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

So much failed system tests on C

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

    pretty bad pretests if you ask me..

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

      Actually, I guess that is intended. It makes contest worse not funner.

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

        Exactly. One can get AC after a few minutes with 1/2 additional penalty. But after system test, BOOM, you dropped down by a huge margin for some silly coding error or corner case misses which could have been easily found.

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

A good good good contest :) but too bad for me, solving E and not get acc from it just because of my poor coding skills ... :( feel so upset ...

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

if(k == 1){ res--; } and only becaus of this i lost 850 point :(

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

That moment when you got TLE on test 105 problem C... I should change my profile photo...

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

This k=1 case where most solutions count 1 and still get pretest pass is a full killer. I doubt I will be able to find such a corner case ever in my life by myself.

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

Is there some easy solution for problemE rather than DP on tree with bitmask?

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

    I type code slowly, so there seems not enough time for me. So I wish to know some simple implemented solution, thanks!

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

    If you only consider the Centroid Decomposition solution easier, then yes.

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

How to solve F ?

i see that most of the people who solved it used bitset so is it a known algorithm ?

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

Am i the only one solved E with DSU on tree? I was afraid that my solution is wrong cause it run so f*cking fast.

UPD : I tried to choose a random root. And it's even faster now.

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

    no some others use this approach like me :)

    also Arpa use this too ...

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

    how did u solve it with Dsu on tree?

    can u explain your approach ? :)

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

      Let's choose 1 as the root of the tree.

      We will use Dsu on tree to get these two things :

      1. calc[u] as the number palindromic paths such that Lowest Common Ancestor of start and end vertices is u.
      2. start[u] as the number palindromic paths start or end at u.

      So now, if we have a palindromic path (x, y), this path will pass through u only if lca(x, y) = u or lca(x, y) is not inside SubTree(u).

      So the number of palindromic paths pass through u is

      sum(SIGMA(start(v : subtree(u))) — 2 * SIGMA(calc(v : subtree(u)) + calc(u).

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

So do i get 2 tshirts?

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

    ideally you should

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

    Yes, I think we will. AFAIK, it has happened before too.

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

    The way organizers had mentioned, you should be getting 2 T-shirts but wouldn't it make more sense to pass on one T-shirt to the next winner either in Top-20 World category or Top-5 Indian category? Anyways what value would the 2nd T-shirt of same contest add for you?
    However, you guys are the winners, so it's up to you. Congrats btw!

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

I submitted my solution to problem C and it results in RE at test 5. I tried running the testcase locally, it outputs correct. I am unable to reproduce the error. Can anyone help?

My submission id: 34391810

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

    Try custom invocation and print some debug variables (maybe you forgot to declare some variable — locally it stars with 0 but on codeforces server it starts with something else)

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

    use diagnostics compiler

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

    Adding cout to begin of choose_again() removes RE. So I thing you've somewhere got UB.

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

    Yeah, you've got UB. if last cycle for i = 1 and j = 2 and number s with one 1-bit you access element at index 1, while size of bits is 1. So you've got there UB.

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

      Yeah, I found that out. Was just waiting for the problem to get unlocked for practice again, just to be sure.

      Thanks, anyway! :-)

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

this guy skipped Candidate Master!!

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

Is anybody check the brute-force solution of H?

For (n,d) = (4,2) and (4,3), my submitted solution and brute-force solution both give 268 and 364 respectively. But test outputs give 168 and 264.

My two solutions agree about some small input, so I couldn't recognize what is wrong. If anybody recognizes something wrong in my solution, please gives help. Thanks.

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

    Both players should play optimally. If for some tree Storm will win then Ember won't choose this tree.

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

      Oh, I misread whole problem statement...

      I need to sleep... Thank you!

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

Why did Um_nik disappeared from the scoreboard? I definitely saw him on the scoreboard..

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

    Admins decided that I was heavily affected by issue with problem H (probably because I was the first one to submit a clar about wrong sample), but I certainly wasn't, so they will restore me.

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

      Oh, I got it. Thank you for your response. It was great that you solved problem H finally!

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

    Probably he spent some time on H and found an error in the statement. Since he spent some time there he probably asked to be out of competition

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

I am not able to figure out wrong logic in my approach for C. I precalculated the number of 1s in binary representation from 1 to 1000. Now I start from 1st digit. If it is 1 I have 2 options. Put 1 and move to the next digit or put 0 and make number of 1s equal to all precalculated values with k-1 1s. If it is 0 I move on to the next digit directly. For example k = 2 then I try to make number of 1s equal to 2, 4, 8, 16, 32... so that in next step I get 1.

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

The last year magic was canceled in the scoreboard

UPD: It's fixed

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

WTF is happening with the rating changes?

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

What happened. The rating just disappeared

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

    I guess history just repeated itself :(

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

    They are updating some scores. Usually it is someone who was detected of cheating that acctually wasnt — so they reinsert him in the scoreboard (which requires everyone's rating to be uptaded).

    So no, it does not mean that the contest is unrated

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

      I hope

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

      I am not sure but I guess they are checking Um_nik's submissions because first the contest was made unrated for him (see his comment above). So they have to change the rankings.

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

        Um_nik obligingly pointed on the issue in the H and spent a lot of time to argue his point of view. I've made him "out of competition", but he asked to return him despite he has negative rating change. He is my hero for today!

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

      It is Um_nik but not for cheating but for not bothering a legendsry grandmaster

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

 What happening

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

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

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

Why there is no changes at the top rated board?

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

MikeMirzayanov Hello Mike! I'd like to ask a question. Is there any way to test someone's code with a large file data or a data generator after a contest is completed? After this contest, I've do some analyses for the problems, and found some coders' solution make me confused after calculated the time complexity myself, so I want to do a test to those solutions. Many thanks!!

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

I got Top 20 this time.How can I receive the T-shirt, thanks. I haven't receive any gifts from Codeforces before so that I do not know what to do. @Superty

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

I have question about ProC(testcase 27):

11111100010011110101100110100010001011100111001011001111101111110111001111011011110101100101001000111001000100000011011110110010001000111101001101001010100011 1

It have 158 bytes and we can set every bits to '1' and they all less than N.So why the correct answer is 157?

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

where is the tutorial ?

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

so sad...

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

Please help me why mycode 34405334 for problem C is getting MLE, my sloution is somewhat similiar to the editorial.

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

    You have initialised an array with size 4*10^8 bytes. C++ has a limit on its array size to around 2*10^7 bytes.

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

Can anyone tell me what's going on? Yesterday on system tests I got TL for problem D. But after some hours I send absolutely the same code and got accepted. How does it works?

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

    yeah with 4 ms difference from tl

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

      It isn't important, I'm don't understand how two same solutions can work for different times.

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

        System load is probably the factor :)

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

          I think CF should seriously think about this problem. For example;e someone can got accepted on pretests in round time and after that get TL on the same tests on system testing only because system load...

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

Thanks for very interesting problems

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

Can anyone explain the sample tc #2 for Div. 2 C.

If I'm not wrong, we will take all the numbers with 2 bits set, 4 bits set and 8 bits set.

Because 11000000 -> 010 -> 001

Similarly, 1111000 -> 100 -> 001

And, 11111111 -> 1000 -> 001

But C(n, 2) + C(n, 4) + C(n, 8) exceeds 169.

Please, point out my mistake. Thanks in advance.

Edit : I was computing C(n, 4) wrong. So stupid of me.

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

The contest problems were amazing , I solved only 2 of them , but got some rating + , so I am happy with it :D