Hasan0540's blog

Codeforces Round #480 (Div. 2)
By Hasan0540, 7 years ago, In English

Hello everyone!

I would like to invite you to participate in Codeforces Round 480 (Div. 2), it will take place tomorrow, May/08/2018 18:05 (Moscow time).

The round consists of 6 problems and you will have two hours to solve them.

The problems were prepared by me with great help from linkinu and Reem. I would like to thank KAN for his great efforts in reviewing the problems and for his suggestions, it is really amazing to see the work done behind every round. Also thanks to Tommyr7, Livace and mike_live for testing the problems, and to arsor for translating the statements into Russian.

This is my first round on Codeforces, I hope that you will find some interesting problems for you.

Note that the round is rated for everyone with rating below 2100.

Good luck and have fun!

UPD: Congratulations to the winners:

Div. 2:

  1. phongthan

  2. allllekssssa

  3. veterfrank

  4. lagin

  5. Fekete

Div. 1+2:

  1. eddy1021

  2. phongthan

  3. Andreikkaa

  4. step_by_step

  5. cerberus97

UPD1: Editorial

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

Comments Comments (210)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

rated for div.3 too?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -21 Vote: I do not like it

...

→ Reply
»
7 years ago, # |
  Vote: I like it +43 Vote: I do not like it

I am expecting some really interesting round, Hasan0540 is one of the best problem setters from the Arab region, I always enjoyed your problems in ACM contests :D

→ Reply
»
7 years ago, # |
  Vote: I like it +26 Vote: I do not like it

I hope to see a realy nice contest from our Jordanian programmer Hasan0540. ❤

→ Reply
»
7 years ago, # |
  Vote: I like it +130 Vote: I do not like it

We've implemented a special tag [contest_time:contestId]. It shows a contest start time in a correct timezone (as a link to timeanddate.com). Please, use it in announcements as Hasan0540 did.

→ Reply
»
7 years ago, # |
  Vote: I like it +74 Vote: I do not like it

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I only noticed that in the russian description only thing in russian is the date :)

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Are these problems in English or Russian?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope will be Short Statements

→ Reply
»
7 years ago, # |
  Vote: I like it +280 Vote: I do not like it

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

    I have final exam too :'(

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

    One Can join the course in the summer course and get grades, But can't join the contest in the virtual participation and get rate .... sorry final :D

    → Reply
»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

WOW!! Three Arab rounds in one month

Codeforces Round 473 (Div. 2)--Codeforces Round 478 (Div. 2) -- Codeforces Round 480 (Div. 2)

We are invading CF :D

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

    if u guys invade codeforces then americans (led by George Bush) will come to cf and look for oil. watch out my dood

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

      Iraq 2003 _ Codeforces 2018

      R.I.P Codeforces

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a question: when we'll have a div1 and a div2 contest in the same time, those under 2100 can participate in both rounds or is forbidden for them to join div2?

→ Reply
»
7 years ago, # |
  Vote: I like it +32 Vote: I do not like it

you forgot to say thanks for MikeMirzayanov for the great Codeforces and Polygon platforms.

→ Reply
»
7 years ago, # |
  Vote: I like it -9 Vote: I do not like it

I hope this contest will make me green once again

→ Reply
»
7 years ago, # |
  Vote: I like it -46 Vote: I do not like it

Time to use my alt account!

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

All the best Hasan0540 for your first round! May it be interesting and great for everyone! cheers!

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

It's time to decrease my rating again....

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why B has no spj?

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

    What's spj ? I have seen people mentioning spj before too.

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

      Special Judge.

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

        Can you please elaborate on it. Thanks.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 5   Vote: I like it 0 Vote: I do not like it

          Such as the test case in problem B, if this problem is SPJ(actually it's not):

          The input is 7 7, 
so one of valid answers is:
.......
.#####.
.#...#.
.......

the another one is:
.......
.###...
.###.#.
.......

and the another one is:
.......
.###.#.
.###...
.......

.etc.

          Your output can be anyone of the above, and the verdict result always is Accepted, instead of Wrong Answer.

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

          Generally, if the problem is SPJ, the writer will explain it.

          → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    I think so. Such test case is WA.

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

I positively registered for this contest but now when I am trying to submit the solution, it says I can't do it because I am not registered. Anyone has any ideas who should I contact?

→ Reply
»
7 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Stupid problem selection.This problem set should be for DIV1.Not for typical div2 and div3 people.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it -21 Vote: I do not like it

    1) If these problems were chosen for Div.1 it will be so easy for them.

    2) Hard problems are the best way to practice.

    3) If you were effected by the problems, it is not the end of the world.

    → Reply
