GlebsHP's blog

Codeforces Round #342 (Div. 2)
By GlebsHP, history, 9 years ago, In English

Hello, community!

Tomorrow Codeforces Round #342 is going to take place. It will share the problemset with Moscow Olympiads in Informatics for students of grades from 6 to 9. Though, grades from 6 to 9 in Russia usually match the ages from 12 to 15, I guarantee that everyone (even Div. 1 participants) will find some interesting problems to solve. Problems were selected for you by the Moscow jury team: Zlobober, meshanya, romanandreev, Helena Andreeva and me; and prepared by members of our scientific committee: wilwell, Sender, iskhakovt, thefacetakt and feldsherov.

Scoring distribution will be quite unusual: 750-750-1000-2000-3000.

UPD System testing is over. Here are the top 10:

  1. _XuMuk_
  2. pandamonium
  3. latisel
  4. zetamoo
  5. yukariko
  6. I_Love_Ximera
  7. kittylover
  8. shdut
  9. harry.zhao
  10. luke0201

Congratulation! Also, problems seemed to be too tough, we should have probably made Div. 1 round. Anyway, thanks for participating, I hope you enjoyed it and learned something new!

Thanks to romanandreev for nice analysis.

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

Comments Comments (176)
| Write comment?
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I am not able to register unofficially for the contest. Please fix this.

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

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

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

In the same time as Open Cup 10 stage. It's a pity.

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

Is this contest going to start at the same time of the official contest? Because otherwise it should be unrated, right?

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

    It's not going to start exactly at the same time, but it will start before the statements become public and will end at the same time as the onsite contest (which actually runs for 4 hours).

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

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

GlebsHP you forgot to thank yourself :)

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

    A sentence like this ??: I thank myself for my great helps to myself in preparing this round.. :D

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

Links to any previous contests by the same authors would be very helpful. It'll give a good idea as to what to expect in the contest! Any help?

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

    Click on the user profiles, and go to Problemsetting tab.

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

    How would previous contests help ? o.O

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

      Quoted, "It'll give a good idea as to what to expect in the contest!".

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

Wish Codeforces a happy Chinese New Year!

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

Nice and short announcement . Kudos to GlebsHP

I guess problem statements will also be short and nice.

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

@ admin whenever i log in into my account(manish_nit) everthing appears in russian, i have to manually right click every time and select translate to english. this creates lot of problem during contests...is there a setting in the codeforces website to do it permanently.

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

    Of course not. You better learn Russian. Who would think of a language switcher?!

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

Is it national level competition?

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

    Seems to be city level.

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

      Thanks! I expected the problems to be much easier for a 7th grade local competition :). I lost too much time on the first problem, then B and C were probably just about right for a Div 2 contest (750 and 1000 points). Didn't even get to D or E ...

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

why A and B has the same points ?

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

Why not a combined division contest?

Great authors and of course great problems!

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

A contest by new( GlebsHP ) and old( Zlobober ) coordinator.

Hello Zlobober again!

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

    Why so many — votes? :)

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

      I don't know! but this contest was good for me after about 30 bad contests.

      (I took place 18 ;) )

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

        took

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

          thanks; edited (English is my default language!)

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

Zlobober is backed :))

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

Great contest and perfect timing, do contest before dinner, then watching firework at mid night, happy lunar-new year.

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

Its Sunday morning in my country. Is it bad if I miss church for contest ? I like contest!!!

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

Today in China, it is Spring Festival, which is the most important festival in China, every single of Chinese will have supper with family. I hope in the New Year, Codeforces will be better and better~

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

i will have fun before the Chinese Spring Festival dinner.

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

Luckily I won't miss the Spring Festival Gala at 20:00.

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

    But I think the Spring Festival Gala is becoming more and more boring

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

      go to watch Pay New Year's call offering of bilibili at 18:00(UTC8)?..

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

hope it will be my last div2 :D

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

happy chinese new year！！！

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

Happy Chinese New Year(the Spring Festival) to everybody and wish Codeforces will become better and better !

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

