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

Автор TheWishmaster, 4 года назад, По-русски,

Всем привет!

Уже завтра состоится Codeforces Round #338 (Div. 2). Обратите внимание на необычное время проведения контеста! Раунд для вас готовили Максим Винниченко (maxkvant) и я, Александр Зойкин. Это наш первый раунд, очень надеемся, что все пройдет хорошо. Огромное спасибо GlebsHP за неоценимую помощь в подготовке контеста, Bobrosoft за тестирование и не только, Delinur за перевод условий на английский язык и, разумеется, MikeMirzayanov за системы Codeforces и Polygon.

разбалловка 500 — 12501750 — 2000 — 2500

Всем удачи на контесте!

upd Поздравляем победителей!

div 2:

zhangzj_is_our_sun

MWaltz

Claris

ucfpt

Tomer.Adar

div 1:

I_love_Tanya_Romanova

tutanjokersharp

sd0061

pavel.savchenkov

ershov.stanislav

Разбор

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

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

Для 2016-го года это тоже первый раунд =)

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

Для авторов первый контест, для нас тоже первый в этом году :) Желаю всем удачного начала!!!

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

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. :-|

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приятно видеть короткий блог :)

Всем удачи на первом контесте за 2016 год!

P.S. Маленькая ошибка -> Раунд для все.

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

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

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

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

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

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

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

Should be called hello 2016...

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

hope it will be good first round for you guys

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

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

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

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

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

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

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

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?

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

    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

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

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

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

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

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

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

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

        Who cares? we can be legendary one day. This is just self satisfaction for us to become the real one :)

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

Maybe the contest can be earlier. I can start the contest after dinner. XDD

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

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 :)

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

orzdyh orzjc orztourist orzWJMZBMR ORZ TooDifficult 23333333

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

Score distribution pls?

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

hope good rating this time

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

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

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

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

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

    there's always the 'Virtual Participation' way :)

    In the words of cf itself, "Virtual contest is a way to take part in past contest, as close as possible to participation on time. "

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

Hey in the second problem what is 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?

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

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

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

    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.

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

      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.

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

      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

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

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

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

    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?

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

      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

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

        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".

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

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.

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

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

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

      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

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

        You just nailed it!!!

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

          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

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

            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.

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

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

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

              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.

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

      its like Uva 10182.
      i use many for loop to simulate.
      this round want us to find the pattern :(

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

      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 :)

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

        Well, got WA on #103 :)

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

          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.

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

    Why problem E problem E?

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

    For me, C was easier than B, even though I didn't pass all the pretests. I couldn't figure out B.

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

    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 -_-

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

How to solve B?

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

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

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

    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).

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

    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])

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

    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.

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

      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.

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

      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;

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

        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

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

          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

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

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

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

Не мог взломать участника. Отправляю контр-тест -> получаю ответ, мол посылка уже взломана. Обновляю страницу комнаты — посылка участника все еще висит(так и провисела до конца контеста). У меня у одного такое было ?

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

Extremely weak pretests in D killed me today :(

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

What is the hack test for problem D!?

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

    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

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

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

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

        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.

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

        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)

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

      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

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

      I took MOD -2 :(

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

Обида, не хватило 5 минут отдебажить C и решить все задачи =\

Справедливости ради, задачки сегодня были очень простые.

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

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

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

Hmmm what's wrong with the code here?

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

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

How to solve D??

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

    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.

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

    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.

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

    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).

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

    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.

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

      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?

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

        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.

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

          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?

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

            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.

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

      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

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

        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.

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

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

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

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?

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

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

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

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

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

