KrK's blog

By KrK, 4 years ago, In English,

Hello, guys!

I invite you to take part in the last year's competition which took place in Kaunas University of Technology and had participants from three different Universities in Lithuania.

The best participant was selected to KTU #1 (the 30th place in the last year's ACM finals) and other top KTU participants were selected to KTU #2 and KTU #3 teams.

Moreover, some of the hardest tasks were used in the preparation for IOI competition.

The contest is scheduled on Saturday, Sep 20, 2014, at 12:00 PM.

As the contest has three stars of complexity, it may be very interesting for Div. 2 participants, but I don't recommend it for Div. 1 participants and those who already participated in the contest.

All kinds of feedback are gladly accepted, as this contest is also a dress rehearsal for this year's KTU qualification round which is prepared with Polygon and will be made public for all Codeforces participants.

Enjoy the contest!


Solutions written by the authors of the problems:


All problems have been fixed

Statements of K1 training
Tags gym, ktu
 
 
 
 
  • Vote: I like it  
  • +65
  • Vote: I do not like it  

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What is duration of this contest

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

How long it lasts ? how many problems ? is it rated ?

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

    5 hours. 9-12. gyms are not rated

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

>> KTU qualification round which is prepared with Polygon
>> the sample test case in the system was incorrect, as a result, this task was ruined

not writing validators is harmful

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

    The words of wisdom. However, today the situation has been different. We moved the contest from our old system and we made a mistake copying samples from the pdf. Our solutions ran as there was no mistake.

    And this year's competition are made with Polygon. We will write validators, so I hope that the contest will be much better.

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

How to solve C and G?

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

    I've solved C with a BIT.

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

    You can solve C with segment trees.

    I 'll assume that you now how segment trees work. The node that represents each interval is an array of 26 ( frequency of each letter in the range ).

    You build the segment tree in a normal way: You store at the leaf a single character. For the parents you need to merge the two arrays of frequencies of the two children.

    For the sort query: Sort the original string form [l, r] and then update the segment tree at those position from l to r.

    For the query: You search for the intervals that are within [l, r] and return their frequencies.

    Note: You do not need to use lazy propagation the sum of all updates is less than or equal to 105.

    Here is link to my submission: link

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

    For G you should notice that 109 + 7 is prime.Then instead of finding pairs ab = 1(mod109 + 7) we should find b for the given a and check whether we have b in the list of the given numbers. The funny thing is that b is the reciprocal for a in the finite field and we can use extended Euclid's algo to find it (see e-maxx.ru/algo, as usual). Moreover for any a there is one and only one such b (because our module is prime). We count how many times each number is present in the given sequence, e.g. by having a hashmap of number to count. Then we iterate on all given numbers and for each we calculate min(count(a), count(reciprocal(a)) / 2. Sum of all minimums is the answer (we divide, because we count both (a, b) and (b, a) pairs).

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

    You can solve it by the next way.

    Let f[letter][i] — amount of symbols s[k] == letter for every 0 <= k <= i

    Answer for query g l r is array cnt[i], where cnt[i] = f[i][r] — f[i][l — 1]

    Let's try to sort s[l]..s[r] quickly Let's calculate how many symbols 'a', 'b', 'c'... is in [l..r] (f[i][r] — f[i][l — 1])

    Then in s beginning from l there are cnt['a'] letters 'a', cnt['b'] letters 'b' e.t.c.

    You can easily recalculate all f[i][l..r] by simply iteration from l to r

    It's all:)

    Of course, you can improve this solution, but during the training I didn't need it.

    My solution: click

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

    for C You just need use : sort (a+l,a+r+1) for s l r and print all between l & r in string!

    My code: http://ideone.com/sp5hN7

    Problem C is Easy, if We see it Easy :D

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

      This shouldnt pass or the testcase is weak coz there is nothing said about the limit of g operation and it might be up to 6*10^8 which is alot !

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

m

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

What is the idea behind E (Magical Code)?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the idea to solve problem D? I tried this way : Find the maximum spanning tree with respect to the 'nr' (non-resistance) values, then find the maximin nr value for each of the target nodes for paths from the source node, then output those target nodes that has the maximum of those values with the minimum distance from the source. But it results into WA.

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

    It is almost correct, just:

    Find the maximum spanning tree with respect to the 'nr' (non-resistance) values, then find the minimal nr value for each of the target nodes for paths from the source node, then output those target nodes that has the maximum of those values with the minimum distance from the source.

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

      Sorry, I actually meant that. After getting the maximum spanning tree, I find the minimum nr value on the path to each target node, which is the maximin path value for each target on the initial graph. Here is my code: link

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can E be solve by dynamic programming?If so then what is the approach?