Happy Chinese New Year~

→ Reply
»
9 years ago, # |
← Rev. 6   Vote: I like it -17 Vote: I do not like it

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

What is the hacking test for problem B?

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

    If the solution searches the whole string from the beginning after each time it finds the pattern.

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

    Some participants were finding string matches in O(n) but ridiculously wrong ways.

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

      can i solve the problem B use kmp algorithm???if not ,can anyone give some advice? by the way ,happy chinese new year!

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

        I've solved it with KMP :)

        Submission

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

        You don't need KMP. O(30*100000) is fast enough, so you can brute force the whole problem. If the pattern was longer, a linear time string searching algorithm would be suggested, but in this case (the fact that it's a Div2B should give you a hint at its difficulty) it's not necessary and has a larger chance for mistakes. This is what I did in the contest (runs in max 46ms on main tests, which is easily good enough) http://codeforces.net/contest/625/submission/15858375

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

          You really replace some characters with '#'! I just imagined to replace. 15874296 Although it's after the contest.

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

C seems so easy then A and B. I think C < B < A Due to overflow with binary search, 6 wrong submissions on A :\ I hope it passes now.

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

    Is this approach correct? Write numbers from 1 to (k-1)*n in first (k-1) columns then again start from column 1 write numbers in increasing order.

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

    I think B and C are equally hard/easy and A easier than both of them.

    Where did you used binary search? I haven't use it at all.

    UPD: Well it seems that I will fail A after system testing. Actually I now think C is easier than A and B, just because its solution is obviously correct comparing to A and B.

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

      I used binary search to find number of times one could buy glass bottles. Looking at others code now, it seems there's a direct formula, but i couldn't get it correct.

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

    You don't need to use a binary search — the answer can be found in O(1) with division. http://codeforces.net/contest/625/submission/15857590

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

how to solve D ?

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