»
7 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Can anyone translate problem D? I really try understand... but fail.

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

Oh my rating!!! They will be in a lot of trouble after this round. A really bad contest for me.

→ Reply
»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

so difficult to understand problem statements...

→ Reply
»
7 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Really? It seems to me that C easier than B

→ Reply
»
7 years ago, # |
← Rev. 5   Vote: I like it +16 Vote: I do not like it

I can't understand the problem statement properly for problem B and problem C. Either my English skill is not good or the problem statements was poor.

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

    I guess problem statements were alright. Yeah for C i would say maximum part was unnecessary but you could easily decipher it seeing sample cases.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

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

    The real question is: How to read problem D?

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

    Let b[i] be the product of primes with odd exponent in a[i]. Then the minimum number of groups is the number of distinct elements in b

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

    Given a subarray:

    1- Every pair of integers that are not 0 will be part of the same group if and only if the set of primes with odd exponent is the same for both numbers (when you write numbers as a product of prime numbers)

    2- Every 0 can be part of any group.

    Then you can pre-group the numbers and after that you just calculate the answer for every subarray.

    My submission

    → Reply
»
7 years ago, # |
  Vote: I like it +66 Vote: I do not like it

Hasan0540 Next time please make statements easy to understand.

→ Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Any idea of test 7 of E?

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

    I forgot to update height values for sons of ancestors.

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

    Something like: 10 5 9 6 8 4 3 4 10 9 4 5 4 10 3 2 1 5 5 7

    (sorry for the big test, I was stresstesting). The answer is 1 2 3 5 7, my code(WA7) prints 1 2 3 6 7

    Maybe that's your case

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      yup 12367 it prints for me too.. Ok why would it print 5. 5 is connected to 7 also even after deletion of 1 and 2?

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

        Well, considering you are already aware that you have to remove 7, you can remove 5 instead of 6, because after 7 and 1 removal, 5 is free to go.

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

Nice problems(though harder version of D was on some round before).

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I don't understand problem C: 5 2 0 2 1 255 254 For this test case in problem C, wouldn't lexicographically smallest array be 0 1 0 254 254 (0 and 1 are grouped for key 0) instead of what is shown as the test case 0 1 1 254 254?

Thanks for any help

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

    If you group 0 and 1, 2 will belong to other group and say key will be 2 or more. Thus you will get 0 2 0 254 254 which is not desirable!

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

      Oh okay, got it, I completely misunderstood the question. Thanks

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

    No. Because you have assumed 2 drops down to 1. So [1,2] is the maximum set that can be paired to 1. You can't include 0 in it as k==2.

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

    According to you, 0 and 1 are grouped for key 0. But then, 2 can be grouped only to itself, as the maximum size of any group is 2, so 2 cannot be grouped with the group [0, 1].

    This will result in the array : 0 2 0 254 254.

    → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

OMG.
~~~~~
long long b = ...;
long long a = sqrt(b);
if (a * a == b)
{
//b if square
}
~~~~~