Кто-нибудь может объяcнить решение B? Хотя бы общий алгоритм, что ли..

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

    Я пока не знаю, прошло ли моё решение, поэтому пока просто сделаю набросок словами.

    Будем перебирать в цикле все вершины (вообще все). Каждую вершину мы считаем за начало хвоста. Дальше мы удлиняем хвост с помощью dfs до тех пор, пока есть смежная вершина с номером больше текущего.
    После каждого удлинения на одну вершину, мы смотрим количество ВСЕХ смежных вершин с текущим концом хвоста. Это количество смежных вершин — все иголки ёжика. Умножаем количество иголок в данный момент времени, на размер текущего хвоста и сравниваем с лучшим результатом, который мы когда-либо достигали.

    Если мой подход пройдёт и никто не сделает более менее красивого описания этого решения, я сделаю более подробный комментарий с картинками =)

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

      Вот один в один как Вы сказали, получил TL на взломе, так же как и Вы на системных тестах только что( http://codeforces.com/contest/615/submission/15254540

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

        Да, я тоже в пролёте :)
        Ничего страшного, зато я изучу и отпрактикую новую для себя концепцию. Видимо концепция dfs сидит в моей голове крепче, чем то, что требуется в этой задаче.

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

          Легко решается динамическим программированием, и я получил-бы AC, если бы записывал результат в long long. Вот работающий код http://codeforces.com/contest/615/submission/15255627

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

            Если бы я совершенно НЕ знал теории графов, то шансов решить эту задачу было бы намного больше. Вот такой вот абсурд — DFS было первое, что пришло в голову — а тут оно еще и претесты прошло

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

              Эта штука, которую ты сейчас описал, в психологии называется Einstellung Effect. Я вот сейчас сижу и размышляю — задачу я не решил, но я стал сильнее в психологии :)

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

    Это задача на динамическое программирование (очень простая). Перебираешь вершины от 1 до n и смотришь, какой самый длинный хвост оканчивается в текущей вершине. А в ответ идёт максимум из степени вершины помноженную на длину хвоста.

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

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

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

    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

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

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

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

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?

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

    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

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

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

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

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

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

    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.

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

    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 :)

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

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 :)

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

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

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

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

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

    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.

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

Когда-нибудь наступит тот день, что я перестану в div1 проверять все решения в комнате в поисках очевиднейшего переполнения... Хотя на это уходит всего минут 5, но всё же...

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

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....

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

    I did n^2 log n but got WA on pretest 15, so I don't really know about that...

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

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

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

    Same here :(

    BTW: wasn't the time limit = 1.5sec

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

    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.

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

      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)

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

      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 :(

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

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

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

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

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

          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... ?

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

    my N^2 DP approach got stack overflow :D

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

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

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

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.

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

Problem E saved some people :)

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

Первый в 2016 году раунд на Codeforces, вне всяких сомнений, удался :)

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

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

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

link Can someone help me?

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

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

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

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

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

    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

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

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

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

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 :(

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

Можете объяснить почему RE на 4 тесте в задаче D? Если это переполнение типа, то как оптимально брать по модулю? Заранее спасибо!

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

    Как минимум, вот эта строка некорректна: n *= x;

    Произведение введенных простых может быть очень большим.

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

Ratings updated

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

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

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

Скажите, почему в D при нечетном количестве делителей работает:

((число % MOD)((количество делителей % Phi(MOD)) / 2) % Phi(MOD) * (корень числа % MOD)) % MOD

где "/ 2" -- обычное деление с отбрасыванием остатка.

Смущает то, что в кольце Phi(MOD) существуют два числа, умножение которых на 2 даст количество делителей минус один:

  • количество делителей % Phi(MOD) / 2
  • (количество делителей % Phi(MOD) / 2 + Phi(MOD) / 2) % Phi(MOD).

Код: 15255053

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

Кто может пояснить почему при выводе переменной ans через cout все выводится нормально, а при выводе через printf выводится пустота? (202 и 203 строки)

http://paste.ubuntu.com/14439109/

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

    ll — неправильный спецификатор формата для long long. Попробуй lld.

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

      Спасибо, при запуске все правильно отрабатывает, но при отсылке файла выдается

      "Пожалуйста, не используйте спецификатор %lld (или подобные) для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d."

      Почему так?

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

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.

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

Разбор будет?

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

    Да будет наверное как обычно. Codeforces хороший сайт и здесь на все задачи разборы есть ^_^

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

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

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

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?

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

    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! ^_^

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

    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.

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

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    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.

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

      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.

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

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

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

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

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

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

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

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

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

Masha ruined my day .... :(
(failed to get what she want as she is a small girl :/ )

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

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

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

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

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

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

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

Masha ruined my day :(
(after all she is a small girl :/ )

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

Так почему были изменены ограничения в задаче С по времени и длине строк, да еще и не было оповещения? Это косяк, вообще-то

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

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.

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

    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.)

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

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

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

Why this submission is TLE? Click

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

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

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

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

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

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).

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

Can the problem B be solved using only dfs?

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

    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.

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

    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

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

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.

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

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

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

    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.

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

      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 ?

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

        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.

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

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

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

Когда разбор?

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

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.

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

    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;
    ?

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

    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

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

      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

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

        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 :/

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

    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.

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

Tutorial?

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

    according to this comment

    solutions for problems mentioned in comments!!!

    you have to read all comments to see solutions

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

There is some problem with some users colors.

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

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

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

When will the tutorials be translated?!

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

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

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

    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!

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

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

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

        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.

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

          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!

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

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

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

              (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

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

Кто-нибудь может поподробнее объяснить проблему D? Пожалуйста!

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

For those who haven't noticed : Link to Editorial

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

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

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

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.

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

    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)

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