By MikeMirzayanov, history, 5 months ago, translation, In English,

Hello, my dear Codeforcers!

Technocup is the olympiad for Russian-speaking highschool children. The winners will get significant benefits to enroll at Russian universities.

But it become open for everyone! Even if you are not a Russian-speaking highschool children, you can register for unofficial (out-of-olympiad) participation. The problems will be translated to English.

The contest starts on October 15, 09:05 (UTC). It will contain 6 problem to solve.

It will be rated round for:

  • official Technocup participants
  • unofficial participants from Div. 2

The contest will be hosted according Codeforcers rules.

UPD 1: The scoring is 1000-1000-1500-1500-2500-3000.

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

»
5 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Would the problems be in English ?

»
5 months ago, # |
  Vote: I like it +93 Vote: I do not like it

3 Div.2 only Contests in 3 Days O_O

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Bad luck for Bangladeshi contestants ! We will miss it, because we have ACM-ICPC Preliminary Contest starting at the same time (3:00 PM UTC+6) today! Missing a CF round is very painful to me. But wish to participate in this round virtually, as there is no alternative.

»
5 months ago, # |
  Vote: I like it +13 Vote: I do not like it

What will be the difficulty of the problems like?

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Almost missed this round since there was no notification yesterday. hope I won't do so bad at this very unusual time.

»
5 months ago, # |
  Vote: I like it -21 Vote: I do not like it

unusual round with unusual time

»
5 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Rated ?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am new here.How much rating is div1/div2?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks

»
5 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Looks like there'll be no trivial problems : 1000-1000-1500-1500-2500-3000

»
5 months ago, # |
  Vote: I like it -22 Vote: I do not like it

I am really happy because we have so many rounds in few days. Thanks !