This works just fine on Codeforces but fails on my computer, so I failed my hack. Gosh. Now I know more about CF.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

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

    Am i correct that this is greedy? First we take vertex n, than try to take n — 1. If we can take number of vertex between n and n — 1 we take it else try to take n — 2 and same algorithm next.

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

      Yes, because 2^x=2^(x-1)+2^(x-2)+...+2^0 + 1.

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

        Fine, how to make fast realization?

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

      I solved it like that. I had to optimize lca to O(1) to prevent tle ...

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

        Can you tell me your solution?

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

        You can think of it as "keeping" vertices. So first you keep vertex n, then you try to keep vertex n-1, then n-2 etc. (To keep a vertex i, you need to keep every vertex on the path from n to i)

        We realize that we keep at most n vertices. Thus, every time we keep a vertex, we can mark it as kept. Now we want to know the first ancestor of vertex i that is already kept (this tells us how many more vertices we need to keep along the way in order to keep vertex i).

        We can use parent doubling to check this in O(lg N), so I don't see why we need O(1) LCA here.

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

          I solved it as follows: given a tree T and a vertex u, we have to find the vertex v in T that maximizes the depth of lca(u,v). Note that a solution for v is one of the leafs that is next to u (left or right) in dfs-order. Mine is also Nlog(N), so I was surprised when I got TLE

          → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          meeeep Can u give any link to learn about the "parent doubling" that u used? One more thing why cant we proceed in this way:- remove the smallest weight leaf from the tree and repeat the same on the new tree until we remove k nodes which could be seen as minimizing the number of fans that we lose by removing a node?

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

            why cant we proceed in this way

            Consider this tree:

            3 — 1 — 4 — 2

            where k = 2. If we do it your way, we'll remove 2 (our leaves are 2 and 3) and then 3 (leaves are 3 and 4). But the correct answer should be removing 3 and 1

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

            I don't know a link, but it should be pretty simple to explain (hopefully).

            For each node, you store your 2^i-th parent for each integer i. (A convenient initialization for this question is that the parent of the root is itself).

            We initialize the 2^0-th (i.e. direct parent) manually. For each i>1, we notice that the 2^i-th parent is just the 2^(i-1)-th parent of the 2^(i-1)-th parent, so we may find this is constant time... assuming we have already computed the parents of its 2^(i-1)-th parent. This means that we want to compute parents in some kind of pre-order DFS, which can be written together with the DFS that roots the tree.

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

              I think that is termed as "finding LCA using sparse table". OK thanks I'll look into that and learn it.

              meeeep U used that parent doubling to find the lowest ancestor who has been marked as "kept" right ?

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

    Because

    2i > (2(i - 1) + 2(i - 2) + ...)

    , process the cities from greatest to least and greedily take them. First, root the tree at the largest value (you always take it). Then to see if you can take city $x$, see how many cities you haven't taken that are on the path from x to the root. If you can take all of them, do so, otherwise ignore this city.

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

hacks for D?

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

    I can only guess that some people (like stupid me) used if instead of while when eliminating square divisors.

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

      Omg that's exactly what I did
      We're not alone XD

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I lost a time because in problem E k supposed to be less than n. When I added if n == k print(all) it passed.

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

Trying to do the C problem...

→ Reply
»
7 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Please guarantee there are at least one perl on A...

I heard the announce after my first submit, so I lost 50pts...

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

    They shouldn't need to guarantee extra things just because you missed an edge case :/

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

      Do you think the necklace that has no perls is really necklace? And when I noticed the edge, I didn't know the answer for ---- is YES or NO.

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

        Do you think the necklace that has no perls is really necklace?

        To keep up the pettiness, according to Oxford dictionary, the definition of a necklace is "an ornamental chain or string of beads, jewels, or links worn round the neck."

        So yes.

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

      Actually, I think it's bad to not write constraints. In our time good manners for problemsetting is one simple rule: if a lot of contestant can misunderstood the statement, it's a bad statement.

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

        A lot of contestants can misunderstand the statement and a lot of contestants can easily overlook an edge case are different things.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Actually the same, when you didn't specify what is the edge case. A lot of people thought it's guaranteed there are at least one perl.

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

            There is a sample case with no links so why would it need to have at least one pearl? I would be much more worried about my necklace having no links to hold it together, rather than no pearls.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
              ← Rev. 2   Vote: I like it -15 Vote: I do not like it

              You see: it's not about how YOU see the problem. It's about how does others see it. For you it may be obvious that it can be zero pearls. For me too. But it can be not obvious for others, and that's ok, all people are different and have different points of view. What's why you need to specify such things as constraints, so it will be obvious for anyone.

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

Statement for C is hard to understand, and B is a bit hard for a Div2-B. But overall, today's problemset is nice (especially E).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A pretest is wayyyyy to soft

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

I realized that in the D is necessary to consider the cases where there is a 0 in the range, but didn't corrected my code correctly, wasted a big chance :(

