Hasan0540's blog

By Hasan0540, 3 weeks 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 1am. 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  

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

rated for div.3 too?

»
3 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

I hope this contest will make me green once again...!!!!

»
3 weeks 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

»
3 weeks 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. ❤

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +74 Vote: I do not like it

»
3 weeks 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 :)

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

Are these problems in English or Russian?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope will be Short Statements

»
3 weeks ago, # |
  Vote: I like it +280 Vote: I do not like it

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

    I have final exam too :'(

  • »
    »
    3 weeks 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

»
3 weeks 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

  • »
    »
    3 weeks 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

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

      Iraq 2003 _ Codeforces 2018

      R.I.P Codeforces

»
3 weeks 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?

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

I hope this contest will make me green once again

»
3 weeks ago, # |
  Vote: I like it -47 Vote: I do not like it

Time to use my alt account!

»
3 weeks 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!

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Why B has no spj?

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

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

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

      Special Judge.

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

        Can you please elaborate on it. Thanks.

        • »
          »
          »
          »
          »
          2 weeks 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.

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

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

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

    I think so. Such test case is WA.

    7 7
    .......
    .###...
    .###.#.
    .......
    
»
3 weeks 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?

»
3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

so difficult to understand problem statements...

»
3 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

Really? It seems to me that C easier than B

»
3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

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

    The real question is: How to read problem D?

  • »
    »
    3 weeks 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

  • »
    »
    3 weeks 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

»
3 weeks ago, # |
  Vote: I like it +66 Vote: I do not like it

Hasan0540 Next time please make statements easy to understand.

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Any idea of test 7 of E?

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

    I forgot to update height values for sons of ancestors.

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        3 weeks 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.

»
3 weeks 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).

»
3 weeks 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

  • »
    »
    3 weeks 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!

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

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

  • »
    »
    3 weeks 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.

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

    If 0 and 1 are assigned for group 0. Then it turns out that (2 and 3)_ can be assigned to one group with smallest unique key as 2.

    So according to this the o/p is ( 0 2 0 254 254) which is lexicographically greater than 0 1 1 254 254

  • »
    »
    3 weeks 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.

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

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

        Fine, how to make fast realization?

    • »
      »
      »
      3 weeks 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 ...

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

        Can you tell me your solution?

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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

        • »
          »
          »
          »
          »
          3 weeks 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?

          • »
            »
            »
            »
            »
            »
            3 weeks 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

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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 ?

  • »
    »
    3 weeks 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.

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

hacks for D?

  • »
    »
    3 weeks 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.

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

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

»
3 weeks 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.

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

Trying to do the C problem...

»
3 weeks 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...

  • »
    »
    3 weeks 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 :/

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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.

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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.

»
3 weeks 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).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A pretest is wayyyyy to soft

»
3 weeks 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 :(

»
3 weeks ago, # |
  Vote: I like it +50 Vote: I do not like it

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

  • »
    »
    3 weeks 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))?

    • »
      »
      »
      3 weeks 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.

    • »
      »
      »
      3 weeks 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]).

      • »
        »
        »
        »
        3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks 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 ???

»
3 weeks 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!!!

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

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

»
3 weeks 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?

»
3 weeks 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 ?

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

rip my rate

oh wait it's already bad

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

it is rated or yes?)))

  • »
    »
    3 weeks 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...

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    Mike, please, do it unrated, you ruined my rating

»
3 weeks 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?

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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 soham_1234'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).

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

        So bad I also thought about that solution but cannot prove it.Now that I implemented that successfully. So pity.

»
3 weeks 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...

»
3 weeks 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.

»
3 weeks 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?

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

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

    • »
      »
      »
      3 weeks 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

  • »
    »
    3 weeks 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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem C?

  • »
    »
    3 weeks 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 :(

»
3 weeks 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 :/

»
3 weeks 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!

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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.

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

      3 independent cases? I handled only 2 independent cases

      • »
        »
        »
        »
        3 weeks 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)

        • »
          »
          »
          »
          »
          3 weeks 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

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

            Can you explain your approach a bit?

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks 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

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

      But it was clear from the statements...

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

D in a nutshell.

»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

tfw when you forgot to handle negative numbers in d.

»
3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -92 Vote: I do not like it

I hope we won't see any contests made by this author anymore.

»
3 weeks 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.

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats test 20 in D?

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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 :)

          • »
            »
            »
            »
            »
            »
            3 weeks 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

»
3 weeks 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.

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