Who is the author of the Problem A? >.< And tester also >_< ?? No mercy, No mercy >_< :'( :'(

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

Now, I know why Russian coders are so good and accurate.

Nice problem-set, especially first problem.

Eagerly waiting for editorial for 4th and 5th question and hoping my solution for 1st three problems pass the system tests.

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

why this work on test

100000 symbols a

a

for 0,2 sec

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

    I tried hacking a solution like this and also failed.

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

    Find returns at the first occurence, so that takes O(1) time. erase can take up to linear, according to specification. But it is probably very optimized and the Codeforces servers are really fast (solutions with 10^9 operations can pass time limits) so it passes. Perhaps erasing the first character is faster than erasing from the middle, as well?

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

      i try to change first symbol to 'b', and it's work fast too

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

This was my solution for 2nd (div2) x = raw_input() y = raw_input() print x.count(y)

It passed the pretests XD, i dont think it will pass the final tests ... will it? EDIT : It passed!

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

    See this test 

    baaacd
aa                       
          Answer = 1.
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      As far as I know python3 count method counts the amount of non-overlapping substring appearances, so your test is not going to hack the solution.

      UPD: Not sure about python 2 tho

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

I wonder how many A solutions will remain after systests :O. What was hack test for A btw

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

Very interesting problems. I got a lot of fun. Thanks to authors!

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

Ouch, the penalty for wrong submissions really showed through this contest because of the sudden spike in difficulty between C and D. Two wrong answers for A cost me 200 places in standing (from ~200th place to ~400th place).

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

too weak pretests these days :(

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

    With strong prtests, we can't enjoy hacking :(

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

    Actually, it surprised me, as I picked about 10-15 pretests in every problem. But still ,the number of cases seems to be much more than this.

    Many solutions will fail system tests, but this time it was unintentional :)

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

Is System Test gonna take long like in the past school contests? (until the closing ceremony)

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

hack test for problem one is : 2 100 100 50

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

    Omg, and here I failed with "-1". :D Hacked some other guy with 10^18 inputs.

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

terrible! I fixed some bugs on problem D and failed to sumbit in last several seconds.

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

Still can't go to sleep because I'm terrified of the system tests for A and B :(

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

    Still can't go to LUNCH because I'm terrified of the system tests for A and B :(

    → Reply
»
9 years ago, # |
  Vote: I like it -7 Vote: I do not like it 
        String gog = in.next();
        String tel = in.next();
        int ans = 0;
        int k = 0;
        while (k + tel.length() <= gog.length()){
            String s = gog.substring(k, k + tel.length());
            if (s.equals(tel)){
                ans++;
                k = k + tel.length();
            } else {
                k++;
            }
        }
        out.println(ans);

Its B. Will it pass sys tests?

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

everyone who solved 6-th COCI task of yesterday contest must solve the 4-th problem of today easily :D

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

Anyone solved E?

I have that idea: using binary heap (aka priority queue) we sort all possible collisions of frogs by (time_to_collision, id). After that in cycle we pop first frog, kill what she could kill, update her step_size, time_to_collision and put her in the heap again (also doing this for her precessor).

Stop when the next frog in heap can't kill anyone.

Should be NlogN. But I stuck in some range checks and didn't finished the solution.

Is it correct approach?

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

    I was thinking about the same solution, but moreover you have to update time_to_collision of previous frog (I mean the one, which gonna kill actual one).

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

      Yea, I've considered that ("also doing this for her precessor").

      In my implementation I simply put another copy of previous frog in the heap (instead of find-delete-putagain, for performance). It shouldn't affect the result, because its value will be strictly lesser than old one, so old one will be skipped somewhere in the future.

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

        Do you think you could explain test case 18's answer for E? I've done it manually and get a different answer than the judger. ( This is my solution btw)

        10 10 9 4 3 5 2 2 5 4 1 6 6 7 8 3 4 1 10 3 7 9 Participant's output 2 1 8 Jury's answer 1 8

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

          Nevermind, it was an arithmetic error in my manual solution.

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

          BTW, your solution seems to get TL later on. You already got 1 second on N=12500. And it could be 100000.

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

            I expected much as I don't really make any clever observations in it. Was more expecting a TLE instead of a WA though.

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

    It looks like the correct approach. Analysis will be published in the nearest 2-3 hours.

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

      Information like this should be added in the main post as it is very hard to find this kind of information in the sea of comments.

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

Wow very fast system testing. My rank jumped from 1000 to 500's before/after system testing xD Problem A is the cause :p

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

bad contest :-(

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

Putting "Guest From the Past" as an A problem was a wicked move.
I wish I didn't waste time on it :'(

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

just 699 who can solve a in the contest XD

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

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

    Yea, very tricky A and obviously_correct_solution in C :)

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

    I don't think this round had enough score differentiation. D and E should've been slightly easier, while A and C should've been switched (or C should've been made much harder, as it's unusual for so many people to get it). A wasn't actually hard, but it was pretty easy to make a silly mistake (a lot of people used it for hacks). The concept of C was roughly the same difficulty but the implementation was much easier (no derps).

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

    The eyes... Oh my god, THE EYES!!!

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

What was the solution to D? I thought of some messy solutions but could not find a clean one.

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

Realy A problem is tricky with Time limit and Wrong answer.

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

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

Could someone just tell me how to solve A? It seemed that A wasn't the easiest problem :(

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

    can do it in O(1):

    • if buying and selling a glass one is more expensive than buying a plastic one, only get plastics
    • if not, buy glass bottles until you can't do so anymore, then buy plastics with the rest of the money

    implemented here: http://codeforces.net/contest/625/submission/15870223

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

      I too thought that it should be O(1) but couldn't solve it, maybe because i freaked out because it took too much time to solve A. It was similar to this problem. I solved that problem by brute force but obviously here brute force won't work. :/ Next time I will try to find a better solution for every problem even if it gets AC.

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

        Is's possible to resubmit an AC problem? :O

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

          yes it is, but you lose 50 points because of resubmission.

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

          yeah! previous submit gets Skipped, and new one will judge in system testing.

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

      Is it any formula for O(1)? If the item costs b units and for returning you can get c units, then you can buy (n — b) / (b — c) + 1 items by n units?

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

574 — "A" = 1228 :(

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

Today I've seen a bunch of guys whose solutions failed systests for A but still they hacked everybody in their rooms so they got about 700-1000 points just from hacks. Turns out you don't have to actually solve a problem to get sufficient points for it.

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

    Yea, its pretty usual thing for hackerfests.

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

    I found my A is wrong when i have hacked 7 persons, finally my code is hacked but i still get 750 point..... btw, there is a guy write"cin>>n>>b>>a>>c", for which i got four times unsuccessful hack

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

The task are ok, but very bad for the div 2 contest.

Only the second task was on the level which it should be.

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

Thanks for timing!! Happy Tet Holiday!! <3 <3

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

Why i got WA on b??? this is my code, any help please?? http://www.codeforces.com/contest/625/submission/15862688

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

    ababc abc

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

    If current characters in S and T are different maybe you won't return to the begging of string T.

    I didn't tested your solution, but I think this is hack case for your solution :

    S='bbbc' T='bbc'.

    Correct answer 1.

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

      yes, you're right, didn't see that coming

      thanks lot...

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

A->C, C->A

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

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

I am very interested, whether someone got full score in official, on-site contest ?

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

.

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

for D I came up with an DP solution where dp[i][j][a][b] represents the interval [i, j] can be written as the format required and current i position number is a and j position is b, a, b < 10, the solution will exceed memory limits but I fail to simplify my solution.

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

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

it can take days for GlebsHP to write/translate the editorial (remember round 327). So, let's not wait for editorial and write our solutions ideas here.

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

Wow, outstanding performance: http://codeforces.net/contests/with/latisel

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

    Cool, i was checking his past contest history

    I expect him to do 100+ unsuccessful hacks in next round :P

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

    I guess he want to stay at Div2

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

Hmmm what's wrong here? It failed at the aaaaaaa... case, where the answer is the number of a's, but my answered was one less.

codeforces.com/contest/625/submission/15869860

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

    Array char is needing one extra cell for null character after end. Sorry if my English is bad, I try hard learning it.

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

      Thanks for your answer! Your English is not bad at all!

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

please, don't say anything before the contest.

Problem set would be too easy. or Problem set would be too hard.

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

I suspect the test data of problem A is very weak, since 15867499 passed system test. But it should TLE at this case: 1000000000000000000 2 500000000000000001 500000000000000000

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

DO we have editorials for this one ?

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

Can someone help me find the problem with my O(n) B?

http://codeforces.net/contest/625/submission/15877046

I feel like it's the correct strategy implemented right... but I'm getting off by 1 on test 26.

thanks!

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

    aaab aab

    Ans should be 1. Yours gives zero

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

      Thank you! I see the problem! Cheers. And as the_art_of_war says, the easier way is of course to just go the simple way so you can't run in to tricky edge cases like this.

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

    I think the length of second string is special so small that you can solve it with O(n*m) using two cycles. If you want to make solution with O(n) you should use special algorithms with strings like Z-function or prefix-function.Maybe there is more easier way to get solution with O(n).
    Sorry for my bad english.

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

Can someone give an idea how to solve 4th one ??

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

Three WA on Question 1 give me the way to hack 5 solutions :)

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

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

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

Happy Chinese new year!Can someone tell me how to solve the A question?I see some answer:they all used (n-b)/(b-c),but I don't know why?

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

    that is it!from others: can do it in O(1): if buying and selling a glass one is more expensive than buying a plastic one, only get plastics if not, buy glass bottles until you can't do so anymore, then buy plastics with the rest of the money implemented here: http://codeforces.net/contest/625/submission/15870223

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

      My question is why n should minus b?My first use n,but I know I am wrong.Can you help me?

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

        If you don't have enough money(like n<b),you can't buy a glass one. So you shoule use n-b not n,I hope you get it.

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

Somebody help me! What the problem with that solution? Problem B.

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

Where is the editorial?

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

Author of B sucks: 15924760

→ Reply