→ Reply
»
7 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Seemed like Problem D's time limit a little bit too strict?

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

    I had that problem too, is the intended time complexity less than Θ(n^2+n*sqrt(10^8))?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Not really sure. My solution has the time complexity you mentioned.

      I was trying to reduce the constant factor that might cause the TLE, but guess I didn't have enough time to come up with an elegant one.

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

      I don't really sure, but, I think, any complicate data structure (set, hashset/unordered_set) will get TL and we need to use bool array instead of them (after renumber of all numbers in handled massive, like [16127, 1046527, 16769023, 1046527, 1046527, 16127] -> [1, 2, 3, 2, 2, 1]).

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

        This is exactly what I was thinking. I was trying to implement such, but since I thought about that too late, I couldn't submit my solution.

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I didn't lock my solution and I got hacked HOW!!!!! here

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

    Locking grants you the rights to hack others, not protects you from being hacked.

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

    You should be happy for being hacked since you got a second chance. Otherwise you would've just gotten "Wrong answer on test xx" without even knowing that your solution was wrong.

    → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you make the number of links between every two adjacent pearls equal? And there is some test for only 1 pearl and even "No" pearl ???

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it -39 Vote: I do not like it

Hasan0540 why you are so strict at dataset for problem F!!!

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

    May be because the intended solution was not a simple BFS?

    → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I could not make out D. Can someone make me understand what the problem statement meant?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

any on got WA test 5 in the problem B then got AC ?

any test case ?

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

rip my rate

oh wait it's already bad

→ Reply
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

it is rated or yes?)))

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    I hope it's UR or Semi-Rated,but Unfortunately, here is Codeforces so it's maybe Rated...

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do B? I thought to create symmetric parts on the innner matrix. Any suggestion?

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

    Yeah symmetric inner matrix.You have 3 cases to consider. Let me assume n=7.

    if k is even say 4:
    .......
    .##....
    .##....
    .......

    if k is odd and <=(n-2) say 3:
    .......
    ..###..
    .......
    .......

    if k is odd and >=(n-2) say 7:
    .......
    .#####.
    .#...#.
    .......

    How did i come up with this? Well i had made a checker that gives no of ways to reach in shortest path from 1,1 and 4,1 for a given grid and used a bit of symmetry and observations to conclude this.

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

      2nd and 3rd cases can be understood as inversions of each other. Look at antipr000's examples: inner matrix of 2nd case is inverse of inner matrix of the 3rd case. So if we have k ≥ n - 2, then we can assign k to (n - 2) * 2 - k and make inversion after (perl code — 38050716).

      → Reply
»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

My first hack on problem A (38026095)

Seriously I don't know how that passed the pretests...

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the problems are really nice.But I spent some time hacking ,and have no time to write out problem E.So sad.

→ Reply
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I could not make out D. Can someone make me understand what the problem statement meant?

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

    Same question. why is the answer to array [5] is 1???

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

      You separate [5] into the set(5). Now since there are no pairs of numbers in this group, the product of any pair is a perfect square (vacuously true). there is only 1 set, so the ans is 1

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Consider the test case [5 2 8]. There are 6 sub arrays. For each, we want to separate it into as few groups such that product any pair of elements in any group is a perfect square. For this example, the groups are

    [5 2 8] -> (5) (2 8)

    [5 2] -> (5) (2)

    [2 8] -> (2 8)

    [5] -> (5)

    [2] -> (2)

    [8] -> (8)

    Now, since 4 of them sep into 1 group, and 2 sep into 2 groups, the ans is

    4 2 0

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem C?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I still couldn't understand C. I think I need to improve my English skills first :(

    → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Stupid cases of 0's in D. These puzzling cases aren't fair :/

→ Reply
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Is it just Me who think that problem B became harder than C just because of the statement? XD just want to know everyone's views!

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

    Yes C was ofcourse easy. B was harder than C because there were 3 independent cases to tackle and needed good observation or otherwise tricks like generating no of paths for smaller datasets and observing patterns

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

      I disagree. My thought process was just "you can reverse the ending/start so it's just number of paths between the diagonals. If the grid is symmetric then the answer is the same". For problem C I struggled to understand what it asked until looking at the samples.

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

      3 independent cases? I handled only 2 independent cases

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

        In my approach i had to handle cases of: k=even, k=odd and <=(n-2) and k=odd and >(n-2)

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I handled: k = 2 * (n - 2) and k < 2 * (n - 2)

          But know i even now how to handle even one case

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

            Can you explain your approach a bit?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
              ← Rev. 2   Vote: I like it +3 Vote: I do not like it

              If k = 2 * (n - 2) then it is obvious.

              Else just put hotels in pairs symmetriсally the middle vertical, and if k is odd, just put the last hotel on it.

              → Reply
