TheWishmaster's blog

By TheWishmaster, 8 years ago, translation, In English

Greetings!

Codeforces Round #338 (Div. 2) will be held tomorrow. Note that round starts at the unusual time! This round was made by Maxim Vinnichenko(maxkvant), and me, Alexander Zoykin. It is our first round and we hope that everything will be OK. Thanks to GlebsHP for the great help in preparing the contest, Bobrosoft for being more than tester, Delinur for translating the statements into English, and MikeMirzayanov for the great Polygon and Codeforces systems.

score distribution 500 — 12501750 — 2000 — 2500

Good luck!

upd Congratulations to winners!

div 2:

zhangzj_is_our_sun

marcorezieho

Claris

ucfpt

Tomer.Adar

div 1:

I_love_Tanya_Romanova

ngfam_kongu

sd0061

pavel.savchenkov

ershov.stanislav

Editorial

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

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

Pretty weird. This blog was posted 21 hour(s) ago and according to it, contest should be held today but it will be held tomorrow. Moreover registration was closed 24 hours before the contest. :-|

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

I hope problem statements be as concise and clear as the post :D

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

    The statement of Problem B is really ugly...

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

I wish the contest would be later... I will miss it.

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

Сuriously, will magic color be changed after rated contest?

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

    The Standings must look very cool with all these popping red colors! :D

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

    Curiously... then we won't be able to be Legendary grandmasters.

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

    i think the magic color will not change before 10/1 but your rating will change after the contest

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

    Finally after contest both magic color and my own color wasn't changed through i have up my rank...:(

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

A nice time for Chinese coder:),hope to work out 3 problems or four:D

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

This contest will be very interesting and there are many hacks , dp and graph problems.

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

Hope to have some interesting Problems with Small , Concise & Easier to Understand Statement . All The Best .

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

Registration open during contest ? Is it indended or is it a bug ?

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

Should be called hello 2016...

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

hope it will be good first round for you guys

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

Good luck to all of you! Hope you'll have fun with the first contest in 2016 :)

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

Sorry, I didn't have that long experience on codeforces. What's really that polygon for which you always thank MikeMirzayanov, TheWishmaster ?

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

    The platform that contests are hosted at. Their own, handwritted (handbuilt?) Ejudge. A pretty neat thing, if you ask me. Link.

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

    Polygon (https://polygon.codeforces.com) is a system to prepare programming problems and contests. It is used for each Codeforces round, but not only: many other contests are prepared in Polygon.

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

A lot of Legendary grandmasters will take part in this round!

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

I'm currently a blue coder because of the Magic (my actual rating is 2510). Can I take part in this contest as a Div2 Contestant? Is it rated for Magical Div2 coders?

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

    i think it depends on your rate not on your color and if what you say is right most of Div2 contestants will not be able to participate in this contest as they change their color into red "or any other Div1 color" and in this case this contest will change from Div2 contest into Div1 contest XD except form a few contestants who doesn't change their color XD

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

First time participating as a Legendary grandmaster :D thanks Codeforces for this opportunity :)

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

    First time as Legendary Grandmaster as well for me! Feeling so nervous ^_^

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

      That magic just changes the color of your name . that's all . it doesn't make you a real legendary grandmaster ! :))

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

I bet this will be the first contest when I will hack Legendary Grandmaster :)

Good luck to setters, my frist round as setter (and the only one in the cf) was very stressful :)

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

orzdyh orzjc orztourist orzWJMZBMR ORZ TooDifficult 23333333

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

Score distribution pls?

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

hope good rating this time

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

I missed the registration due to unusual time. Can i any how give the contest now ??

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

Why do you change the time limit in problem C without notification?

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

    We were not changing any constraints or time limits during the contest. However, they were changed just before the contest, so it may happen that you got old version because of caching. We apologize for the inconvenience.

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

      It's strange. I've seen that the time limit of Problem C is 1.5s when I open the page of Problem C first time. I submitted the problem and got TLE, and I found my program just run 1000ms. So, I check and confirm the time limit is 1.5s. But when I refresh the page, the time limit had been changed to 1s.

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

      This is a very serious issue, my rating was not affected by this because I am in div 1, but it changes a lot in a solution with hash to have 1.5x time and the time hints about the level of optimization required. Please try to design a way to prevent this from happening in the future (all people should read the same statements)

      PS: If it wasn't obvious I also got the 1.5seconds time limit

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

