Yury_Bandarchuk's blog

Codeforces Round #267 (Div. 2)
By Yury_Bandarchuk, 10 years ago, translation, In English

Hi everyone!

Codeforces Round #267 will take place on September 18th at 19:30 MSK My name is Yura and this is my first Codefocres round and I hope not the last.

I'd like to thank Fedor Korobeinikov (Mediocrity) and Alex Vistyazh (netman) for helping me to test all the tasks and prepare this round. Also, special thanks Gerald for helping me to prepare the tasks, Delinur for translation of all problem statements into English and MikeMirzayanov for Codefocres and Polygon.

I hope that everyone will find the problem for himself, and plunge into the student's life.

Good luck! =)

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

Comments Comments (163)
| Write comment?
»
10 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Third Belarusian contest for last 2 months:)

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

I think this time it's better to not hope for math! If you remember problem B of last contest (round #266), most of the passed solutions, failed in system testing! Also right now it has less accepts than problem C of that contest!

Good Luck!

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

    I liked question B even though my solution got hacked. It did not seem tough(probably because it was level B and I was expecting it to be easy) at first look but required careful observation.

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

First time participating out of competition!

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

All the best for your round, Yura!

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

netman From grey to red , your graph is awesome it gives hope =D

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

The time link on this blog is broken, but according to the contest schedule, the contest will be held on Sep 18th 2014 at 19:30 MSK. So it will start while the CF Training Episode 2 will be running. Therefore, I think the schedule should be changed so that people can take part in both contest and training.

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

Does "the student" also have too much biology homework?? -_-

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

never heard about Codefocres before :)

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

Following standard procedures, I have to communicate that:

This is my first round out of competition!!! :-)

I really don't feel prepared for Div 1 right now, seems like I got lucky last round...

Hope today I do a good job and build up some confidence for my first Div 1 round!!

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

    Yeah, same, my solution for E last time was apparently flawed but worked because of weak testdata.

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

I hope that the contest can be earlier so that I needn't stay up late. (I'm from China)

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

    Nope, I love this time, in China, I always get up at 11:00am and go to bed at 3:00am, now I'm in very good health!

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

      lol, you should see the sunrise with more frequency. It is good for your brain!

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

wow , over 4000 registered . Hope CF doesnt crash & can fully function. Good luck & high rating to all :)

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

    Elo rating system can't provide high ratings to all ! therefore good luck to all !

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

      i know that , but that doesnt mean i cant hope for high rating to all ^_^

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

    unfortunately it crashes at the beginning of the contest, when most of the participants are submitting for problem A.. Hope that future contests will run smoothly :)

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

Hope to enjoy it!

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

Seems to be a good contest :D Good luck everyone ...

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

don't miss to surprise us with scoring system just before the start of the contest :D

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

10 minutes left. What about score distribution? Good Luck.

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

wow final number of registration users is x4777
Lucky Number

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

    Actually, x4776.

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

      Actually it's my fault I didn't make a screenshot :D it was x4777 but I don't know what happened

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

        And now it's 4775 :D

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

2 minutes before the contest. Still unknown score distributions.

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

what about scores?

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

long queue!

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

Worse is on a comeback! He solved the first 2 problems in 9 minutes!

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

There should be an online issue redressal system. Commenting on the problem to get clarifications from the problem setter depending upon the language of the problem. Or is there already existing?

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

New superstar!

http://i.imgur.com/igG6Qzz.png

P.S. Nothing can change worse :D

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

In problem B, if x[i] could be zero, i'm sure there would be many hacks! Because i saw many users in my room which said while (num>0) and if num was zero, their code wouldn't work!

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

Damn!! What was the tricky test case for C? My solution got hacked.

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

    4000 60 60 0 0 ... 0

    or

    5000 1 5000 1000000000 1000000000 ... 1000000000

    I got two hacks with these

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

      This is just great. I got hacked because Python has failed me yet again. Maximum recursion depth exceeded. So cruel

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

How to solve C?

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

    dp[i][j] = max(dp[i-1][j], dp[i-m][j-1])

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

      Can you be more elaborate, please? What does the dp state (i, j) signify?

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

      Would you please elaborate

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

      It should be dp[i][j] = max(dp[i-1][j], dp[i-m][j-1] + sum[i] — sum[i-m])

      sum[i] = a[1] + a[2] + ... + a[i];

      dp[i][j]: In first i numbers, you choose j pairs. you can get the max ans.

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

    DP : dp[i][j] denotes optimal answer when we choose i m-length sub-arrays before index j+1. Also b[j] is sum of first j elements of array. Then : dp[i][j] = max(dp[i][j-1],b[j]-b[j-m]+dp[i-1][j-m]); //You either choose j-m+1...j as a sub-array or not.

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