»
7 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Clarification on A was so unfair, for people, who already failed on this case, and got minus points

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    i also deal with this and the jury said "It is clear from the statements." , i hope it's unrated. this contest is worst

    → Reply
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

D in a nutshell.

→ Reply
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

tfw when you forgot to handle negative numbers in d.

→ Reply
»
7 years ago, # |
  Vote: I like it +53 Vote: I do not like it

I think, 2 hours are too few for this contest (a lot of cases, a lot of thinking, a lot of text understanding). It would be better to have 2.5 or 3 hours of solving time.

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

    I agree. I think some participants could solve F if they had another one hour.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -92 Vote: I do not like it

I didn't really like this contest

→ Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

D is really hell. I've spent a lot of time to read and understand it. There is no any example explanation like in other problems.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A could really use some constraints on perl/links numbers and D's statement was so bad.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats test 20 in D?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When writing code for problem A, I know that I have to wait for the statement update to handle the case of 0 pearls. I took me few more minutes. I don't know how 1500 solvers before me manage this case.

→ Reply
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Can anyone please give me the proof for problem B's solution?

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

    Observe symmetry. Let me explain in cases:

    if k is even:
    We put 2 #'s in grid[1] and grid[2] as long as needed. Why this works?
    Well see symmetry with respect to (1,1) and (4,1) one can easily tell that no of paths will be same.
    .....
    .#...
    .#...
    .....

    Now for k odd and <=(n-2):

    Here observe symmetry of (1,1) and (1,n-1) ; (4,1) and (4,n-1).

    .....
    ..#..
    .....
    .....

    And for k odd and >(n-2) number of paths is always 2.

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

      So for the last case — odd k and k>(n-2), I can place the hotels anywhere?

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

        No. Place them like this

        .......
        .#####.
        .#...#.
        .......
        see you blocked all ways and only 2 left.

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

          Yeah, thats what I did but since you said that it would always be 2, I got confused :p

          Thanks for the help :)

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

            oh sorry my bad. yeah you have to block such that its 2. xD

            → Reply
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Write winners, write winners, I want to see my name :D

For me contest was really nice with cool tasks :) I thought that I will never say this sentence, but maybe texts could be a little longer.

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone explain the problem statement for D ?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

PROBLEM B: for input 9 5 why YES

.........

.##.#....

..#.#....

.........

isn't an answer?

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

    You can understand why it is not correct answer by thinking on simplified but similar case:

    5 5
