elakstein's blog

By elakstein, history, 4 years ago, In English

Problem Statement:- You are given a string S with length N that contains only the 26 lowercase English letters. You are also given a sequence W1,W2,…,W26 of weights corresponding to these letters in the order from 'a' to 'z', i.e. W1 is the weight of 'a', W2 is the weight of 'b' and so on.

We define the weight of a string as the sum of weights of all characters present in it. If a character occurs multiple times in this string, its weight is also counted multiple times.

Next, we define the power of a string s as the sum of weights of all strings r such that s can be represented as r+r+…+r+p, where + denotes string concatenation and p is a prefix of r (possibly empty).

Can anyone explain what does the author mean here by power of the string. Even after reading it 100 times I can't understand the statement. I would also like to know that am I just too dumb to understand it or you also think the problem statement is shit .

Link to problem statement .This problem is a part of live codechef long challenge.

  • Vote: I like it
  • -18
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

It is an ongoing competition, that problem should't be talked about.

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

    I haven't asked for solution. I just asked what does the author mean by power of string as it isn't clear from the statement.

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

    Also I have already mentioned that the question is from a live contest.

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

      It is good that you mentioned this (thanks for that), but if the problem statement isn't clear, you should submit a clarification request so that all contestants hear the explanation and you don't have an unfair advantage.

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

    I will be very thankful if you can explain that part of the statement.

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

      So, if a string is "ABC", And weight for letters is A: 10, B: 7, C:3. The power of string is power of "ABC" + power of "AB" + power of "A". (10+7+3) + (10 + 7) + (10) = 47

      Maybe I wrong

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

    He hasn't asked for the solution and just wants to understand the problem statement better. Moreover he has explicitly mentioned that this a problem from a live contest. I don't think there's a problem with this unless you mean to say that the problem setter has deliberately written ambiguous statement and wants the ones that are able to understand the statement to have some advantage, which I think is nonsense because then we're not being tested on coding skills but on language proficiency. Also, everything is up to the discretion of the person writing the comment. If you're afraid that he might get unfair advantage and don't want to comment, then don't. No one is forcing you.

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

      "...just wants to understand the problem statement better.".

      Yes, we all want that. But asking other people while contest is running is not the way to go. It is not allowed, on no CP platform, in no competition, no channel. Simply don't.

      It is as simple as that.

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

        Statement clarification is always acceptable. Although as SecondThread mentioned, it is preferable to mention it in the contest itself first. But at the end it depends on the one posting the blog. He might prefer a different community or there might be delay in the response from the problem setter.

        You can't decide the "way to go" for others. A little flexibility is essential for learning. And if you can't do that just sit tight and ignore the blog. "It is as simple as that".

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

          "Statement clarification is always acceptable." It is not.

          If you try this on CF while constest you most likely get a ban.

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

Given a string s think of it as a concatination of another string r like r+r+r ... and at last if some elements are left those elements can be prefix of r. eg s = abaabaab so here r = aba so aba+aba+ab(ie prefix of aba) so power of s is the sum of weights of all possible r. eg for ababab: r1 = ab, r2 = abab, r3 = ababab. so P(s) = W(ab)+W(abab)+W(ababab).