what is the hack case for D? is it about cycles?

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

    I guess it is about overflow.

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

    Answer could not fit in 32-bits type.

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

      How come? The total input length could not exceed 5*10^5 => Answer <= Total input size.
      UPD: Thanks for explaining the test case. While the number of r's will be <= total input size, the total length of final words <= 5*10^10.

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

      Oh oh oh ... you mean in case of minimizing the R ... we pick a long string each time that the total len will be larger than 32-bits?!

      Challenge Accepted :D Nice Hacks !!

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

      I've changed int to long long but unfortunately the new verdict was TL :(

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

        First find the R's and Len of each string store it somewhere by an ID and work with these numbers.

        That should work!

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

How to do C?

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

    DP : dp[i][j] denotes optimal answer when we choose i m-length sub-arrays before index j+1. Also b[j] is sum of first j elements of array. Then : dp[i][j] = max(dp[i][j-1],b[j]-b[j-m]+dp[i-1][j-m]); //You either choose j-m+1...j as a sub-array or not.

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

      Nice solution. I definitely need to learn DP.

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

What is the approach to solve D ? I tried to solve it by dp with state st(index , no. of r , cur_len ). Will this represent a unique state or not ?

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

    i did it by simple dfs. Will see is wrong or not after systests

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

    Simple DFS+DP won't work. You'll need SCC+DP.

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

      aha. WA25.

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

      what's SCC? got WA 25 dunno why.

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

      You don't need to keep all of the edges. If you just keep the edges like st1 -> st2 witch no. of r in st2 is strictly smaller than st1, your graph will be DAG and you don't need SCC! :)
      (You also have to keep the edges between states with same no. of r if endpoint of the edge have smaller length)

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

        I don't think I quite understand your approach. Could you please elaborate for this case:

        1
rr
2
rr rrr
rrr aa
        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        i don't think this is right.

        if we can change r to rrrrrrrr, and rrrrrrrr to e, it will be best answer.

        maybe just didn't understand u

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

      simple dfs + dfs + dp work.

      first, we need to answer d[v] = min(d[v], d[to]) before dfs.

      now, answer of cycle in 1 element of the cycle.

      next dfs, we share answer to all parts of cycle, so here u can not use SCC

      here is the code http://mirror.codeforces.com/contest/467/submission/7850107

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

I love DP .... :)
Nice Problem C ... :)

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

Why my 1st is skipped despite doing only 1 submission http://mirror.codeforces.com/contest/467/my :(

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
  • Am I the only one who did not get this sentence "Fedor may perform this operation any number of times." — appropriately!!! I thought it says, if a finds a feasible replacement b then it will do it and if later it finds more feasible replacement it will be replaced by c. In short I thought a can be replaced by any number of times by its synonyms. I didn't understand that this replacement can be recursive I mean, that synonym can also be replaced by its synonym.
  • essay : a
  • Dictionary
  • a <=> synonym_of_a_1
  • a <=> synonym_of_a_2
  • a <=> synonym_of_a_3
  • synonym_of_a_1 <=> synonym_of_synonym_of_a_1
  • I thought that sentence meant a can be replaced by any of synonym_of_a_1,synonym_of_a_2,synonym_of_a_3 but it actually meant which I obviously came to know by others that meant a can be replaced by synonym_of_a_1 and synonym_of_a_1 can be replaced by synonym_of_synonym_of_a_1!!!
→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Consider this case:
    1
    rrr
    2
    rrr rrrr
    rrrr e

    or even this one:
    1
    eee
    2
    eee efef
    efef a

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

Why my 1st is skipped???

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

    Submissions are skipped when exactly the same code is submitted before and judged.

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

    It has also happened to one of my friend. Only submitted a single code to a problem but it was skipped with "JUDGEMENT CALL".

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

Why my 1st question is skipped?

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