In one of my hacks i recognized that the person is printing "Yes" instead of "YES" .. i thought i will get it but i was penalized for it. can we print in any format other that that was specified in the problem. the problem A is clearly saying to print "YES" and "NO". Please look into it

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

    I guess the checker is case-insensitive. How do you think that person's solution would pass the pretests if the checker was indeed case-sensitive?

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

      maybe.. but i got -50 because of that and i thought maybe the pretest didnt have any answers with "yes" sometimes they leave out many cases in pretest so we can hack

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

        There is a special note on the hacking form: "Attention: the most checking programs ignore whitespaces and case of keywords (e.g YES/yes, NO/no, etc.) while judging participant's output".

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

          Oh sorry for my comment then .. Thanks for clarifying

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

Hm, for me E was easier than C and D :)

UPD: Actually I think its even easier than B too. Just a bit hard implementation because of math on big numbers. It has no complex algorithms or hard ideas, just obvious pattern and mid school math.

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

    but i cant find the pattern. can you tell me?

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

      Instead of thinking them as hexagons, think of them as squares.

      Now, after 6 steps, it will be on x-axis. Just take it from there. n%6

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

        You just nailed it!!!

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

          The only thing I nailed is A. I solved D, but I can't code it. B is fucking beyond me. I dind't even read C. I only read E after I read Beresta's comment, and since I'd already fucked the round up, I didn't have much hope left. Besides, what's the point in having something so div2A disguised as div2E

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

            I don't think B should be beyond you. You are a candidate master. I understood and solved it.

            It is just find the longest path length that ends at node i. This can be found with dfs.

            Then multiply this with the number of neighbors of i.

            Maximize this value over all nodes i.

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

              umm.... he isn't a candidate master :v check his profile

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

              The approach I came up with for B is not pretty.

              First, you have to do a DP on tree using DFS to calculate contiguous segments. Then, you have to take care of bends(reverse logic of the previous dfs). Store bunch of things, like endpoints, degree of each node, etc.

              It just didn't feel like div2 B.

              Besides, I may be wrong.

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

                you just have to do the dp using dfs and store the degree. Taking care of bends, storing endpoints are not necessary

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

                  So if the root of tree is 3, and one branch has 2,1 and another branch from root has 4,5 what will you do then?

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

                  the idea is to start iterating from the maximum node. first you take 5 and and calculate the maximum obtainable tail ending at 5 , store the value in dp , multiply it by degree. then continue doing this for 4,3,2,1

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

                  Yeah, that's how you handle bends.

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

                  Got it! Thanks :)

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

      So, on each iteration we do a full cycle around the last spiral starting in right-bottom corner. Full cycle done in 6 steps (move top-right, top-left, left, left-bot, bot-right, right). All these steps except second will have the same length, each cycle increasing by 1. Second step has one hex less length.

      So on Nth iteration we will do (6N-1) steps to made a cycle.

      So from progression formula it will be (3N+2)*N steps to made N iterations.

      From input we substract full cycles by solving the equation. After that just do at max 6 more steps to finish remaining steps.

      The solution is O(1). Most hard part is to mess with big numbers.

      Passed pretests and I done some testing manually, so 90% sure it is correct. Will be 100% after system testing :)

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

        Well, got WA on #103 :)

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

          Messed up with big numbers in that one. Small fix and now it is AC.

          So, the algorithm is correct, just messed up with implementation.

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

    Why problem E problem E?

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

    I just read the problem in the last few mins, after solving D (I didn't attempt C first), and realize that it is quite easy -_-

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

How to solve B?

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

    I didn't solve B. I think C was easier than B

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

    Iterate over each vertex and fix it as the end of tail. Now however long the tail you choose(ending at current vertex) the spine will be same, which is the number of edges originating from current vertex. So, that value needs to be multiplied with dp[x], which is the longest decreasing sequence originating from current vertex. You can precompute dp easily in O(N).

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

      Thank you! With that description I managed to get the solution without the graph structure 15261877.
      Very beautiful :)

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

    my solution is
    for node 1 to N
    it can be a node of a tail(a,b,c...N)
    a<b<c<...<N
    can build max tail for each node

    ans is max (len(max_tail[N]) * connection[N])

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

    B is killing me.

    I've spent like 20 minutes reading and reading and reading the statement. So overwhelming.

    And after that got hacked 5 mins before the end, couldn't figure out whats wrong with my solution in that time.

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

      Oh my god, stupid overflow of int32. I don't really want to see my rating change after this contest. Solved A, B, E but because of stupid mistakes have only A left.

      It is so awful. Place #2832.

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

      Me too but got WA on system test. Translation of problem B was blunt. I think the test case which yours was hacked is this one.

      10 9
      1 2
      1 3
      1 4
      1 5
      1 6
      1 7
      1 8
      1 9
      

      Expected Answer: 9

      After contest I figured out that tail can be only one point ( no segment :D ).

      BTW problems were good.

      Statement ( girl who translated the statement :D ) just trolled me ( maybe my English trolled me )

      She wants to paint the tail that satisfies the following conditions: 1. Only segments already presented on the picture can be painted;

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

        The contestants mostly got hacked because they used int, I also got hacked 10 minutes before the end and was completely dumbstruck. But then I changed the final ans to long long and got AC. And during system test , many people failed on B. I checked some of them and they all had this overflow issue

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

          I'm sure many got WA because of overflow. But the statement was evil for people who reads carefully.

          She wants to paint the tail that satisfies the following conditions: 1. Only segments already presented on the picture can be painted;

          This means, To paint a tail then paint segment o.o. Problems were good but translation was bit dummy. Any Thanks for great platform. Good luck to all :D

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