Can someone explain the problem statement for D ?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B Can you help the mayor place the hotels in a way such that there are equal number of shortest paths from each village to its preferred pond? But they are counting all paths.Please,be more clear about the problem statement. Thank you

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

    shortest paths is the keyword.

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

      wrong answer The number of paths between opposite corners doesn't match: 2 and 3 They are counting all paths so shortest paths is the wrong keyword which caused a lot of problems I believe.

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

        The problem is correctly asking for shortest paths. Remember this is distance in taxicab geometry, so in a 4*n grid, going from (1,1) to (4,n) takes 3+n-1 steps regardless you take the "inverted-L-shaped" path or some intermediate "staircase-shaped" path. This is true for any path that does not go back to the starting point. This is the same for (4,1) to (1,n).

        For my reasoning, the key was observing how the two "diagonal" paths (that are shortest paths too!) crossed => place hotels with horizontal symmetry.

»
3 weeks 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?

  • »
    »
    3 weeks 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)

  • »
    »
    3 weeks 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

  • »
    »
    3 weeks 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!

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

      Use block formatting it gives monospace font.

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Problem B

Based on intuition : easy

Based on Proof : hard

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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

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

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

»
3 weeks 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

  • »
    »
    3 weeks 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.

»
3 weeks 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.

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

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

  • »
    »
    3 weeks 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)

    • »
      »
      »
      3 weeks 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!

»
3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks 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.

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

    Well it's easy to see that if you set hotels symmetrically equal to each other, the tourists will always have the same number of paths. The worst case is to set hotels is such a way like

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

    at this point, there will be no equal number of paths because you block the shortest way to upper guys and lower ones have no problem to pass. But it doesn't give the "NO" answer, because you can just set that one hotel in the middle of second line since they made us sure, number of columns will always be odd.

    So there is no option to get wrong answer, you can just do:

    fullfill lines if number of hotels is bigger than n — 2 and for modulo number of hotels left from k / (n — 2) (the rest of them) set simmetrically like 1st column -> last column -> 1st column -> last column.. with one condition, if your modulo equals 1 (so there is only 1 hotel to be set) just place it in the middle of the line

    In other words always go like -> middle -> left -> right -> left -> right...

    7 3
    .......
    .#.#.#.
    .......
    .......
    
    7 1
    .......
    ...#...
    .......
    .......
    
    7 7
    .......
    .#####.
    .#...#.
    .......
    

    Submission -> 38056037

    That's my approach to this problem and i hope i explained it clearly with not much language mistakes :)

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

      Aah, now they make sense to me. Your first example made it pretty clear and the middle->left->right... seems to be the way to go. Thanks a lot! I coded it in a similar fashion and got an AC. Great explanation! Here is my code: 38055986

  • »
    »
    3 weeks 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)

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

      It is easier to place hotels with vertical symmetry

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

        Could you please elaborate why?

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

          Because you don't need to handle many cases. Solution with only one 'if': 38060661

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

        We probably mean the same thing! By horizontal symmetry I mean over a vertical axis.

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

          Oh, my bad

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

            Not at all, I should have been clearer!

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

      I don't quite understand how you implied crossing of the diagonal path leads to placing hotels with horizontal symmetry..

      I think horizontal symmetry works well with even k. Could you explain how you approached odd k using the same logic?

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

        See for example the (now fixed) drawing in my comment above. The crossing diagonal paths form a shape resembling an X, while path on the borders are L-shaped. Imagine to morph between the two to find other possible paths.

        If there are no hotels, for any path from top-left to bottom-right you can find a mirrored path from bottom-left to top-right. For any top-left path you remove, you want to remove the corresponding bottom-left path.

        For example, to remove the two diagonal like paths you can place two hotels like this:

        ....X XX...        ....X XX...
        ...XX .XXX.        .#.#X .#X#.
        .XXX. ...XX   =>   .XXX. ...XX
        XX... ....X        XX... ....X
        

        As you say, this works well with even number of hotels. For odd number of hotels it just works: you have an odd number of columns, so place one more hotel in the middle column. See my solution at http://codeforces.com/contest/980/submission/38049226

        They grow roughly like this:

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

          Yes, now it makes sense. Amazing work! Thank you for explaining your approach. Really helpful!

»
3 weeks 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:

  • »
    »
    3 weeks 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 :)

    • »
      »
      »
      2 weeks 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! :)

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

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

»
3 weeks 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)
»
3 weeks 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?

  • »
    »
    3 weeks 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