How in problem C two same solution one got Accepted by c++ and other got memory limit by java?

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

    Moreover, some solutions get ML on Java7, but AC on Java8.

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

      Yes my solution on java 7 when I changed it to java 8 got Accepted . Very bad judging :(

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

        I think, redjudge with ml 512 is a good idea.

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

    Why my 1st question is skipped?

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

How to solve D and E, could someone can teach me ? thanks.

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

How to solve D ?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it
    1. Сreate a directed graph of rules (rule = edge in graph).
    2. Find all strongly connected component.
    3. For all component find min vertex in it (minimum number of 'R' or minimum length)
    4. Compress graph in tree (component in old graph = vertex in new) and update min for all components (using DFS).
    5. For all worlds in text find vertex => find components => add min to answer
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      realy HARD approch :|||| just sort the nodes and make dfs from sorted nodes :| look at my solution for better undrestanding

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

    I'll Try to explain my solution.

    Let's forget about the words we have for now and focus on the synonyms. Let's model the problem as a directed graph problem with vertices as the words we have in the dictionary and there is and edge from word a to word b if word a can replace word b. Each word has a cost of <Number of Rs,Length>, If the cost of some word a is smaller than the cost of some word b, then it's always better to substitute word a with word b. But Notice that word b can also be replaced by another word c for example if c has a smaller cost.

    So the first solution that comes to your mind is a simple dfs from each word to find the word with the smallest cost to be replaced with. The problem with this idea is cycles. If you started at some word and through the dfs you went back to that node again then words of this cycle can replace each other and the optimal solution is that they are replaced with the word with the smallest cost.

    Wikipedia : "A graph is said to be strongly connected if every vertex is reachable from every other vertex". So words of a certain strongly connected component here can replace each other so let's find all strongly connected components and treat them as one node with cost equal to the minimum of the costs of the node of this component.

    In our new graph there is an edge from node a to node b, if there is any edge in the old graph starting from any node in component a and ending in any node in component b. Now we are sure that in our new graph there isn't any cycles and we can run the dfs we mentioned before to get the cost of the representative node of each strongly connected component.

    Finally back to our words, The cost of a certain word is the cost of the representative node of the SCC in which this node lies.

    Note A common hack in this problem was that the answer may not fit into a 32-bit integer.

    Here is my solution 7840587, I hope you understood my explanation :)

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

Can you check if there is some issue with "Memory Limit Exceeded"?

http://mirror.codeforces.com/contest/467/submission/7840542 — This failed on 14th test case with Memory Limit Exceeded

http://mirror.codeforces.com/contest/467/submission/7842953 — This failed on 3rd test case with same error. This is supposed to use less memory (I halved a array size) than above solution. That passed 3rd case and this failed. (I checked that both are same test case)

-Anudeep

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

Couldn't one solve C with segment tree? I've almost implemented it, hadn't enough time, but don't know if such a solution would pass tests.

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

I submitted 7840896 and 7841275. The only difference between these two codes is \n character at the top of printf. Although, they give different verdicts (wrong answer on pretest 2 and wrong answer on pretest 4). How is that possible?

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

I tried to hack this problem with m=1000, as the coder stored the value in 1001 th index. But he/she declared array like a[1000]. My hacking was unsuccessful ... How did it happen ??? :(
submission link... 7839186

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

    your submission link is wrong it will be 7839186

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

    Unlike java, which directly gives out of bounds exception, C++ silently tries to access the memory index.
    Two cases can occur:
    1. the memory access is not allocated to the current program: in this case it is SIGSEGV(e.g. allocating a[1000] and accessing 10^7th element.
    2. The memory access is allocated to current program: like allocating a[1000] and b[1000] and then accessing a[1005] could give some element of b since such small arrays are allocated mostly contiguous. So, if the memory access does not cause SIGSEGV and is not altered by an intermediate code logic, it will behave as normal (extended) part of array, and hence the program gives correct answer.

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

Why is my code giving Garbage on Pretest 1? Works fine on ideone and codeblocks.

http://mirror.codeforces.com/contest/467/submission/7841331

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

    It is contest too???

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

    Codeforces temporary is unvialable...

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

    You are accessing i-l index in ans[i-l] . When i=1,l=m then you are accessing negative indices, which gives unpredictable behavior.

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

Why did my solution time out on test 22..? I used top down approach with memoization.. I think my complexity is O(nk) which is the complexity of most accepted solutions..

http://mirror.codeforces.com/contest/467/submission/7840201

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

    you have n*k nodes ans each node use O(n) to update so O(n^2 * k ) in total ;)

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

      Ohh thanks a lot.. Can you please give a hint on how to modify my solution to make it O(nk).. ?

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

        From every position there is effectively only one possible transition. Either start an interval from that point, hence you need not consider the next m-1 points and skip directly to the i + m point with number of intervals formed increased by 1. Otherwise do not start an interval and hence move to next index with number of intervals remaining the same. P.S. Have a look at my solution for better understanding. :)

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

    I think that you did not check the exit condition when y == n+1 you should return

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

    Your complexity is actually O(kn^2). Number of states is kn and from each state you are doing n transitions.

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

Why there isn't any UPD in the blog? Editorial publishment time, Score distribution, Top 5, ...??

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

My great congratulations to Bredor! ^_^

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

    it would have been fitting if Bredor had become Candidate Master in Round #228. ;)

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

467C - George and Job was a very nice problem. :)

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

