Nerevar's blog

Codeforces Beta Round #10
By Nerevar, 15 years ago, translation, In English
Codeforces Beta Round #10 took place on Thursday, 15th of April at 19:45 MSK. This time I am the author of the problems. I would like to thank the creator of the Codeforces Mike Mirzayanov for correcting the statements and Julia Satushina for the excellent translation problem statements into the English.

I want to apologize for the problem D. There was a bug in model solution. Moreover, this problem may not be solvable in polynomial time even with such constraints on the number's size. We will investigate it. I hope nobody will feel offended in any case.

UPD: Now I am pretty sure that my model solution for the problem D was completely wrong. I want to apologize for it again. There will be no rejudge of the solutions accepted during the contest. The statement will be changed so that it will ask to find the LCIS of the two sequences. This problem definitely has a solution.

UPD: Problem D was changed as I promised.
Announcement of Codeforces Beta Round 10
  • Vote: I like it
  • +21
  • Vote: I do not like it

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

No need to thank me for each contest. Frankly speaking, I feel embarassed, and... ashamed for the comment I made some days ago (hope, you know what I'm speaking about). Forgot to ask you earlier not to mention me. Moreover, one of the translations is yours))

We'll see how good the translations are during/after the contest ;-)

From the bottom of my heart I wish you all the best! It is such a difficult think to make a contest (now I know this for sure). So, you deserve only the best))

→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    We will give You a lot of thanks for each contest over and over again. =)
    Thank you! =)
    → Reply
  • 15 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Forgot to say – it’s a difficult thing to make a contest, but it’s even more difficult to reconcile with the idea that you have to miss the contest and lose rating points… :-( For a programmer like you it’s hard… So, good luck one more time))

    → Reply
15 years ago, # |
  Vote: I like it +12 Vote: I do not like it
Anyone wants to share ideas about solving D?
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
C: they require to count the number of triplet (A,B,C) which d(C)=d(d(A)*d(B)) but C!=A*B?
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    ya, I guess that is what we need to find. The translations for all the problems, can be made better. 
    No need to go for complex english wording. Either make the little story in the problem simple and neat or, after the little story is finished in the problem, you can just write precisely, "in other words, you are given --this-- , and you need to find --this-- ". Apart from this, Problems are very nice. Thanks a lot for all this !
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      The translation seems fine to me.
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        For what it's worth, I personally couldn't make heads or tails of the problem statement during the contest or after it. I still don't get what it asks. That doesn't necessarily prove anything about the quality of the translation of course (maybe I'm just thick) but it's not a good sign.

        For a slightly more objective assessment, it might be interesting to calculate the percentage of Russians amongst those who solved the problem, and compare that to the percentage of Russians in the competition.
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it
          I'm a native English speaker and I understood the problem statement fine.  It is almost all technically correct English but the choice of idiom is often foreign and not what a native speaker would naturally say.  Nevertheless I felt the statement was clear when read with sufficient patience.
          → Reply
    • 15 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Well, the translation is not really good. But I found it's challenged and interesting to understand the problem-statement (it's tricky but still logical). I saw similar writing style in other Russian contests at acm.timus.ru.
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        Maybe it's not a problem of translation but simply a style? It is common for the contests we are solving on our trains, that one have to "decode" a statement at first, to get rid of the "story", and only after that - start solving the mathematical problem.
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          I don't think so. That's not bad logic or bad style, but bad English. Some guys here had solved thousands of ICPC problems, but couldn't understand the problem-statement of problem C.

          Maybe the version you read was the Russian one?
          → Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
How come we cannot view code of other people's submissions?
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    We can, but not yet. Viewing other people codes takes some time after the contest is over.
    → Reply
15 years ago, # |
  Vote: I like it +2 Vote: I do not like it
