HolkinPV's blog

Codeforces Beta Round #33 (Codeforces format)
By HolkinPV, 14 years ago, translation, In English
Good morning, day, evening, night to you.

Welcome to the wonderful randomized contest, which is prepared for you by team Saratov SU 3 (Davtyan Edvard, Kholkin Pavel, Kudryashov Igor).

Thanks to Julia Satushina, Artem Rakhov and Dmitry Matov for their help in preparing this round. Special thanks to VK company.


Good luck and high rating!
With best regards, Saratov SU 3.
  • Vote: I like it
  • +41
  • Vote: I do not like it

Comments Comments (30)
| Write comment?
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Is a tutorial available for this contest?
//It's funny! I know how to solve all problems except B!
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I didn't participate, but just read B. Did you understand it as, 'we need to change all occurrences of c1 to c2 ? '. Its just one character change at a time. First thought is.. a simple Floyd on 26x26 matrix to find cost[x][y] -> minimum cost to make x & y characters same. I hope this works.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I also thought that but I think we need to verify if we can transform A -> X, B->X if cost[a][x] + cost[b][x] is less than cost[a][b].
      → Reply
  • 14 years ago, # ^ |
    ← Rev. 6   Vote: I like it 0 Vote: I do not like it
    I also want to know the spected solution for problem B.
    I did a Floyd-Warshall from all letters to have the minimum cost for each pair, then for each char C in the first word and D in the second word I take the min(graph[C][k] + graph[D][k]), k being all letters from 'a' to 'z'.

    What is wrong in this idea?
    ---
    Fixing: I am sorry, my problem was Accepted in the contest. I thought I won a "wrong answer" but it was correct.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      You probably mean min(graph[C][k], graph[D][k]).
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Yes! You got it.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          i did it the same way.  but on pretest 7 it fails i cant' get what's my problem here is my pseudocode.
          if (length1!=...2) print -1;
          for (i=0;i<length;i++)
          { 
           min=min(a  (s1[i]   ,s2[i]) ; a(s2[i], s1[i])
           if min = a  (s1[i]   ,s2[i]) temp = s2[i];
           (for q='a' to z)
           if a( s1[i], q)+ a(s2[i],q) <min then{ min =a(s1[i], q)+ a(s2[i],q;) temp=q; 

          if min== 200 ( initally array is filled  200) print -1;
          s1[i]=temp;
          res+=min;
          }


          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Replace 200 with something larger. The minimum path length may be upto 100*25
            → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I got a presentation error on problem B for test 38. Can someone tell me why?
I have used a combination of printf and cout. Will that be a problem?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What's the test case 16 of problem C...
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
On problem B what is the expected answer for the input:
aaaa
bbbb
4
a b 1
a b 2
a b 3
a b 4
is it:
4
bbbb
or
10
bbbb
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is the test input data of test 5 (problem C)?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
On problem B,I have used :
// in the main function
if(strlen(sa)!=strlen(sb)){
       puts("-1");
       return -1;
}

Unfortunately, my code is always getting Runtime Error for test 3.
However, if  "return 0" replace "return -1", I get Accepted.
Why?
sorry for my poor English!Thanks!
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    You must always return in main function 0, and write anwer in console\file, because if you return non-zero value in main function, test system may think that you program crash with runtime error.
    → Reply
14 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it
K (the number of queries) in problem D can be larger.
In that case, O(MK) solution will get TLE, and problem D can be a bit harder to get accepted.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I noticed some of the scores are shown in blue after the final tests. Any ideas what does it mean?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anyone plzz tell what problem c meant .. i couldnt understand it ..:(

thanks in advance
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I can't understand it too!
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Give you a sequence with integers,choice one prefix and one stuffix (each of them maybe empty) to make the sum of the sequence MAXIMUM by mult each of the prefix and stuffix `s element with -1;
    Print the maxSum;
    PS: Sorry for my poor English...
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      plzz explain with a test case..
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        you are given a sequence, you take a prefix and suffix. for all numbers in the prefix and suffix, for  multiply all numbers in prefix and suffix by -1. so for test case:
        3
        -1 -2 -3
        there are many possible answers:
        (1) -1 -2 -3 sum= -6 (here the prefix is empty and suffix is empty)
        (2) -1 -2 3 sum=0 (here the prefix is empty and suffix is {-3}, multiply by -1 become  {3})
        (3) -1 2 3 sum=4 (here the prefix is empty and suffix is {-2 -3}, multiply by -1 become { 2 3} )
        (4) 1 2 3 sum=6 (this is the maximum possible answer, prefix is empty and suffix is {-1 -2 -3} multiply by -1 become {1 2 3})

        etc
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          typo:
          *for all numbers in the prefix and suffix,  multiply all numbers in prefix and suffix by -1. so for test case:
          → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
During the contest I coded wrong solution for B in Java, I didn't analyze the problem very well, but after the contest I tried the problem with the right solution in Java. I got Time Limit Exceeded. I tried every possible optimization in order to pass the test 26, but I couldn't manage it. I guess the reading input was taking the longest time. I used
BufferedReader br = new BufferedReader(new InputStreamReader(System.in);
Also, I tried reading the string byte after byte with using only InputStreamReader, but it was still TLE...
In the end I just copied my code in c++, changed some syntax in order to work with c++ and I got Accepted.

The thing I like to ask is whether some more experienced Java coder can tell me what is the most efficient reading input structure to use. I saw that there are accepted solutions in Java so every hint is welcomed.

Thank you in advance.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I had a similar problem as your's ::

    Hope that this help :http://codeforces.me/blog/entry/735
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi! I did problem D but with a rather difficult solution. Can someone give me his/her solution or the official solution?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is the test case 6 in problem E?
Test case 1 in final test of problem E is same as example test 1. Right or wrong?
→ Reply