But when I saw in description of the task that is interactive + looked at inputs in the second and fourth problem, my wish for doing round dissapeared :(

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I've got my D running on pretest 3 for about ten minutes

Can anybody tell me what's wrong with this?

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

What was pretest 4 on problem B?

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

    I think something like:

    a0.50a0.50

    answer is just 1, you shouldn't print 1.00

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      I am sure this is not the pretest since my code accounts for this

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

        Maybe a999.999b0.01c0.99?

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

          This is not it either

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

            for me , a case when answer is 1 not 1.00 worked for getting past test case 4 .

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        well, in this kind of problems you never know where the WA comes from :(

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

    how about a13.523.532.01b0.98c0.01

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I got this pretest working after I changed int to long long. This stupid mistake took so much time and score from me...

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

      I did the same mistake and I didn't get blue because of that :C Well better luck next time :D

»
5 months ago, # |
Rev. 3   Vote: I like it +25 Vote: I do not like it

Problem B was unusually horrible ;[

Even #passed C is greater than #passed B...

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I Agree, but for some reason I thought it was easier than A and thus tried to solve it first.

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Is D completely greedy?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Yep!

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    matching problem but can be solved greedy

    N=1e5 so greedy is safer to code

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it +6 Vote: I do not like it

      <_< I stupidly forgot about the bound that preference will be adjacent sizes so I actually did max flow. You only need ~50 nodes for your max flow though, because you can group together people with the same preference specification.

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

        I struggled for quite a time but still couldn't understand the greedy algorithm. I am more stupid as I didn't notice the "neighboring" constraint until reading you comment T_T

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How do we construct a network small enough for a flow algorithm to pass the time limit?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E Pretest 5:Anti Hash?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I dont know the answer to problem D. please tell me the approach. I thought it like putting shirts which are sure over and over again.

And after the contest I read prob F, and is it greedy???

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    i used dp but did not code it

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    Sort the people by their tshirt choices sizes . Say you want to assign x "S" tshirts , you greedily assign them to people with only one choice . If you cant the answer is NO . Next assign tshirts to people with one of the choices as "S" . After that remove "S" from the choices of people who havent been assigned any tshirt yet . Similarly for other tshirt sizes .

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

    Problem D: assign T-shirts for participants with only one size first. Then sort the remaining participants by size, always try to give them a smaller T-shirt if possible, bigger one otherwise. If any of the counts for remaining T-shirts in negative, print "NO".

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

      a sample code please?

      && and also is F greedy?

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

        Sorry, I couldn't solve F.

        My C# Code for D (as submitted, added some comments):

        Code
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why is this correct?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • assign T-shirts for participants with only one size first

        You can't do anything wrong in this step, so it should be obvious, that this is correct.

        • Then sort the remaining participants by size, always try to give them a smaller T-shirt if possible, bigger one otherwise.

        I should clarify, that I start with the contestants having the smallest size. So, if I have T-shirt S and M (one each), participants S/M and M/L, then I assign the S T-shirt to the S/M participant. If I would not do that, noone else would have use for the T-shirt. So, if I assign it in this step, I can't break anything. There might be some more participants with the same size, but not enough T-shirts of the lower size, so these get a larger one (if they wouldn't, there would be no way to give them any T-shirt). Now we have handled all participants with the smallest size. We can go one with the next bigger size, that works in the same way as the previous one.

        • If any of the counts for remaining T-shirts is negative, print "NO".

        That means, that I assigned more T-shirts of a size than possible. That obvoisly doesn't work.

        One could solve that problem with a max-flow algorithm too, but it would be quite overkill.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, that's good enough to me... Thanks!

          One more question: how do we construct a flow network small enough to Edmonds-Karp fit the time limit?

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            The graph is actually quite small: you have vertices for each T-shirt size as well as each participant type (2*sizes-1 types here). Two more vertices (source and sink), that's all. The edges are the capacities (from source to participant: count of participants of that type, from t-shirt to sink: count of t-shirts). Numbers are random, change them depending on the testcase:

»
5 months ago, # |
  Vote: I like it +21 Vote: I do not like it

I hate tasks like B . C and D were way easier . I wish I'd read D before B :(

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    B took lot of time. F was not that hard either. I needed some more time for F.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E ?? without hashing

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Aho–Corasick algorithm

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

      can you please explain your approach ?

      • »
        »
        »
        »
        5 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        I haven't coded it yet, but it should be something like this.

        1. Build the aho-corasick tree.
        2. Build an array, mark the possible "jumps" for each position. This can be done by searching the CD through the aho-corasick tree. (You can handle the name that goes cyclic by extending the string) Also check if it is possible to reach that position. For position i<k we will assume it is always possible, for others check if s[i-k] is possible.
        3. Finally check if it is possible to reach s n*k+d . If yes, print the combination.

        This should be O(n*k + g*k), which is guaranteed to be about O(1e6 to 1e7) and fits into the 4s TL easily.

        UPD: My implementation: http://codeforces.com/contest/727/submission/21471422, remember to handle repated usage of a certain name.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Maybe Suffix-Array. Use Binary-Search to match all the names of the game to the string on the CD. Then find some positions which can make the string on the CD filled by these names.

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

    I thought so: take the text, copied it, and just tested an array of names in the copy text. I copied to remove him from the proven results, and in the original took position. Separately tested variant with the transfer.

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

I did that stupid mistake str.size() — 3 and leading to integer underflow issue.

But can anyone explain why this happens? is integer underflow also compiler dependent? o.O This code http://ideone.com/QU5GRm doesn't work as on ideone on my system?

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Approach for problem D?

»
5 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

F hack test:

3 1 
-6 -3 -3 
6

Answer: 1

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Any ideas why one could get WA50 on E?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Assuming you're using a hash-based solution, I think that test case makes a bunch of games' hashes collide, so that if you try to keep a map "hash -> game", it won't work: this would have to be a multimap, since several games can hash to the same value. To solve this problem, I used two different hash functions.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the intended complexity for F?

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

    We have proven complexity and unproven O(m + n2).

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it +24 Vote: I do not like it

      Isn't my O(n2 + m) DP trivial (and trivial to prove correctness)?

      Maybe I'm missing something?

      Edit: I have missed factor so the correct complexity of my implementation is . (integer sorting can be used to get O(n2 + m) (under reasonable bounds of values and on a reasonable model), though).

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        It is great. Please write it!

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
          Rev. 2   Vote: I like it +16 Vote: I do not like it

          dp(i, r) is the minimum possible non-negative value you can start with at position i and go till position n, removing at most r elements, such that the value never drops below 0. Complexity of this step is O(n^2).

          For a given query b, you can use binary search on the number of elements r you need to remove, using dp(1, r). I have used 1-indexing. Complexity of this step is O(m*logn).

          Total complexity is O(n^2 + m*logn).
          Code

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Using a greedy algorithm, the complexity will be O(n^2 * log n * log m), which also gets accepted. 21472657

»
5 months ago, # |
  Vote: I like it +96 Vote: I do not like it

Rating changes for unofficial Div2 participants ?

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem D: http://codeforces.com/contest/727/submission/21454057 when i run same code on my system i am getting correct output :(

»
5 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Anyone else cannot find their name in the standings although they participated?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

WTF !!!

This is bullshit , where's the rating change for div2 !!!!!

»
5 months ago, # |
  Vote: I like it +7 Vote: I do not like it

That feel when you fail the round but still improve your rating and become blue. https://www.youtube.com/watch?v=BinWA0EenDY

»
5 months ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

.

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Waiting for div. 2 rating changes!

»
5 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Is the rating updated? I'm from div.2 and was not rated.

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I am an unofficial div 2 participant and my rating stays the same after rating change. Can someone explain?

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    for all unofficial div.2 participants still doesn't change.

    I think rating change in this round will be in two part for us and for officially participants separately.

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

    That's a common problem for DIV2 unofficial participants

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

    Ratings haven't been updated yet.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    It will be updated soon.

»
5 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

thanks for clearing!

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Hi. Could someone please clarify who will have ratings changes for this round? It appears that all those who were official participants have had ratings changes, unlike what was said — that it will be rated for div 2 and official participants are Russian school students. If it is clarified, it will be great!

»
5 months ago, # |
  Vote: I like it -17 Vote: I do not like it

This is the best comment I read :D

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What about the editorials ? there will be editorials like regular CF rounds ?

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

    Of course, there were editorials for the previous Technocup.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Rating changes are weird for unofficial participants . In usual rounds any rank < 300 fetched me a positive rating change , today even a rank of 177 fetched me negative change o.O

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

    It depends on different things like number of participants and your own rating ! (AFAIK)

    If an expert is ranked X and a newbie ranked X too .. the newbie's rank will increase more than the expert's .

    (if am wrong please correct me :) tnx )

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

    That's because number of users were much lesser today.

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

In problem D, flow worked. Constraints were not tight.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Do you mean to say that the test cases are weak. Or your algorithm worked in linear time? As far as I know max flow works in O(E*V^2).

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Why didn't I get any rating changes? (I registered during the contest)

»
5 months ago, # |
  Vote: I like it +48 Vote: I do not like it

Achievement unlocked! Gotta change my handle now!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I see that some div2 participants have their rating changed after the contest. But still no change for me :( ?

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

where is the editorial ?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem E. I have written hash as described here but failed on 14 test. What is wrong? It is not good approach here or should I search bag in my code?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any python solution passed for D ? my Python code got TLE, it's frustrating when you have to rewrite the same code with another language to get accepted.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Would someone mind help take a look at this code for Div2F? It seems to over-estimates the answer but I don't know why.

http://codeforces.com/contest/727/submission/21475250

Logic: Solve the queries offline, answer them in non-increasing oreder as the solutions are monotonic. Always keep the minimum prefix sum, whenever the guessed mood is not sufficient to compensate the prefix sum, keep removing the worst quality question from the array and increase the counter by one.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Removing the worst isn't optimal. We should remove the one that maximizes the minimum of new prefix sum.

    3 1
    -2 2 -3
    1
    
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the editorial be posted?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    It is already posted (and translated, as the Russian version was available before the English one)

    http://codeforces.com/blog/entry/47773

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

      How did u know that it was posted ? I log in daily and didn't notice it in "Recent actions" section !

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

        I guess it was posted in recent actions, though I am learning Russian and sometimes I go to Russian version of the website (maybe it was only posted there and then I changed the language to English — as I know less Russian than a 5 year old kid. I don't know how blogposts work, but I saw it in recent actions).

»
5 months ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

:(

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If someone have missed editorial, it is there.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Would it be a rated contest?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We are planning to run TechnoCup Elimination 2 as rated contest for at least D2.