I have a question about gnu c++ compiler. Which precisely version is it? Today I had a problem with outputting a long long value. The "%lld" format works at my computer, not at checker; "%I64d" - inversely.
Thanks
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can someone show me how problem E works?
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    It's a known problem... You can read this, for example:
    http://graal.ens-lyon.fr/~yrobert/algo/coins2.ps
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks for the reference ;)
      → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Wow, that's like the exact thing.  Did you know this before the contest?  I guess I don't read enough.
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        No I didn't know that before, I was just very lucky to find it :)
        Once I've heard some lecture where some guy was talking about a criteria
        to check whether a knapsack problem is greedy solvable. I thought maybe this problem
        is also has a known solution, so I went straight to google and started to search. And after
        some time I've found this.
        → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Not sure who David Pearson is, but that was one good paper.  I recommend it to everyone!
      → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I wonder if someone solved it on his own without David Pearson help
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I think it's physically impossible :)
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          It's possible to "guess" this algorithm in the contest. The algorithm is rather intuitive. Though a rigid proof to convince yourself needs sometime
          → Reply
          • 15 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            I still cannot see why the relationship between the minimum counter example w and a[i-1] - 1 is intuitive or obvious.  Any insight into this?  May be I am just stupid.
            → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Me :D
        → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I passed a tough time to understand the problems statements, specially C. Please try to make the problem statements more understandable. Though the problems were very nice, keep going :-bd.
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anyone give hints about how to solve problem C ?
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Yes, I can.
Hints are:
  1. Pre-calculate some values with dynamic programming
  2. Bust d(A) and d(B)

Full solution is:
  1. First, let's calculate cnt[X] - count of numbers from 1 to N, inclusive, with the fixed digital root X. We can do it with brute force.
  2. We bust A' and B', which is digital roots of A and B from condition
  3. For each pair (A', B') we need add to answer (which must be 64-bit integer to avoid overflowing) count of triplets (A, B, C), where digital roots of A and B are fixed (A' and B'), and digital root of C is d(A' * B'). But we need to deduct count of real solutions (let it be cntMul[A][B]).
  4. So, we need to count triplets (A, B, C) with fixed digital roots of A and B, such that C=A*B and C<=N. Well, bust first number (A), and we automatically get maximum B (maxB). For example, we can divide N to A or use two pointers. So, every time we are increasing A, we need to bust d(B) and add to cntMul[d(A)][d(B)] count of numbers, that are lesser than maxB and it's digital root is equal to d(B).
  5. We can dynamically maintain array with this count. Initially, array is equal to cnt[]. Every time we decreasing maxB, we 'delete' from it waste numbers. Just use one pointer.

And, if you can, leave feedback for my mistakes in English. :)
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hey , I really appreciate your effort to explain the solution , but I am still a bit lost :)  I didnt get what you meant by bust . And how do you define cntMul[A][B] ?
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I think he means, in American English, brute force, or enumerate.
      → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      cntMul[A'][B'] is count of pairs of numbers (A, B) with fixed digital roots - A' and B' such, that its multiplication - A*B is less or equal N. In the other words, it's count of solutions, when digital roots of A and B are fixed.
      → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
This looks like an article that solves the original version of D:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.2394&rep=rep1&type=pdf
Personally, I thought the idea was to find this article, read it and implement during the contest.
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Just looking at the abstract, the algorithm requires O(r) time, where r is the number of tuples where the sequences match, and that is one big number, right?
    → Reply
15 years ago, # |
  Vote: I like it +6 Vote: I do not like it
No. It is exponential.
→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please write a tutorial for the updated D problem :)

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

In case of problem C, for N=4 why (1,2,2) and (2,1,1) is not among expected pairs?

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

Can someone tell me how to solve E?

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

Can Someone tell me how to solve problem D ?

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

    we need to build a graph over the elements after co-ordinate compression, consider two elements i,j if i is present before j in both sequences and i<j then we add a directed edge from i to j , now the answer is to find the longest path in a directed acyclic graph

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

Editorial ?

→ Reply