.....
.#?#.
..##.
.....

    (question mark means doesn't matter)

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    (1,1) -> (4,9) 23patterns

    (4,1) -> (1,9) 22patterns

    YES ......... ..#####.. ......... ......... is one of the answer

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it +1 Vote: I do not like it

    While other paths are symmetric, there's one exception. For the one that starts from the upper side and first goes down,

    A........
A##.#....
AA#.#....
.AAAAAAAA

    and

    A........
A##.#....
A.#.#....
AAAAAAAAA

    are both possible, while for the opposite side, only

    AAAAAAAAA
A##.#....
A.#.#....
A........

    is possible.

    edit: Thanks rsFalse!

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

      Use block formatting it gives monospace font.

      → Reply
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Problem B

Based on intuition : easy

Based on Proof : hard

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

    If the matrix is perfectly symmetric you don't need to count the number of paths to know they are they same number. They are literally the same paths, no need for more proof.

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

    ways (1,1) -> (4,n) is equal to ways (4,n) -> (1,1)

    If answer table is symmetry, number of ways from (4,n) -> (1,1) equals (4,1) -> (1,n) (because of symmetry)

    (symmetry through (n+1)/2 like this

    00000!00000

    00#00#00#00

    0#00#!#00#0

    00000!00000 )

    proof doesn't look hard

    → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Wow, exactly 50 users became Master according to new rules!

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

Wow, I've become so numb orange, but now it is not so cool

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

    For me it is cool , orange is orange :D

    But someone should investigate is everything fine with rating, for me it looks jumps are a little bigger than expected.

    → Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

while I had a very bad contest but the problems was so beautiful. thanks for that Hasan0540.

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What is case 18 in problem D. I keep getting WA.

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

    I also had WA 18 0 * (ANY NUMBER) = 0 — square also 0%(j*j)==0 (this should help)

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

      Thanks!
      It was unclear whether 0 is perfect square or not while I was competing!

      → Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can anyone explain me problem C ? I read at least 10 times, still find hard to understand.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    7 3

    0.4.1.7.6.11.8 ______________________ 0.1 | 2.3.4 | 5.6.7 | 8 | 9.10.11 | 12.13 ....

    ^ The answer is: 0 2 0 5 5 9 8.

    → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Could someone please explain the symmetric approach used to solve B? I can't understand how to think in the correct direction.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Please see my other reply above. The key, for me, was observing that many shortest paths cross in the middle of the grid, and must be symmetrical. For example

    ....X XX...        ....X XXXXX
...XX .XX..        ....X ....X
.XXX. ..XXX   or   ....X ....X
XX... ....X        XXXXX ....X

    To keep or remove the same number of "diagonal" paths from both sources, you have to place hotels with horizontal symmetry, leaving a hole in the middle column if they are even, or putting one in the middle column too, if they are odd.

    Hope this makes sense!

    (edit: fixed drawing of "diagonal" paths)

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

      It is easier to place hotels with vertical symmetry

      → Reply
»
7 years ago, # |
  Vote: I like it +59 Vote: I do not like it

For those who are curious how the color distributions are changed due to the update of upper bound of the rating on "Div.2 Only" rounds. Please be informed that this describes top 2000 contestants for each round:

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

    Hey good job. Can you brief in 1-2 lines rhat what can we conclude from.this data? Seems to me like it says more about the level of the specific rounds rather than the updated rating system. Please enlighten me :)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      If I understand your question, I believe Codeforces #480 was the first "Div. 2 Only Round" that contestants in purple participated. In other words, purple lines described here hadn't appeared in any previous rounds! :)

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

        For your reference, here's 6 rounds version of it :)

        → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
  • Pretest passed on D at 01:47
  • Immediately locked all problems and started hacking
  • 3 minutes later found silly mistake in my submission of D (before looking at other people's solutions)
  • Shouted "fxxk"
  • Turned out that SO MANY people FSTed on D that I still got +17 rating (should have got about +60 if I made D right)
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I came up with a solution for D that is something like this:

We add bidirectional edges between pair of nodes i to j if ai·aj is a perfect square. My first observation was, every connected component is a complete graph. Let, bi be the binary string consisting the parity of powers of primes of ai. Then if i and j are connected and j and k are connected, then i and k are also connected. Because, i and j connected means — (1), again, j and k connected means — (2). Combining (1) and (2), we get , means i and k have an edge. This gives us enough material to prove that all connected components are complete graph.

Now, the problem reduces to finding the number of connected component of the sub-graph consisting only edges in a range, i.e. in [l;r] (1 ≤ l ≤ r ≤ n).

To do this, I implemented this using the following way:

We first select sub-array's starting point, let's say i(actually we also iterate this from left to right), then iterate on the ending point from left to right (denote it also with j). When extending one node to the right (means, we are going from j to j + 1) we need to only know if j + 1 connects to any of the node in range [i, j]. If it does, then number of connected component remains same, increases by 1 otherwise. As we don't care about the edges connecting with a node left to i, we may delete them on the go i.e. when we move the left end point one step right, i to i + 1, we delete all the edges that are connecting node i and another node with index greater than i. Another observation is that, when we are trying to find if the new node j + 1 can be connected with any component, we need not to check all the edges as all the edges lead to the same component. Instead of keeping all the edges we will keep the edge which connects j + 1 with the closest node left to j + 1. More formally-

For each i (1 ≤ i ≤ n), maximum j < i such that there is an edge between i and j, if there is none then it's simply  - 1. Again a set for each i, .

Now, the pseudo code seems something like this-

for i in range 1 to n :
    c := 0
    for j in range i to n :
        if back[j] = -1 then :
            c := c + 1
        cnt[c] := cnt[c] + 1
    for j in to(i) :
        back[j] := -1

Where is the answer array.

But I got Wrong Answer on test 18. Submission

Can anyone check and tell what's wrong here?

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

    if i and j are connected and j and k are connected, then i and k are also connected.

    This doesn't hold when a[j] is equal to 0, like in this case.

    3 10 0 7

    → Reply