prophet_ov_darkness's blog

[GYM] 2019 MIST IUPC Replay
By prophet_ov_darkness, 6 years ago, In English

Hi Codeforces community!

I'm glad to invite you to the online replay of 2019 MIST IUPC, which will be hosted on Codeforces Gym on Sunday, March 17, 2019, 1 PM MSK, and will run for 5 hours. This is an ICPC style contest comprising of 9 problems of varying difficulties.

ICPC style national level contests are frequent in Bangladesh, and they are commonly referred to Inter University Programming Contest (IUPC). From now on, we plan to regularly upload these contests to CF Gym.

MIST IUPC 2019 was organized by Military Institute of Science and Technology. 120 teams participated in the onsite contest, which took place on February 23, 2019.

Bangladesh Association of Problem Setters (BAPS) was in charge of the problem set. Problems were prepared, reviewed, and tested by Shahriar Manzoor, Jami_CSEDU, shovonshovo, shibly, Imran_Bin_Azad, ridowan007, Shafaet, Mehdi Rahman, Rafsan, sgtlaugh, bhadra, flash_7, Z0RR0, and prophet_ov_darkness.

GLHF.

UPD 1: The contest was over a couple of hours ago. We are currently working on an editorial. We will share it as soon as it is ready.

UPD 2: Here is the editorial.

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

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

That's a great initiative.

→ Reply
»
6 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Love this initiative!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Thanks! Can you please write/ crowd-source an editorial, like you did for SUB contest? As there are only 9 problems, it can be easily done by three persons.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      Yeah, sure. I can try. But I have got a term final tomorrow. So it should take some time.

      → Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Reminder: The contest will start in 30 minutes.

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

How to solve E — consecutive letters ?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

any hint for problem no B , mysterious LCM

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Though I was not able to solve the problem in the alloted time (still getting WA) but I think I have some ideas.

    1. First of all we can factorise X, two cases might be troublesome, If X is a big prime (can be checked with miller rabin),if X is product of 2 big primes, then either we can search for the two big primes using the numbers given in the array or else we can assume X to be a big prime instead of being a product of 2 primes, this will not affect the final ans.
    2. Then we eliminate unnecessary numbers in array. first way is to eliminate numbers which dont reduce to 1 by constantly dividing by prime factors of X as long as we can,also eliminate numbers which get divided by some prime factor of X more times than X itself, second way is to eliminate numbers like for ex. if X=30, then numbers like 2 and 3 can be eliminated if 6 is present in array. The last elimination is tricky, but if I am not wrong can be done in O(1<<(distinct prime factors of X)).
    3. Then we need a dp[i][mask]= minimum elements needed in first i elements out of remaining elements so that by using them, powers of prime factors corresponding to set bits in mask that needed to be present in final lcm have already been satisfied. I may be wrong but this is what I think of the problem.
    → Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Link to the editorial has been added to the post.

→ Reply