What was 3-d pretest for D? Can't detrmine whats wrong...

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

Extremely weak pretests in D killed me today :(

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

What is the hack test for problem D!?

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

    Contestant's mistake: (ab)%MOD ≠ (a(b%MOD))%MOD

    What it actually is (ab)%MOD = (a(b%(MOD - 1)))%MOD

    Contestants solution were working if b < MOD - 1

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

      could you please explain why to use b%(mod-1)
      my solution also failed for that reason.

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

        Little Fermat Theorem. a ^ (p — 1) is 1 mod p, and you can avoid groups of length (p-1) in multiplication because they are equal to 1.

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

        By Fermat's Little Theorem we get that

        ap - 1 ≡ 1%p, so if b = n × (p - 1) + r, then,

        ab → (an × (p - 1) + r)%p

         → (an × (p - 1) × ar)%p

         → (an × (p - 1))%p × (ar)%p

         → 1 × ar%p

        Here r = b%(p - 1)

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

          Except carmichael numbers

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

          I got the formula right, but used inverse of 2 while calculating (a ^ (p/2)%MOD-1)%MOD. It got WA. Why ?

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

            That is because 2 and 109 + 6 are not co-prime and inverse exists only if the pair of numbers is co-prime.

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

      I used some value and understood that (a^b)%MOD ≠ (a^(b%MOD))%MOD

      but couldn't understand what would be the alternative. could u explain why (MOD-1) ?

      (upd) just saw your reply, thanks

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

      I took MOD -2 :(

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

Very well prepared round and the problemset was good! :)

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

Hmmm what's wrong with the code here?

http://codeforces.com/contest/615/submission/15249100

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

How to solve D??

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

    Use formula:

    p(n) = n ^ (d(n) / 2)

    where: * p(n) is multiplication of all the divisiors of n. * d(n) is count of divisors.

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

      but, why?

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

      So how do you calculate the number of divisors fast?

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

        n=p1^e1 * p2^e2 ... pk ^ ek

        number of divisors is (e1+1)*(e2+1) .... *(ek+1)

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

      it`s not quite correct for example: 2 3 3

      d(n) = 3 d(n) / 2 = 3 / 2 = 1 9 ^ 1 = 9 the correct answer is 27

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

        Well, in maths 3 / 2 = 1.5, and 91.5 = 27, so mathematically speaking it is absolutely correct.

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

    Formula.(I think this is the formula. Feel free to correct me)

    let k=frequency of a prime

    then, ans=product of((prime^(2^k-1))^(sum/f(prime)))

    sum=product of(frequency of prime+1)

    f(prime)=frequency of prime+1.

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

    If n is not a perfect square, then every divisor d1 can be paired with the divisor n/d1, which is distinct from d1; the product of these two is n. So the product of all divisors is equal to n^k, where 2k is the number of divisors. (Note that a positive integer has an odd number of distinct divisors if and only if it is a square).

    If n is a perfect square, then it will have 2k+1 divisors for some k; the product will be n^k×√n=n^(k+0.5).

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

    First of all you want to bundle all primes with the same value. You now have n = p1e1p2e2...pmem

    All divisors must be written in the form d = p1f1p2f2...pmfm, where 0 ≤ fi ≤ ei.

    Then we know that the product of all divisors d is:

    We see that all factors from i1 to im - 1 are not depending on im so we can put them outside the last product when we raise it to the (em + 1)'th power. In fact we can repeat this process for every term, and so we can split this product into m terms to get the following result:

    Which is equal to:

    The inner product should be calculated by using two precalculated tables:

    One table for the products from i=0 to i=j-1

    One table for the products from i=j+1 to i=m-1

    To prevent overflow, everything in the exponent of pj can be taken modulo 109 + 7 - 1, using Euler's theorem.

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

      How could we apply modulo 109 + 7 - 1 in the exponent of pj, since we have a division (by 2) and 2 and 109 + 7 - 1 aren't coprimes?

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

        ej is at most 200000, so we calculate ej·(ej + 1) without using modulo because it won't overflow. Then you can divide by 2 because it will either divide ej or ej + 1. Then after multiplying with the product you can take the modulo.

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

          Hmm... So if we have an expression like (a / b) % c, we can always divide a by b before taking the modulo if b divides a?

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

            Correct! But if you calculate a by some crazy formula, you must check that it won't overflow. In this case, you must use long longs for calculating ej(ej + 1). Otherwise it might overflow for large ej and then the value is negative, and might not be divisible by 2 anymore.

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

              Got it! Thank you a lot for your explanations!

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

      I've done EXACLY like this(or at least I meant to do so) but I get WA on test #12 which looks really easy, it is basically just 200 000 , 135391 's so we should print:

      135391 ^ (sum of all numbers from 1 to 200 000) but still getting WA,code : 15258784

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

        1LL * x * x * a van produce an overflow when both x andere a are very large, so you could mod 1LL * x * x before multiplying it with a.

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

      If you're using a language with fast enough arbitrary integer arithmetic, just compute the entire product. See 15259490.

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

In problem E i am getting wrong answer at pretest 2 but for the given test #2, i am getting right answer on my machine as well as on custom invocation. are they different test cases?

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

    I have exactly the same trouble with you.

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

    So, it's turned out that the second pretest is different from the second example. Never seen this in the past...

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

Nice problems, but bad performance by me :( I hope to do better next time :)

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

I think difficulty is:

A,D,E,B,C

At least for a math student. Although I somehow kept gettin WA on E. No idea why.

For problem D, if x is the number we just want . Unless x is perfect square, in which case we want

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

    I don't know about E I read till D. So according to me, the difficulty was A < D~=C < B.

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

    I'm sorry, if the question is silly, but how do you make these formulas here? :)

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

      You wrap the text in dollar signs. Like if it was a latex document.

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

How to pass the pretest 4 for D? I don't even figure out why I got WA.

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

    I think it was a case for perfect squares because when i fixed my code for perfect squares it passed for pretest 4. Not totally sure though because I haven't checked the test cases manually yet

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

    Fuck, I always compute sqrt(n*t(n)), but there are 2 sqrt by module p...

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

Hey in the second problem what if tail is 2 and 5. then the spines will be 1-2, 2-5 2-8, 5-3, 5-4 ans should be 2*5 = 10?

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

    only the edges from tail endpoint will be considered as spine . in this case the tail end point is 5 (maximum node value in the tail), so the spines in this case are 2-5, 5-3 and 5-4

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

hmmm I don't see what is wrong with the code here: http://codeforces.com/contest/615/submission/15249100

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

hello , you can give me solution B , thank you so much

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

    For each vertex x, find the longest increasing sequence ending in it, we save it in L[x]. We can do this with a dfs starting with the largest integer, and setting the maximum length of a sequence ending in x as 1 + max, where max is the longest sequence ending in a neighbour of x that is smaller than x. You can look at my submission for more details.

    After that, we just have to calculate the maximum of d(x) * L[X]. Where d(x) is the degree of vertex x.

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

    I don't know whether my solution passed yet, so I'll make a sketchy description.

    Let's enumerate all the vertices. At every step of that loop we'll consider the current vertex as the beginning of the tail. Inside the loop we're going the grow our tail step by step using dfs. On each step, dfs processed the last vertex of the tail, so it must have the biggest number among those we've already encountered. If the current vertex we are processing is the last, then we can also count how many spines there are. The number of the spines is the number of the adjacent vertices to the current back of the tail. So, we multiply the current length of the tail and the number of adjacent vertices and store that number in some global variable. If, during our dfs processing we're encountering bigger beauty, then we update that global variable. DFS continues till it can find the next vertex with the number bigger than the current number.

    If my approach is correct and there wouldn't be any beautiful descriptions of the solution, I'll make a more detailed description with pictures :)

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

I think the English in the problems is really bad and misunderstood. Especially problem B: "The number of points", they said, seems to be confused! Is it better if we simply write "the point" or "index"? Moreover, "endpoints" couldn't be the last point, this is not the meaning of "endpoints". Fortunately, they have noticed this and announce other contestants. Anyway, it was such a difficult contest for me and there were a lot of fun. Thanks :)

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

When does the editorial usually come out? Last time it came out as soon as the contest finished :)

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

    recently it comes out real fast.so I don't think it will take more than "a few" hours

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

    Usually we publish editorial immediately or in one hour after the contest ends. However, this time that may take a bit longer. Anyway, solutions for all the problems are already mentioned in comments.

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

This time limit for C is a joke, isn't it? All solutions using hashing failed on test #20 due to TLE.. And difference between N^2 and N^2 * LOG is not huge....

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

    same ! got tle on test #20 ... I assume they were expecting some trie based solution for that :|

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

      Could be also solved by Z-Function.

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

        I used only std::string member-functions, very easy and straigtforward solution.

        Submission: 15255098 46ms.

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

          Greedy solutions works here?

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

            It is easy to prove that it works.

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

      My solution was based on trie and I got TL anyway, 15252039. I think the time limit was very tight and it was not set taking into account Java solutions.

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

        My solution got ML on test #23. after changing vector(27) to map I got accepted in 900ms

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

    Same here :(

    BTW: wasn't the time limit = 1.5sec

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

    We were expecting a very stupid solution, that does nothing except straightforward comparison of the strings. It works in 70ms on all tests. As for trie and hashing, we set the timelimit such that it will pass depending on it's optimality.

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

      Exactly. I solved it in that way. But, I make a precalculation for saving some starting positions (for later finding longest match in a straightforward way)

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

      Why was the timelimit changed from 1,5s to 1s ? Also, the sad thing is that on Good Bye 2015 hashes for n = 5000 were accepted and today for much smalled constraints they fail :(

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

        You are free to generate maxtest and use "run" tab to see how long does your solution work.

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

          But... how? I've never known about such a feature o.O Where can we find it ?

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

          Sorry for the insistence in the same topic but you seem to disregard the importance of the fact that different people get different statements. Assuming that the time limit didn't changed during contest and it is a caching issue the is is HUGE, today it was a 0.5 seconds difference but tomorrow it may be a last minute FIX on a bugged problem, and the worst is that the people affected have no way to know!

          PS: Referring as to GlebsHP doesn't answers the Why was the time... ?

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

    my N^2 DP approach got stack overflow :D

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

    I solved it using Z algorithm and it runs in 77 ms in the worst case. 15255258

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

Sorry to say..but a better indication of these line could fetch more AC's.

3.The numbers of points from the beginning of the tail to the end should strictly increase.

  1. The number on the points from the beginning of the tail to the end should strictly increase.

The translation is no doubt awesome( The job you guys do is really good ..please don't mind) but this whole line changes the problem in a second.

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

    Completely agree with you, but anyways is a great problem.

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

    Exactly. I understood this line after 15 minutes of reading the problem

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

    Yes, initially I thought that there are no cycles. "Number of points increase" :P

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

Problem E saved some people :)

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

I must say the problems are pretty nice ;) I spent two interesting hours of coding.

But I can not tell that I like third task, I can not understand why we should print anything more than number of needed strings s. For me that change task from nice to boring.

And yes, I hacked one Legendary Gradmaster :D

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

link Can someone help me?

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

I liked the problems, they were very nice but I hate B's statement.

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

    I think it's safe we all did :-(

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

    Here's how I got B's statement.

    1) Read the problem statement (WTF) 2) See the picture below (eh?) 3) Read the problem statement again (getting the hold of it) 4) See the picture again and compare with my understanding (oka, time to code)

    though I got WA first, then got pretest passed, then got HACKED :v , and at the last moment got the right solution

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

      Eh, I forgot to use the current vertex in the dfs and got TLE (unfortunately it passed pretests ... ) :D :D :D

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

For the problem B i just sorted all the edges according to source and destination and then i just iterated over all of them with maximum length tail that can formed by keeping the starting and ending point of that particular tail and it passed :)

http://www.codeforces.com/contest/615/submission/15255459

Though it is in practise now because i didnt took 1LL while i was calculating result so its got overflowed :(

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

Ratings updated

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

    It is funny that for unrated people color wasn't changed:

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

And i rise again, just because i solved A fast enough. :D

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

Is there a way to get a full test case? I got wrong answer in problem C at test case #20 and I really don't know why.

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

Could someone tells why this gives WA!! what I missed here?! problem D 15242486

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

What happened to problem B? I left it with all test passed after 1 hour and a half then I had to leave my pc and now I see that I got TLE on test 34.. Did you reevaluate the sources?

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

    After contest will be system tests, there are about 100 test, if your solution will not pass one of them it will be wrong answer. That's codeforces system testing! ^_^

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

    It passed only pretests, which is only a part of the entire test set.

    After contest ends, all solutions are running through full test set.

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

Solved A and B and then spent over 1 and a half hour on problem D and couldn't pass test 12. My approach was:

Knowing that n = p_i^x_i * p_i+1^x_i+1 * ... * p_k^x_k, I tried to look at each p_i and count how many times it's used in d(n), the multiplication of all divisors of n. My goal was to find d(n) as p_i^y_i * p_i+1^y_i+1 * ... * p_k^y_k, multiply it all and find the result MOD 10^9+7.

For each p_i we have y_i = sum(1 to x_i)*((1+x_1) * ... * (1+x_(i-1)) * ... * (1+x_(i+1) * ... * (1+x_k)). You can use p_i from 1 to x_i times and for each p_j != p_i you can use it from 0 to x_j times to build one divisor of n.

Someone used the same approach and passed test 12? Or can you point me where I'm wrong? This problem is killing me.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    1. y_i can overflow (e.g. we have 100 different primes in input), y_i will be more than 2^99. It should be calculated modulo 10^9 + 6.

    2. AFAIU you will get TLE if you will calculate each y_i separately.

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

      Oh, I was considering (a^b)%MOD == (a^(b%MOD))%MOD as true, never thought about it and didn't see it was false during the contest. Learned something today, thank you.

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

    My first solution failed Pretest 12 too. I think it's overflow since my resubmission changed some ints to long longs.

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

looks like the magic thingy has done something pretty weird with the "became .." portion

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

Why second test in problem E didn't match with second test from samples during the contest? But now it matches.

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

Explain, please, where's the bug  As you see, I have verdict: ans is too long. And at the same time ans isn't too long (23==23). And it is correct, because checker should give another verdict in the case it's incorrect

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

is this only me or there is a legendary master in div 2?

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

    Dont worry, it's just a present from Santa Claus)

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

      i didn't expect this to be down voted so many :) but i was dumbly confused, maybe i missed the news about this :D

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

Could you explain why my solution to problem C gets TL. Here is the link: http://codeforces.com/contest/615/submission/15258328 i made several assertions for TL ( bad() function ), but still can not get where the solution stuck.

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

    Try running your code on custom invocation using this random testcase

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int main() {
      for(int i = 0; i < 2100; i++) printf("%c", rand() % 2 + 'a'); printf("\n");
      for(int i = 0; i < 2100; i++) printf("%c", rand() % 2 + 'a'); printf("\n");
      return 0;
    }
    

    Your code run 1528 ms. And it's RTE too. It's O(n^2 log n) because of map. Try finding better approach (i.e. without log n factor, don't use map, etc.)

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

      But as you see there is a function ( void bad() ) checks for TL, in that case i should get runtime error, instead TL.

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

Can anyone tell me why I am getting runtime error on test case 23 in problem D? http://codeforces.com/contest/615/submission/15258241

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

Became Candidate Master! What a Magic :D

picture above taken from rating change page

and some other people who didn't use magic and promoted today to another color their color didn't change :D

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

I think there is a problem crash on Problem D tonight.

It's quite similar to the problem BestCoder Round #61 Div.1 Problem 1003, which was held on 2015-10-31 19:00~21:00 UTC+8, which may be a little bit harder than tonight's problem D(I think).

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

Can the problem B be solved using only dfs?

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

    If you're writing a dfs without remembering anything, then it's impossible to pass this problem.

    If you're writing a dfs, which will remember the answer of certain node it gave before, and will give you the answer directly if you ask later, it'll work.

    15242225 It's a good example.

    BTW, in fact, a for loop will solve this problem directly, since the graph is a DAG, and you know exactly the correct order to visit them (from 1 to n).15255434 Here's mine solving in this way.

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

    i don't think it can. As I have no control over the degree of the nodes, There is no avoiding checking all the nodes for the tail length multiply the node's degree. And as doing DFS from each node will cost you TLE, you must use a dp table

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

I think the problems are good.Howerer I really felt unhappy when I got "Wrong Answer at pretest 1" ,just because i didn't wirte '\n' in the end.

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

For problem D why does this solution give WA on case 23 ?

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

    The way you're finding the divisors is wrong.

    There are over 10,000 primes betwwen 1 and 200000. If your program is given all the primes between 1 and 200000, the variable divisors you're getting is wrong. In fact, it's way larger than a long long int can repesent.

    Some tricks are required here.

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

      I only found the number of divisors , not the divisors . variable divisors is sum of (power of each prime + 1). If this number is odd , that means N is a perfect square so I calculate temp which is basically the root of N. then the answer is simply N^(divisors/2). Whats wrong in this ?

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

        I just mean the way you are calculating the number of divisors, or in other word, the variable divisor.

        Line 40~41 in your code is:

            for(map<ll int,ll int>::iterator it=m.begin();it!=m.end();it++)
                divisors *= (it->second + 1);
        

        which is absolutely wrong. Since the number of divisors can be really large.

        There are over 10,000 primes betwwen 1 and 200000. If I give your program 10,000 different primes as input, the number of divisors will be 2^10000 ,which is impossible to represent by a long long int variable.

        So some number theory tricks is required here.

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

Can this solution be optimised to pass task C ? (right now it gives TLE on test 41)

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

I want to clarify a bit the B's problem statement for myself, so that I am not prone to make such a mistake in the future.

  1. "The tail should be continuous, i.e. consists of some sequence of points, such that EVERY TWO neighbouring points are connected by a colored segment;"
  2. "all the SEGMENTS, such that ONE OF their ends is the endpoint of the tail"

Aren't these statements mean that the length of the tail MUST be bigger than 1?
If not, I'd like to see an explanation for that, because it will make me a bit wiser in the future.
Specifically, I'd like to see how the logical inverse of the first statement looks like.

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

    Here is my attempt to construct the unambiguous tail.

    A thing is a tail if the following statements are both true:
    1. Statement A: the tail is a vector (a1, a2, ..., an).
    2. Statement B: there is no element in the vector such that the element is less than or equal to the previous element. The same thing simbolically: ai - 1 & ai (ai > ai - 1).

    Notice the existential quantifiers on the left-hand side of the implication. If the left-hand side becomes false, then the whole statement is true, which allows the tail to be a single vertex. The thing is not a tail when the following statement is true: ai - 1 & ai (ai ≤ ai - 1).

    Could the same thing be done with the statement
    The tail should be continuous, i.e. consists of some sequence of points,
    such that EVERY TWO neighbouring points are connected by a colored segment;
    ?

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

    You are analyzing too much and making the thing complicated.

    1)Tail will have some points. two points will be connected by a segment. The points connected will form an increasing/decreasing order. The node with the maximum value is the endpoint. If you take only one node, it doesn't violate any of that. It has some points (one). Two points are connected by a segment (there are no two points that they are not connected by a segment). The points connected will form an order (trivial, there's only one node).

    2)The tail endpoint is a node. and all the segments that form the spine will have this node as one of their ends. This statement looks clear to me compared to previous one

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

      Maybe not too much — It's in the statement

      She wants to paint the tail that satisfies the following conditions: 1. Only segments already presented on the picture can be painted;

      This means — To paint a tail then paint a segment. Translation just trolled some people and some people got AC instead of getting hacked o.O

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

        Only segments already presented on the picture can be painted. This statement may be redundant but does not derail the main statement . "paint a tail then paint a segment"- this doesn't make sense, does it? because only after painting a segment u get the tail. a tail is already painted, why should u paint a tail again? :v

        You might have some problem with translation issue. But please don't demoralize people like me who have solved it after much hardship by saying things like "some people got AC instead of getting hacked" :v (I also got hacked once) . It makes me feel very unaccomplished :/

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

    Statement of B was very ambiguous. I thought during the entire contest that we can use two end points. Translation was not good. The problem should have had a mathematical formulation written along with it to avoid confusion.

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

Tutorial?

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

    according to this comment

    solutions for problems mentioned in comments!!!

    you have to read all comments to see solutions

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

Anyone notice that the Length constraint for strings for problem C changed from 3000 to 2100 and the time limit changed from 1.5s to 1s without any announcement?

BTW, the problems are very good , thanks

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

When will the tutorials be translated?!

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

If someone please can help me with some explanations to the D problem, I got a bug/problem and can't find it. I've read some comments but still not found the bug after 2 hours. Here is the code: http://codeforces.com/contest/615/submission/15260805

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

    x = multi( x , z / 2 );

    You should get rid of that annoying division, given that you are working with modular arithmetic.

    I think that's the problem!

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

      That changes the result but is still not giving the right answer for the 21st test

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

        I mean, you have to make the division, but not there!

        Given that you are working with (MOD — 1) for the exponent, the division result will be (in most of the cases) incorrect.

        Hint: If z is an even number, and z = (a0 + 1) * (a1 + 1) * ... * (ap + 1), then there must be at least one (ai + 1) that is even.

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

          After long, long, long revisions to my code, I finally managed to finish the problem, even if I'm not very clear about this modular arithmetic. Thanks!

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

            I am getting same problem as yours..Can you tell me what did you do to remove WA in tc 21?

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

              (f*k)/2 this code right here, you divide it by 2 but if you work modulo and in your f variable will be an even number, you will have at least one ( it->second + 1 ) in your map which is even and you should divide it by 2 when f will be even. If you still can`t figure it out look at my hode here: http://codeforces.com/contest/615/submission/15262138

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

For those who haven't noticed : Link to Editorial

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

    The explanation for the C problem is still the best explanation I've heard yet.

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

    How could we notice it? Was it published anywhere else?

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

My rating didn't change, although I was not disqualified. I want to know the reason.

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

What color has zhangzj_is_our_sun?
In div2 winners he is gray, in his profile he is red/purple
3-colored man?)

And yes, I found a little bug with these colors. When I clicked 'preview', his handle was red, but you see a gray handle in this comment. MikeMirzayanov, fix please.

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

    His magic color was Newbie before the contest afaik.

    His current magic colour is Red.

    His current actual color is Purple

    Maybe the standings show the color the person had before the contest (which includes magic color)

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

What happened to the editorial post? It seems gone :(

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

Editorial link is not working.

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

Please activate the editorial link. It does not seem to be working. Without editorial there is nothing to learn from a contest.

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

Editorial link is now working again :) Thanks

http://codeforces.com/blog/entry/22658