RAD's blog

Codeforces Beta Round #55 (Div. 2)
By RAD, 14 years ago, translation, In English

While the world community of participants of programming contests is waiting with bated breath for the news about new date and place of the Final, we decided not to delay the next round and prepared some problems on the train from Petrozavodsk to Saratov. In preparation were involved Mike Mirzayanov, Artem Rakhov and Max Ivanov. Tasks were translated into English by Maria Belova.

Good luck!

Artem Rakhov and Codeforces team 

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

Comments Comments (22)
| Write comment?
14 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it
The page of this round is  just now became invisible?

EDIT: now available.
→ Reply
14 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Why are there so many judgement fails?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
281538

my code is correct and is giving correct output on my system....can the moderator please let me know...what is the prob ??
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can see the test cases for every question now. Go to your submissions and click on the submission code. Scroll down and you can see the test cases.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can view the reason of fail looking to the tests of your submission.
    You can found tests and the results below your code.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      the case for which they are giving runtime error is giving the correct output on my system.....
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it
        line 37 of your solution
        a[s[s.size()-i-1]]++;
        should be
        a[s[s.size()-i-1]-'a']++;

        After that I got AC.
        → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Wow, good problems as always!

Could anyone tell me how to solve the problem E? Thanks.
My BFS timed out, because it is O(NMlogK).

→ Reply
  • 14 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    Let build new graph where nodes are edges of current graph and edge between (a,b) and (b,c) exists if (a,b,c) is not bad triple. Finally just run BFS in new graph.

    I used hash-table for checking bad triples and my solution has O(NM) time.
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      Similar python solution, but with set instead of hash-table also got AC, although it is O(n * m * log(k)). 

      Upd: python set also uses hash-table, so it is exactly same solution...
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Orz python..

        I use C++ set And AC 140ms,O(N*M*log K).Uses Hash is also OK.
        → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      What is about the case when you have input date as 
      4 3 0
      1 2
      2 3
      3 4

      If we constructed a graph in you way we would have obtained the answer -1, because  the ways with only odd length from the given graph will be considered.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        No, we will have path (1,2)->(2,3)->(3,4) in new graph what is path 1->2->3->4 in old graph.
        → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Hi Ripatti:
      Could you tell me your problem-solving process? I cannot solve thie problem, even if using a lot of time. Maybe I need to do more practice, what is the effective?
      Thanks a lot!
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Solving process... I just read problem and sometimes solution emerges from subconscious. Else I must to little analyze problem for to see a solution.
        Practice - yes. The more I solve the faster I find solution. But reading of algo books is good idea too.
        For fast solving hard problems you must solving more and more problems a lot of time. I solve nonstandard problems from primary schools. And now I cannot solve some hard problems whatever.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Thanks a lot, Ripatti.
          I must do more and more practice to improve my           problem solving ability, I hope to get a red name someday... maybe I need long time.
          → Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Hi cgy4ever,
    Please explain ur solution to Problem B : Fortune Telling.
    I like ur solution to this problem.
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it
      There is much simpler solution.

      #include <iostream>
      using namespace std;
      int n,k,r,m=100;
      int main()
      {
         cin      >>n;
         while(n--)
               {
            cin      >>k;
                  if(k&1)
               m      =min(m,k);
            r      +=k;
               }
               if(r&1)
            cout      <<r;
               else if(m&1)
            cout      <<r-m;
               else
            cout      <<0;
      }
      Explanation:
      1) The Result must be odd.
      2) If Sum is odd - return it
      3) Else if there was an odd element, find the least (m) of them and subtract from Sum - this is the answer
      4) Else if there are no odd elements at all, Marina doesn't love Sasha. :-( Return 0.
      → Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Hey there,
I have a question, does contribution affect one's rating? (I know that this is kinda irrelevant to this blog entry, but I dunno how to ask questions, the site doesn't have something like "[email protected]" or "Contact Us", sorry anywayz)
Thanks in advance
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Contribution and rating are independent of each other. Rating is a measure of one's success during the coding rounds. Contribution is a measure of one's positive influence on a community. Contribution doesn't affect rating.
    Btw, you might want to use google search to track codeforces information in a more comfortable way
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks Aidar :D
      You've got a quite good rating yourself :) Unlike me :(

      → Reply