I solved a b c and d but because of the contest stress I didnt realize that c was actually n^3. If I realized that the code I have written in the contest was n^3 I could easily delete the for loop from the dp function. By problem d because of not using long long I couldnt become div 1 again :(

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

Can the Java 7 solutions for problem C please be rejudged? Many C++ and Java 8 solutions with similar algos passed without a hitch while Java solutions using long[5002][5002] solutions failed with Memory Limit Exceed. Shouldn't the judging be impartial?

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

    Can you explain, why Java 8 is passing and Java 6/7 not? Thanks

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

      I don't know why its happening. But the submission with java 6/7 (link) fails while Java 8 passes (link)

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

Waiting for Editorial?

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

Can someone explain to me why I'm getting TLE on 467C - George and Job with this submission 7843970.

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

Please someone help me find the bug in D. Submission — 7845185

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

Editorial ?!!

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

    The Editorial will be ready tomorrow.

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

      Soryy, can you help me?? I'm a new one, and i don't know how to give or send my answer to codeforces What should i do??

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

        In the problem page there will be a tab SUBMIT CODE click on it and paste your code, choose the language then press submit.

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

Can someone help me with my solution... dont know where i am getting wrong. Already tried enough :( http://mirror.codeforces.com/contest/467/submission/7845375

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

so can anyone tell me why generating all possible sums of consecutive m pairs and choosing the top k of them won't work in c ?

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

    Because they may intersect and the problem states that no intersection is allowed

    1 ≤ l1 ≤ r1 < l2 ≤ r2 < ... < lk ≤ rk ≤ n
    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider the array: 0 1 1 1 0 0 where m = 3 and k = 2. You will choose the the pair (1, 3) but then you need one more pair of size 3. So this is not going to work.

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

Can somebody explain the other approach for D(without scc).
Many submission seems to be on the line of using priority queue with all starting nodes already pushed in it.

like this here

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

    Though I have solved the problem using SCC and DFS. But I have understood the greedy Solution.

    At first give some id to the string. Then if an edge is given like from A to B. Insert a reverse edge to your graph like b->a.

    Now use priority queue or just sort the nodes by their 'R' count, and string length as tie breaker.

    Then in ascending order run a BFS/DFS to cover all the ancestors of a node (lets say x) with the value of x. If you find a node is already covered ignore it ( so the complexity of running total BFS/DFS will be O(n) ). Why we will cover the ancestors with that value ? Because all of the parents can be converted to that node x and node x does have the lowest cost so far.

    And the complexity is O(nlogn + n) = O(nlogn) overall.

    Hope you have understood the solution.

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

Hey can anyone explain what "Fedor wants to get an essay which contains as little letters «R» (the case doesn't matter) as possible" this means in problem D? As little letter as possible means what? Can anyone explain with any of the testcase provided? thanks in advance :)

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

    That means that Fedor wants to get an essay which contains minimum number of 'r' or 'R' as a character and case doesn't matter means 'r' and 'R' consider to be same :) In case 2 :

    2

    RuruRu fedya

    1

    ruruRU fedor

    we can replace RuruRu with fedor where the final essay will be fedor fedya. This essay contains only 1 R and the total length of the essay is 10.

    Hope it helps :)

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

I really enjoyed the problems, one of the best Codeforces rounds, but soon after the beginning of the round, Codeforces kept on 'Codeforces in unavailable' for more than 10 minutes. It's sad because hundreds of other coders made submissions for B while I was unable to try. It really should be avoided.

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

Can someone explain problem E

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

:) Hello

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

I have started participating in the contests here, yday I did 2 questions AC but here it shows only 1. Second I did, in three attempts(3rd was AC). But then how in final standings, its showing only one accepted. Even in the last contest, I submitted my sec solution i the last two minutes of the contest. There was a long queue for the judge and my solution was evaluated after the time got over and passed all cases, but wasn't counted in my solutions accepted during the contest.

M i getting wrong somewhere..? Please help!

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

    check your submission history. your code for B failed on test case 15.

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

    Actually any AC during the contest won't mean that your code is right and will pass the test cases.It just means that it have pass the pretests which might be weak.after any contest all of ACs would be rejudged by all of test cases and they might fail at that time. sorry for my poor English.

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

When will the editorial be up?

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

I saw someone using the greedy algorithm to solve the problem E. But I don't know how to prove it. Can someone explain it?

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

Editorial please.

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

where is the editorial ??

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

where is editorial link?

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

Can somebody please explain what is going on with problem C for me. I keep getting out of memory error. I have resorted to copying Java 8 solution of VArtem here: 7829968, and yet I still receive out of memory error, while for him it passed. See my submission here: 9636506 . Can somebody please explain what is happening, I am going out of my mind here?!? By the way, I typically never copy someone else's solution to submit, however I only try after not being able to solve problem for month, and keep thinking about it and no matter what it is out of memory error for me!

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

where is the tutorial of this contest ?

→ Reply